LeetCode第390场周赛题解（c++）

真的无语了，早上怎么都提交不了，显示未知错误。。。

结果晚上就可以提交了。唉

100245.每个字符最多出现两次的最长子字符串

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该

子字符串

的 最大 长度。

示例 1：

输入： s = "bcbbbcba"

输出： 4

解释：

以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。

示例 2：

输入： s = "aaaa"

输出： 2

解释：

以下子字符串长度为 2，并且每个字符最多出现两次："aaaa"。

提示：

• 2 <= s.length <= 100
• s 仅由小写英文字母组成。

这个代码是我自己写的，应该没有那些大佬写的简洁。

思路就是遍历所有可能的字符串，在遍历过程中，终止条件有两个：

• 当unordered_map,char ,int> charCount里面，某个字符个数>=3
• 当该子字符串已经到原字符串的结尾，虽然没有某个字符个数>=3，但是应该结束
• 在这2种情况下，每次进行maxStr的更新

#include<iostream>
#include<unordered_map>
using namespace std;
int maximumLengthSubstring(string s) {
        int len=s.length();
        int maxStr=0;
        
        for(int i=0;i<len;i++){
            unordered_map<char,int> charCount;
            for(int j=i;j<len;j++){
                 char currChar=s[j];
                 charCount[currChar]++;
                 if(charCount[currChar]>=3){
                    maxStr=max(maxStr,j-i);
                    break;
                }
                if(j==len-1){
                    //最后面了
                    maxStr=max(maxStr,j-i+1);
                }
            }
        }

        return maxStr;
    }

    int main(){
	   string s="aaaa";
	   int a=maximumLengthSubstring(s);
	   cout<<a;
	   return 0;
 }

100228.执行操作使数据元素之和大于等于K

给你一个正整数 k 。最初，你有一个数组 nums = [1] 。

你可以对数组执行以下 任意 操作 任意 次数（可能为零）：

• 选择数组中的任何一个元素，然后将它的值 增加 1 。
• 复制数组中的任何一个元素，然后将它附加到数组的末尾。

返回使得最终数组元素之 和 大于或等于 k 所需的 最少 操作次数。

示例 1：

输入：k = 11

输出：5

解释：

可以对数组 nums = [1] 执行以下操作：

• 将元素的值增加 1 三次。结果数组为 nums = [4] 。
• 复制元素两次。结果数组为 nums = [4,4,4] 。

最终数组的和为 4 + 4 + 4 = 12 ，大于等于 k = 11 。
执行的总操作次数为 3 + 2 = 5 。

示例 2：

输入：k = 1

输出：0

解释：

原始数组的和已经大于等于 1 ，因此不需要执行操作。

提示：

• 1 <= k <= 105

#include<iostream>
#include<cmath>
using namespace std;
int minOperations(int k) {
        //肯定是先+再copy用的次数少
        /*
        假设1先加了m次成为1+m;
        然后copy了n次成为(1+m)*(1+n);
        题目要求： (1+m)*(1+n)>=k;
        简化一下就是：
        M*N>=k 同时 M+N最小
        即M+k/M最小，这是一个对勾函数，根据函数性质可知
        当M=sqrt(k)时最小；
        需要向上/下取整
        */
        int M,N;
        M=ceil(sqrt(k));
        N= (k + M - 1) / M;
        return M+N-2;

}
int main(){
    int t=minOperations(11);
    cout<<t;

    return 0;
}

（这个思路是我下午两点看灵茶直播时候讲的思路，感觉非常nice）

100258.最高频率的ID

你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ，nums 中每一个元素表示一个 ID ，对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。

• 增加 ID 的数目：如果 freq[i] 是正数，那么 freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会添加到集合中。
• 减少 ID 的数目：如果 freq[i] 是负数，那么 -freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会从集合中删除。

请你返回一个长度为 n 的数组 ans ，其中 ans[i] 表示第 i 步操作后出现频率最高的 ID 数目 ，如果在某次操作后集合为空，那么 ans[i] 为 0 。

示例 1：

输入：nums = [2,3,2,1], freq = [3,2,-3,1]

输出：[3,3,2,2]

解释：

第 0 步操作后，有 3 个 ID 为 2 的元素，所以 ans[0] = 3 。
第 1 步操作后，有 3 个 ID 为 2 的元素和 2 个 ID 为 3 的元素，所以 ans[1] = 3 。
第 2 步操作后，有 2 个 ID 为 3 的元素，所以 ans[2] = 2 。
第 3 步操作后，有 2 个 ID 为 3 的元素和 1 个 ID 为 1 的元素，所以 ans[3] = 2 。

示例 2：

输入：nums = [5,5,3], freq = [2,-2,1]

输出：[2,0,1]

解释：

第 0 步操作后，有 2 个 ID 为 5 的元素，所以 ans[0] = 2 。
第 1 步操作后，集合中没有任何元素，所以 ans[1] = 0 。
第 2 步操作后，有 1 个 ID 为 3 的元素，所以 ans[2] = 1 。

提示：

• 1 <= nums.length == freq.length <= 105
• 1 <= nums[i] <= 105
• -105 <= freq[i] <= 105
• freq[i] != 0
• 输入保证任何操作后，集合中的元素出现次数不会为负数。

淦。明天再写吧。。。好困