笔试时间：2024年03月23日 阿里钉钉

历史笔试传送门：2023秋招笔试合集

第一题

题目：小红劈字符串

小红定义一个字符串满足以下条件即为好串:

‘r’的数量比‘e’多。

‘e’的数量比‘d’多。

现在小红拿到了—个字符串,她想劈一刀将字符串劈成2部分,满足左边和右边都是好串。

小白想知道有多少种不同的劈法？

输入描述

第一行输入个正学数n,代表字符串长度。第二行输入个长度为n的、仅由"red”三种字符组成的字符串。

1<=n<=10^5

输出描述

一个整数,代表最终劈字符串的方案数。

样例输入

10

rerdrrerer

样例输出

2

说明

第1种劈法:"rer"+"drrerer"

第2种劈法:"rerdrre"+"rer"

参考题解

比较典型的前缀和算法：计算从0到每个下标的red三种字符的数量，然后枚举每个下标，判断当前下标是否可以得到两个好串，最后累加即可。

C++：[此代码未进行大量数据的测试，仅供参考]

int main() {
  int n; cin >> n;
  string s; cin >> s;
  vector<vector<int>> arr(n + 1, vector<int>(3, 0));
  for (int i = 0; i < n; ++i) {
    arr[i + 1] = arr[i];
    int c = s[i] == 'r' ? 0 : (s[i] == 'e' ? 1 : 2);
    arr[i + 1][c] += 1;
  }
  int ans = 0;
  for (int i = 0; i < n - 1; ++i) {
    bool ok1 = false, ok2 = false;
    if (arr[i + 1][0] > arr[i + 1][1] && arr[i + 1][1] > arr[i + 1][2]) ok1 = true;
    int a = arr[n][0] - arr[i + 1][0], b = arr[n][1] - arr[i + 1][1], c = arr[n][2] - arr[i + 1][2];
    if (a > b && b > c) ok2 = true;
    ans += (ok1 && ok2);
  }
  cout << ans;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = scanner.next();
        int[][] arr = new int[n + 1][3];
        for (int i = 0; i < n; ++i) {
            System.arraycopy(arr[i], 0, arr[i + 1], 0, 3);
            int c = s.charAt(i) == 'r' ? 0 : (s.charAt(i) == 'e' ? 1 : 2);
            arr[i + 1][c] += 1;
        }
        int ans = 0;
        for (int i = 0; i < n - 1; ++i) {
            boolean ok1 = false, ok2 = false;
            if (arr[i + 1][0] > arr[i + 1][1] && arr[i + 1][1] > arr[i + 1][2]) ok1 = true;
            int a = arr[n][0] - arr[i + 1][0], b = arr[n][1] - arr[i + 1][1], c = arr[n][2] - arr[i + 1][2];
            if (a > b && b > c) ok2 = true;
            ans += (ok1 && ok2) ? 1 : 0;
        }
        System.out.println(ans);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
s = input()
arr = [[0] * 3 for _ in range(n + 1)]
for i in range(n):
    arr[i + 1] = arr[i][:]
    c = 0 if s[i] == 'r' else (1 if s[i] == 'e' else 2)
    arr[i + 1][c] += 1
ans = 0
for i in range(n - 1):
    ok1, ok2 = False, False
    if arr[i + 1][0] > arr[i + 1][1] and arr[i + 1][1] > arr[i + 1][2]:
        ok1 = True
    a, b, c = arr[n][0] - arr[i + 1][0], arr[n][1] - arr[i + 1][1], arr[n][2] - arr[i + 1][2]
    if a > b and b > c:
        ok2 = True
    ans += 1 if ok1 and ok2 else 0
print(ans)

第二题

题目：小苯的密码锁

小苯有一个长为n位的密码锁,但和普通常见的密码锁不一样的是,他的密码锁每位都是数字0,1,2中的一个。并且小苯的密码锁只能向上转动,如0向上转动一次会变成1,再向上转—次会变成2,再向上转一次又会变回0。小苯想解开他的密码锁,他的密码锁解锁条件十分特殊,要求:任意相邻的两位都不相同,即可解锁。例如如果当前密码锁的数字为:"1212”即可解锁,而"1120"由于第一位和第二位相同因此不能解锁。他现在想知道,自己最少需要操作多少次可以使得密码锁解锁。操作指:任选锁中的一位数字,将他向上转动一次。

输入描述

输入包含两行。

第一行一个正整数n(1<n< 10),表示密码锁的位数。

第二行一个长度为n的字符串 s,表示密码锁当前的状态。(保证s中只包含0,1,2三种字符.)

输出描述

输出包含一行一个整数,表示最少的操作次数。

样例输入

6

112200

样例输出

3

说明

转动第一位一次,从1变为2。

转动第三位一次,从2变成0。

转动最后一位一次,从0变成1。

参考题解

非常典型的动态规划的题目，密码锁的每一位有三种动作，不转、转一次、转两次，所以枚举三种状态即可。无论是记忆化递归还是迭代的dp，都是可以的。

C++：[此代码未进行大量数据的测试，仅供参考]

int memo[1000005][5];

int main() {
  in