LeetCode第289场周赛题解

T1. 计算字符串的数字和

给你一个由若干数字（0 - 9）组成的字符串 s ，和一个整数。

如果 s的长度大于k ，则可以执行一轮操作。在一轮操作中，需要完成以下工作：

将 s 拆分成长度为 k的若干连续数字组，使得前 k 个字符都分在第一组，接下来的 k 个字符都分在第二组，依此类推。注意，最后一个数字组的长度可以小于 k 。
用表示每个数字组中所有数字之和的字符串来替换对应的数字组。例如，"346" 会替换为"13" ，因为3 + 4 + 6 = 13。
合并所有组以形成一个新字符串。如果新字符串的长度大于k 则重复第一步。
返回在完成所有轮操作后的 s 。

示例 1：

输入：s = "11111222223", k = 3
输出："135"
解释：

第一轮，将 s 分成："111"、"112"、"222" 和 "23" 。
接着，计算每一组的数字和：1 + 1 + 1 = 3、1 + 1 + 2 = 4、2 + 2 + 2 = 6 和 2 + 3 = 5 。 
这样，s 在第一轮之后变成 "3" + "4" + "6" + "5" = "3465" 。

第二轮，将 s 分成："346" 和 "5" 。
接着，计算每一组的数字和：3 + 4 + 6 = 13 、5 = 5 。
这样，s 在第二轮之后变成 "13" + "5" = "135" 。 
现在，s.length <= k ，所以返回 "135" 作为答案。

示例 2：

输入：s = "00000000", k = 3
输出："000"
解释：
将 "000", "000", and "00".
接着，计算每一组的数字和：0 + 0 + 0 = 0 、0 + 0 + 0 = 0 和 0 + 0 = 0 。 
s 变为 "0" + "0" + "0" = "000" ，其长度等于 k ，所以返回 "000" 。

提示：

1 <= s.length <= 100
2 <= k <= 100
s 仅由数字（0 - 9）组成。

方法一：递归

题目分析： 题目的意思就是不断的去替换，直到替换后字符串的长度小于k，那么我们可以考虑用递归去做，因为他的每下一个操作都是类似的形式，所以完全可以用递归去做

首先我们每隔k个字符计算一次，用新的字符串去加上计算后的结果，相当于文章中的替换
因为是每隔k个计算一次，所以可能会有剩下的字符没有计算，所以用一个flag去记录一下是否有剩下字符串没有计算
如果当前字符串的长度小于k，那么直接不返回这个字符串
如果不是那么就递归计算，直到当前字符串长度小于k

class Solution {
public:
    string solve(string s,int k){
        int n=s.size(); 
        int cnt=0,sum=0;
        string ss="";
        int flag;
        for(int i=0;i<n;++i){
            ++cnt;
            sum+=(s[i]-'0');
            flag=1;
            if(cnt%k==0){
                flag=0;
                ss+=to_string(sum);
                sum=0;
            }
        }
        if(flag)//判断是否存在剩下未计算的字符串
        ss+=to_string(sum);
        return ss;
    }
    string digitSum(string s, int k) {
        if(s.size()<=k)
            return s;
       string str=solve(s,k);
       if(str.size()<=k)
           return str;
        return digitSum(str,k);
    }
};

方法二：模拟

其实本题的正解应该是模拟

只不过是把每次替换后的字符串重新赋给s，然后再去替换，直到被替换后字符串的长度小于k，模拟代码中if(i%k==k-1||i+1==s.size())很巧妙，可以试着参考这句代码修改上面递归的代码，可以让递归的代码更加简洁

class Solution {
public:
    string digitSum(string s, int k) {
        while(s.size()>k){
            string ns;
            int ans=0;
            for(int i=0;i<s.size();++i){
               ans+=s[i]-'0';
               if(i%k==k-1||i+1==s.size()){
                   ns+=to_string(ans);
                   ans=0;
               }
            }
            s=ns;
        }
        return s;
    }
};

T2. 完成所有任务需要的最少轮数

给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。在每一轮中，你可以完成 2 个或者 3 个相同难度级别的任务。

