🔥 10.14 360笔试面经 - 编程题 & 题解

考试平台： 牛客

考试时间: 2023-10-14 (120 分钟)

考试题型: 选择题 + 2道编程题

投递岗位：大数据开发工程师

T1 复制粘贴

时间限制:3000MS

内存限制:589824KB

题目描述

小明最近学会了快捷键Ctrl C、Ctrl V。具体来说，给她一个字符串，她复制其中的一个字符并将其粘贴到这个字符的下一位，从而整个字符串的长度加一。小树来检测她的学习成果。他给出两个字符串 s、t，小明可以对 s 进行任意次复制粘贴操作，请问她能否将 s 转化成 t?

输入描述

本题采用多组数据测试，第一行为数据组数T。

在接下来的每组数据中 (1<=T<=100) 第一行有个非空字符串 s,第二行有一个非空字符串t。

字符串中均为小写字母，所有测试数据的 s 的长度之和与t的长度之和都不超过.

输出描述

对于每组数据输出一行，如果可以转化输出YES，否则输出NO.

样例

输入：
4
hello
hello
hello
helloo
hello
hlllloo
hello
helo

输出：
YES
YES
NO
NO

题解

双指针，

题意：复制其中的一个字符并将其粘贴到这个字符的下一位，意思就是 t 中的字符可以比s中的某个字符串重复的次数多，但不能少。

两个字符串利用两个指针进行模拟比较。

import java.util.Scanner;

/**
 * P1
 * @author code5bug (同v)
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        in.nextLine();

        Solution solution = new Solution();
        for (int i = 0; i < T; i++) {
            String s = in.nextLine();
            String t = in.nextLine();
            System.out.println(solution.solve(s.toCharArray(), t.toCharArray()) ? "YES" : "NO");
        }
    }
}


class Solution {
    public boolean solve(char[] s, char[] t) {
        if (s.length > t.length) return false;

        int n1 = s.length, n2 = t.length;
        int i = 0, j = 0;
        while (i < n1 && j < n2) {
            int cnt1 = 0;
            while (i + 1 < n1 && s[i] == s[i + 1]) {
                i++;
                cnt1++;
            }

            int cnt2 = 0;
            while (j + 1 < n2 && t[j] == t[j + 1]) {
                j++;
                cnt2++;
            }

            if (s[i] != t[j] || cnt1 > cnt2) return false;

            i++;
            j++;
        }

        return i == n1 && j == n2;
    }
}

T2 加密算法

时间限制:3000MS

内存限制:589824KB

题目描述

小X和小Y正在进行加密算法有关的研究。 小X提出了一种简单的加密算法: 对于一个只包含小写英文字母的字符串，将’a’替换成1，’ b'替换成2........，’z’ 替换成26，比如一个字符串’ abcyz',加密后变成 '1232526' 但是小Y觉得对于一个加密后的数字串可能对应很多原串:比如’ 1232526’可能表示’abcyz’,也可能表示’abcbebf’,也可能表示’lcyz’ .....。但固执的小X并不想听取小Y的想法。为了说服小X，小Y希望能计算出某个加密后的数字串可能对应的原串个数，由于答案可能很大，请输出答案对1000000007(10^9+7)取模后的结果。

输入描述

第一行一个正整数n,表示加密后的数字串的长度接下来一行字符串长度为n,表示加密后的数字串.对于所有数据，n<= 50000，保证输入字符串所有字符是’ 1’到’9’的数字

输出描述

输出一个正整数表示可能的原串个数

样例

输入：
6
114514

输出：
6

提示：
分别是'aadead’,kdead’,kden’,aaden’,anead’,anen'六种可能的原串

题解

动态规划， 爬楼梯题目的升级

import java.util.Scanner;
/**
 * P2
 * @author code5bug (同v)
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        char[] cs = in.nextLine().toCharArray();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = cs[i] - '0';

        Solution solution = new Solution();
        System.out.println(solution.solve(a));

    }
}


class Solution {
    int MOD = (int) 1e9 + 7;

    public int solve(int[] a) {
        int n = a.length;
        // dp[i] 表示长度为 i 的字符串解密后可能的原串个数
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;

        for (int i = 1; i < n; i++) {
            // 当前字符单独解密映射
            int sum = dp[i];
            // 当前字符和前一个字符一起解密映射一个字符
            if (a[i - 1] == 1 || (a[i - 1] == 2 && a[i] < 7)) {
                sum = (sum + dp[i - 1]) % MOD;
            }

            dp[i + 1] = sum;
        }
        return dp[n];
    }
}

如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。