陆陆续续这是第三次周赛，第一次是虚拟的我瞎写ac了两题，上一次也是ac两题因为起得太晚了。这次稍微一点点进步，ac两个半，第三题有思路但是暴力超时，是因为我没见过这种数据结构。

Hard就跳了吧

第一题：每个字符最多出现两次的最长子字符串

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

示例 1：

输入： s = “bcbbbcba”

输出： 4

解释：

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

遍历每个字串，判断是否字符只出现两次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int maximumLengthSubstring(String s) {
        int max = 2;
        for (int k = s.length(); k >=1; k--) {
            for (int i = 0; i < s.length() - k; i++) {
                String sub = s.substring(i,i+k+1);
                //如果没有返回false
                if (judge(sub)){
                    max = Math.max(max,sub.length());
                }
            }
        }
        return max;
    }
    //判断字串是否只出现两次，用哈希表实现，如果哈希表超过2就返回false
    public boolean judge(String s){
        HashMap<Character,Integer> map = new HashMap<>();
        boolean flag = true;
        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),1);
            }
            else {
                Integer integer = map.get(s.charAt(i));
                if (integer >= 2){
                    flag = false;
                }
                map.replace(s.charAt(i),integer+1);
            }
        }
        return flag;
    }

}

第二题：执行操作使数据元素之和大于等于 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 。

数学题，假设+1的次数为x，复制的次数为y，要使得(y+1)*(x+1)>=n，而满足x+y最小

满足x+y+2最小其实也是满足x+y最小，那么就是开根号了，由基本不等式可得。

还有个问题就是这里的是整数，假如n=29开根号是5，这个时候用6 * 6=36就浪费了一次，只需要用5 * 6=30就可以，需要进行特殊判断

wa了一次，因为这里如果正好开根号，就直接返回x+y了，不需要-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minOperations(int k) {
        if (k ==1){
            return 0;
        }
        int sqrt = (int) Math.sqrt(k);
        if (k == sqrt*sqrt){
            return sqrt*2-2;
        }
        else {
            if (k <= sqrt *(sqrt+1)){
                return sqrt+sqrt+1-2;
            }
            else {
                return sqrt+1+sqrt+1-2;
            }
        }

    }
}

第三题：最高频率的 ID

高级的排序哈希集（TreeMap）不得不品

你需要在一个集合里动态记录 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 。

暴力超时

hashmap维护当前的频率，每次都对其进行最小值查找，时间复杂度o(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public long[] mostFrequentIDs(int[] nums, int[] freq) {
        long[] ans = new long[nums.length];
        HashMap<Integer,Long> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!hashMap.containsKey(nums[i])){
                hashMap.put(nums[i], (long) freq[i]);
            }
            else {
                long integer = hashMap.get(nums[i]);
                hashMap.replace(nums[i],integer+freq[i]);
            }
            ans[i] = getMost(hashMap);
        }
        return ans;
    }
    //遍历哈希找最小值
    public long getMost(HashMap<Integer,Long> hashMap){
        long max = Long.MIN_VALUE;
        for (Map.Entry<Integer,Long> entry : hashMap.entrySet()){
            max = Math.max(max,entry.getValue());
        }
        return max;
    }
}

TreeMap（重要）

TreeMap是索引为键的有序哈希表，从小到大排序，每次维护treemap只用从最后面找到就是最大值。

这里treemap存的是频率的频率，每当有更新的时候就对应频率的值-1，如果为0了就删除，然后在加上新的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public long[] mostFrequentIDs(int[] nums, int[] freq) {
        long[] ans = new long[nums.length];
        HashMap<Integer,Long> hashMap = new HashMap<>();
        TreeMap<Long,Integer> treeMap = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!hashMap.containsKey(nums[i])){
                hashMap.put(nums[i], (long) freq[i]);
                //如果没有就默认为1，有就加上
                treeMap.put((long) freq[i],treeMap.getOrDefault((long)freq[i],0)+1);
            }
            else {
                long integer = hashMap.get(nums[i]);
                if (treeMap.containsKey(integer)){
                    int temp = treeMap.get(integer);
                    if (temp == 1){
                        //如果本来就只有1了，就移除
                        treeMap.remove(integer);
                    }
                    else {
                        //这里其实可以直接用put
                        treeMap.replace(integer,temp-1);
                    }
                    treeMap.put(integer+freq[i],treeMap.getOrDefault(integer+freq[i],0)+1);
                }
                hashMap.replace(nums[i],integer+freq[i]);
            }
            ans[i] = treeMap.lastKey();
        }
        return ans;
    }
}

引申：前天的每日一题

有一点相似