返回完成所有任务需要的最少轮数，如果无法完成所有任务，返回 -1 。

示例 1：

输入：tasks = [2,2,3,3,2,4,4,4,4,4]
输出：4
解释：要想完成所有任务，一个可能的计划是：

第一轮，完成难度级别为 2 的 3 个任务。 

第二轮，完成难度级别为 3 的 2 个任务。 

第三轮，完成难度级别为 4 的 3 个任务。 

第四轮，完成难度级别为 4 的 2 个任务。 
可以证明，无法在少于 4 轮的情况下完成所有任务，所以答案为 4 。

示例2：

输入：tasks = [2,3,3]
输出：-1
解释：难度级别为 2 的任务只有 1 个，但每一轮执行中，只能选择完成 2 个或者 3 个相同难度级别的任务。因此，无法完成所有任务，答案为 -1 。

提示：

1 <= tasks.length <= 105
1 <= tasks[i] <= 109

题目分析：哈希表+贪心

首先用map去统计每个元素出现的次数，存进数组里
因为题目要求最少轮数，所以我们每次都尽可能做3难度级别个数任务
通过几次发现，其实最少轮数就是相同元素个数除以3向上取整

class Solution {
public:
    int minimumRounds(vector<int>& tasks) {
        map<int,int>mp;
        int n=tasks.size();
        for(int i=0;i<n;++i){
            mp[tasks[i]]++;
        }
        int ans=0;
        for(auto x=mp.begin();x!=mp.end();x++){
            if(x->second==1)
                return -1;
            if(x->second%3)
                ans+=(x->second+3)/3;
            else
                ans+=x->second/3;
        }
        return ans;
    }
};

换一种形式，其实y对x向上取整就是y加上x-1再除以x

class Solution {
public:
    int minimumRounds(vector<int>& tasks) {
        map<int,int>mp;
        int n=tasks.size();
        for(int i=0;i<n;++i){
            mp[tasks[i]]++;
        }
        int ans=0;
        for(auto x:mp){
            if(x.second==1)
                return -1;
            ans+=(x.second+2)/3;
        }
        return ans;
    }
};

T4. 相邻字符不同的最长路径

给你一棵树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为n 的数组 parent来表示这棵树，其中parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以parent[0] == -1。

另给你一个字符串 s ，长度也是n ，其中s[i]表示分配给节点i的字符。

请你找出路径上任意一对相邻节点都没有分配到相同字符的最长路径，并返回该路径的长度。

示例 1：
在这里插入图片描述

输入：parent = [-1,0,0,1,1,2], s = "abacbe"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。
可以证明不存在满足上述条件且比 3 更长的路径。

示例 2：
在这里插入图片描述

输入：parent = [-1,0,0,0], s = "aabc"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。

提示：

n == parent.length == s.length
1 <= n <= 10⁵
对所有i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent表示一棵有效的树
s 仅由小写英文字母组成

题目分析：树的直径（树形dp）

题目求的是任意相邻两点不能是相同字符的最大长度

可以转化为：对于每一个节点，以该节点为根节点，在符合题目要求的情况下，求其子树的直径，然后不断回溯，求出最长路径

class Solution {
public:
    vector<int>edge[100010];
    int dis[100010];//dis[i]表示以i为根节点的最大深度
    int ans=0;
    string str;
    void dfs(int u){//找出当前节点为根节点的最大深度和次大深度
        int second_dis=0;//记录次大深度
        dis[u]=0;
        for(int i=0;i<edge[u].size();++i){
            int v=edge[u][i];
            dfs(v);
            if(str[u]==str[v])
            continue;
            if(dis[v]>dis[u]){//求以u节点为根节点的最大深度
                second_dis=dis[u];
                dis[u]=dis[v];
            }else
            second_dis=max(dis[v],second_dis);//更新次大深度
        }
        dis[u]++;//考虑节点自身加一
        ans=max(ans,dis[u]+second_dis);
    }
    int longestPath(vector<int>& parent, string s) {
        int n=parent.size();
        str=s;
        for(int i=1;i<n;++i)
        edge[parent[i]].push_back(i);
        dfs(0);
        return ans;
    }
};