第 390 场周赛记录-快手

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

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

示例 1：

输入： s = "bcbbbcba"

输出： 4

解释：

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

示例 2：

输入： s = "aaaa"

输出： 2

解释：

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

提示：

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

✏️ 题解：

求连续子字符串，且需要遍历，用滑动窗口解决。

class Solution {
    public int maximumLengthSubstring(String s) {
        // 滑动窗口 + 哈希（小写英文字母可以用数组记录数字
        // 每个字符最多出现两次:则子字符串的长度最小都为 2
        if(s.length() == 2)return 2;
        int len = 0;
        int[] letter_cnt = new int[26];
        int i = 0;
        int j = 1;
        // j - i >= 1恒成立
        letter_cnt[s.charAt(i)-'a']++;
        // letter_cnt[s[j]-'a']++;
        while(j < s.length()){
            if(letter_cnt[s.charAt(j)-'a'] == 2){
                // 字符串中重复字符出现次数超过 2
                while(s.charAt(i) != s.charAt(j)){
                    letter_cnt[s.charAt(i) - 'a']--;
                    i++;
                }
                letter_cnt[s.charAt(i) - 'a']--;
                i++;
            }else{
                letter_cnt[s.charAt(j)-'a']++;
                len = Math.max(j+1-i,len);
                j++;
            }
            
        }
        return len;
    }
}

2. 执行操作使数据元素之和大于等于 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

✏️ 题解：

这道题采用贪心的思路，要先加后减，通过找规律发现开根的方式可以获得最小的操作次数。（a 次加操作、 b 次复制操作和 a 次复制操作、 b 次加操作是一样的，因为是求和）。

class Solution {
    public int minOperations(int k) {
        // 先加后减
        if(k == 1)return 0;
        
        int e = (int)Math.sqrt(k);// 加操作
        int q = (int)Math.ceil((k*1.0)/e); // 复制操作
        
        return e+q-2;
    }
}