力扣第374场周赛题解

这一场周赛的题目是比较难的一次，写了1个多小时就写了两个题目。

首先第一题：

纯水题，遍历然后进行一下判断就可以解决了。这边就不放代码了。

第二题：

这个题目，我觉得难度非常大，其实代码量也不大都是很难想到解决的方案，在比赛的时候也没写出这个题目，还浪费了很多时间。这个题目的思路其实是，对于数字来说，只有两种情况，我们设置初始区间为[0,s-1]，s设置为1，也就是初始区间什么都没有，然后添加数字,假设这个数字为a，产生的新区间为[0+a,s+a-1],在a小于等于s的情况，0+a<=s-1;也就是说新生成的区间与老区间中间没有空隙，所以此时就可以把区间扩展到[0,s+a-1],s=s+a;但是如果a>s，新产生的区间与老区间就肯定会有空隙我们就肯定需要添加新的数字，然后通过贪心的思想，添加s可以把当前的区间正好扩大一倍，这是只添加一个数字可以做到最大的区间扩张，大于s会产生空隙，小于s扩张的范围会减少。所以这个时候这个问题的解决方案就出来了，a<=s,i++,s=s+a;a>s,添加数字加一，s=s*2；

实现代码：

class Solution {
    public int minimumAddedCoins(int[] coins, int target) {
    Arrays.sort(coins);    
    int ans=0;
    int a=1;
    int i=0;
    while(a<=target){
        if(i<coins.length&&coins[i]<=a){
        a+=coins[i];
        i++;
        }else{
        a*=2;
        ans++;    
        }
    }
    return ans;
    }
}

第三题：

这个题目在比赛的时候写出来了，这个题目思路还是比上面那个题目容易想出来，首先看条件是需要相差至多为2，然后是每个字符恰好出现k次，这两个条件如果是同时去做的话，相关的处理就会比较麻烦，而且也容易超时间，所以最好的解决办法就是把有相邻字符超过2的字符串进行分组求和，这样对于每一组来说只有去考虑子字符串中每个字符恰好出现k次这一个条件，这个用hash表应该没什么问题，当然优化的话就可以使用滑动窗口，因为要求每一个字符串出现k次所以很明显，满足要求的子字符串的长度为n*k,这样就可以求出来所有满足条件的子字符串了。

代码：

class Solution {
    public int countCompleteSubstrings(String word, int k) {
        int n = word.length();
        int ans = 0;
        for (int i = 0; i < n; ) {
            int st = i;
            for (i++; i < n && Math.abs(word.charAt(i) - word.charAt(i - 1)) <= 2; i++) ;
            ans += count(word.substring(st, i), k);
        }
        return ans;
    }
    
    private int count(String S, int k) {
        char[] s = S.toCharArray();
        int res = 0;
        for (int m = 1; m <= 26 && k * m <= s.length; m++) {
            int[] freq = new int[26];
            for (int right = 0; right < s.length; right++) {
                freq[s[right] - 'a']++;
                int left = right + 1 - k * m;
                if (left >= 0) {
                    boolean flag = true;
                    for (int i = 0; i < 26; i++) {
                        if (freq[i] > 0 && freq[i] != k) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        res++;
                    }
                    freq[s[left] - 'a']--;
                }
            }
        }
        return res;
    }
}