WNJXYKの博客

Problem A: 计算字符串的数字和

按照题目意思模拟即可，题目主要操作为：

1. 将数组切分成长度为 k 的若干段，利用 Python 切片功能显示
2. 对数字统计各位之和，定义 sum 函数实现制定功能
3. 重复题目所述操作直到满足条件，利用递归实现

class Solution:
    def sum(self, s):
        ret = 0
        for c in s: ret += int(c)
        return ret
    
    def digitSum(self, s: str, k: int) -> str:
        if len(s) <= k: return s
        n = len(s)
        
        strs = [s[i: min(i+k, n)] for i in range(0, n, k)]
        ret = ""
        for s in strs:
            ret += str(self.sum(s))
        return self.digitSum(ret, k)

Problem B: 完成所有任务需要的最少轮数

仅难度相同的任务才可以一起完成，因此，首先对任务数组排序，将其切分成任务难度相同的若干段，对每一段单独考虑。

考虑一段长度为 \(l\) 的任务，由于每次仅能完成 \(2\) 个或 \(3\) 个任务，因此当 \(l\) 为 \(1\) 时，永远无法完成它，直接返回不可行，否则一定可以通过 \(\lfloor \frac{l}{3} \rfloor\) 轮将这段任务完成。

class Solution {
public:
    int minimumRounds(vector<int>& tasks) {
        sort(tasks.begin(), tasks.end());
        int n = tasks.size();
        int ans = 0;
        
        for (int i = 0, j; i < n; i = j){
            j = i;
            while(j < n && tasks[j] == tasks[i]) j++;
            int l = j - i;
            if (l == 1) return -1;
            if (l % 3 == 0) ans += l / 3; else ans += l / 3 + 1;
        }
        
        return ans;
    }
};

Problem C: 转角路径的乘积中最多能有几个尾随零

由于我们仅需要计算乘积末尾 \(0\) 的数量，因此，我们只需要统计乘积中质因子 \(2\) 与 \(5\) 的数量即可。

由题意，拐角至多出现一次，因此，我们可以首先枚举拐角处的元素，然后枚举从此点出发的路径分别往什么方向延伸，复杂度为 \(O(4nm)=O(nm)\)。

对于每种的情况，我们需要快速计算乘积中 \(2\) 与 \(5\) 的数量，这里用前缀和就可以做到。在代码中，我们首先维护纵方向与横方向数字中质因子 \(2\) 与 \(5\) 数量的前缀和，在查询时，利用两个前缀和相减即可统计出一段路径上对应的质因子数量。

const int MAXN = 5e5 + 50;
int sav2[2][MAXN], sav5[2][MAXN];

class Solution {
public:
    
    void set(int arr[], int m, int i, int j, int v){
        m += 1;
        arr[i * m + j] = v;
    }
    int get(int arr[], int m, int i, int j){
        m += 1;
        return arr[i * m + j];
    }
    
    int gets(int arr[], int n, int m, int i, int j, int typ, int dir){
        if (dir == 0) return get(arr, m, i, j);
        if (typ == 0) return get(arr, m, n, j) - get(arr, m, i - 1, j);
        return get(arr, m, i, m) - get(arr, m, i, j - 1);
    }
    
    int maxTrailingZeros(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        
        for (int i = 0; i <= n; i++) set(sav2[0], m, i, 0, 0), set(sav2[1], m, i, 0, 0), set(sav5[0], m, i, 0, 0), set(sav5[1], m, i, 0, 0);
        for (int j = 0; j <= m; j++) set(sav2[0], m, 0, j, 0), set(sav2[1], m, 0, j, 0), set(sav5[0], m, 0, j, 0), set(sav5[1], m, 0, j, 0);
        
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                int cnt2 = 0, cnt5 = 0;
                while(grid[i][j] % 2 == 0) cnt2 += 1, grid[i][j] /= 2;
                while(grid[i][j] % 5 == 0) cnt5 += 1, grid[i][j] /= 5;
                set(sav2[0], m, i + 1, j + 1, get(sav2[0], m, i, j + 1) + cnt2);
                set(sav2[1], m, i + 1, j + 1, get(sav2[1], m, i + 1, j) + cnt2);
                set(sav5[0], m, i + 1, j + 1, get(sav5[0], m, i, j + 1) + cnt5);
                set(sav5[1], m, i + 1, j + 1, get(sav5[1], m, i + 1, j) + cnt5);
            }
        }
        
        int ans = 0;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                for (int ta = 0; ta < 2; ta++) for (int tb = 0; tb < 2; tb++)
                    ans = max(ans, min(
                        gets(sav2[0], n, m, i, j, 0, ta)
                        + gets(sav2[1], n, m, i, j, 1, tb)
                        - (get(sav2[0], m, i, j) - get(sav2[0], m, i - 1, j)),
                        gets(sav5[0], n, m, i, j, 0, ta)
                        + gets(sav5[1], n, m, i, j, 1, tb)
                        - (get(sav5[0], m, i, j) - get(sav5[0], m, i - 1, j))
                    ));
            }
        }
        return ans;
    }
};

Problem D: 6073. 相邻字符不同的最长路径

简单地在树上进行动态规划。

首先考虑树上的一条路径，找到其中深度为小的节点，记为 \(x\)。此路径可以拆解为 \(x\) 向下的两条链（也有可能是一条）。因此，想要找到最长路径，不妨在树上 DFS 到节点 \(x\) 时候考虑所有以 \(x\) 为根结点向下延伸两条链组成的路径，当我们 DFS 了整棵树，也就考虑了全部的路径。

当我们 DFS 到节点 \(x\) 的时候，我们需要知道从 \(x\) 向下延伸且相邻字符不同的链中长度最大与次大是多少（将他们拼起来可以形成长度最长的候选路径）。因此，定义 DFS 函数返回从 \(x\) 节点向下且相邻字符不同的链的最长长度，并在 DFS 的过程中进行拼接链的操作。

整体复杂度为 \(O(n)\)。

const int MAXN = 1e5 + 50;
vector<int> edge[MAXN];
class Solution {
public:
    
    int ans = 0;
    
    int dfs(int x, int fa, const string &s){
        char c = s[x];
        int m1 = 0, m2 = 0;
        for (int v: edge[x]){
            char nc = s[v];
            if (nc == c) dfs(v, x, s); else{
                int m = dfs(v, x, s);
                if (m > m1) m2 = m1, m1 = m; else{
                    if (m > m2) m2 = m;
                }
            }
        }
        ans = max(ans, m1 + m2 + 1);
        return m1 + 1;
    }
    
    int longestPath(vector<int>& fa, string s) {
        int n = fa.size(), rt = -1;
        for (int i = 0; i < n; i++) edge[i].clear();
        for (int i = 0; i < n; i++){
            if (fa[i] == -1) rt = i; else {
                edge[fa[i]].push_back(i);
            }
        }
        ans = 0;
        dfs(rt, -1, s);
        return ans;
    }
};