2022.03.14

我参加的是 2022.03.25 的笔试，03.14 的笔试题摘自牛客网：2022.3.14 阿里算法暑期实习笔试

1. 求 (x*y) mod m 的最大值

题目：
给出 a, b, c, d, m 求 a<=x<=b, c<=y<=d，求 (x*y) mod m 的最大值。（1<=a<=b<=1000, 1<=c<=d<=1000）

#include <iostream>
using namespace std;
int main()
{
    int a = 1;
    int b = 1000;
    int c = 1;
    int d = 1000;
    int m = 699;
    int result = 0;
    for(int x = a; x <= b; ++x)
    {
        for(int y = c; y <= d; ++y)
        {
            // 性质：(x*y) mod m = ((x mod m) * (y mod m)) mod m
            int cur = ((x % m) * (y % m)) % m;
            result = max(result, cur);
        }
    }
    cout << result << endl;
    return 0;
}

2. 交换字符得到的字符串个数

题目：
给定一个字符串 s, 任意交换两个不同位置的字符一次，求可以得到的不同的字符串的个数

注：如下代码中的 int 可能需要改为 long long

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
    string s = "abccd";
    // 1. 遍历字符串，统计 <字符，出现次数>，存储到哈希表
    unordered_map<char, int> chCntMap;
    for(int i = 0; i < s.size(); ++i)
        ++chCntMap[s[i]];
    int result = 0;        // 结果，即不同的字符串的个数
    int flag = 0;        // 是否存在相同字符（即是否存在出现次数 ＞ 1 的字符）
    // 2. 遍历哈希表，计算任意交换两个不同位置的字符一次可以得到的不同字符串的个数
    for(auto it = chCntMap.begin(); it != chCntMap.end(); ++it)
    {
        int cnt = it->second;                // 当前字符出现的次数
        // 当前字符可以和其它不同字符交换，加到结果里
        result += cnt * (s.size() - cnt);    
        // 如果当前字符出现次数大于 1，令 flag 为 1
        if(cnt > 1)
            flag = 1;
    }
    // 3. 计算最终的结果
    // a. 如上统计的每个字符串实际上都会出现两次，所以要 / 2. 
    //    eg. 遍历到字符 a 时，算了字符 a 和 字符 b 交换；遍历字符 b 时，字符 b 和字符 a 交换，
    //          重复统计了
    // b. 如上的统计没有考虑一种情况：任意两个相同的字符交换，会得到原字符串，这个字符串也要计数加到结果里
    cout << result / 2 + flag << endl;
    return 0;
}

3. 分割数字求和

题目：
给出 n 个数字，可以对每个数字进行若干次切割，问最少几次切割能使得所有数字之和是 k 的倍数。（1<=n, k<=200, 1<=a[i]<=1e18）

2022.03.25

我参加的这场，感觉都不难，都能有思路写出来，但是只 A 了 0.83.3/3，心态炸了

1. 判断用户名是否合法 83.3%

用户名的要求：

长度在 [6, 12] 区间内，每个字符只能是大小写字母
这个用户名必须未注册过

判断顺序：

如果用户名长度不合法，则输出 “illegal length”
如果包含大小写字母以外的字符，则输出 “illegal character”
如果用户名注册过，输出 “existed”
如果合法，则输出 “success”

输入：第一行 T 代表输入的用户名数量，后面 T 行每行代表一个用户名
输出：T 行，每行输出对应用户名的合法情况

坑点：只过了 83.3%，是因为提交的样例中包含存在空格的情况

eg. “abcd efg”
应该每次读一行，而不是 cin >> str，这样在空格处就断掉了

C++ 读入整行：**getline(cin, str)**

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string str;
    getline(cin, str);
    cout << str;
    return 0;
}

2. 5 个数取 4 个减一的次数 0%

给定 5 个数，每次从中取 4 个数减一，但不能减为负数，问可以减几次。

输入：T 行，之后 T 行每行 5 个数
输出：T 行，每行代表对应的 5 个数能减一的次数

错误解法：将数组从小到大排序，则 reuslt = nums[1] + min(nums[2] - nums[1], nums[0])

示例：对于 3 3 3 6 7 这 5 个数，用上面的思路得到结果是 3 ，但实际是 4，即 3 3 3 6 7 -> 3 2 2 5 6 -> 2 1 2 4 5 -> 1 1 1 3 5 -> 0 0 0 2 4
因此，应该暴力模拟，每次都选择最小的 4 个数减 1（也就是说，每次减 1 后都要重新排序）。但是暴力模拟会超时，所以也只能通过 40%

参考：2141. 同时运行 N 台电脑的最长时间

3. 合法字符串 0%

空串 S 是合法的
bSaSb 也是合法的（要求两个 S 相等，且 S 合法）
cScS 也是合法的（要求两个 S 相等，且 S 合法）

判断输入的字符串是否合法

解法：

遍历字符串 s，看是否包含 'a', 'b', 'c'之外的字符，如果包含，则直接输出 No
否则，动态规划
1. 动态规划数组 dp[i][j] 代表字符串 s[i...j] 是否合法
2. 状态转移：
  1. 若 s[i] =='b' 且 s[j]=='b'：遍历 k in [i + 1, j - 1]，若存在 k 使得 s[k] == 'a' 且 s[i+1...k-1] == s[k+1...j-1] 且 dp[i+1][k-1] == true，则 dp[i][j]=true
  2. 若 s[i] == 'c'：遍历 k in [i + 1, j]，若存在 k 使得 s[k] == 'c' 且 s[i+1...k-1] == s[k+1...j] 且 dp[i+1][k-1] == true，则 dp[i][j]=true
3. 初始化：先全部初始化为 false
  1. 对于空串，即 i < j，dp[i][j] = true
  2. 两个字符，如果 i + 1 < len，且 s[i, i+1] = "cc"，则 dp[i][i+1] = true
  3. 三个字符，如果 i + 2 < len，且 s[i, i+1, i+2] = "bab"，则 dp[i][i+2] = true
4. dp[i][j] 取决于 dp[i+1][k-1]，所以状态转移的时候，i 逆向遍历，k 正向遍历

问题：内存超过限制，可能需要压缩成一维 dp 数组，但是没时间改了。。。

《百面机器学习》诸葛越

阿里算法暑期实习笔试 2022.03.25