标签： easy

目标

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

说明：

• 1 <= s.length <= 10^4
• s 仅由小写英文组成
• 1 <= k <= 10^4

思路

将字符串从左至右划分为若干个长度为 2 * k 的子串，将每个子串的前 k 个字符反转，返回反转后的子串拼接成的字符串（保持子串之间的顺序不变）。

代码

/**
 * @date 2025-01-31 14:45
 */
public class ReverseStr541 {

    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();
        int k2 = 2 * k;
        int n = chars.length;
        for (int i = 0; i < n; i += k2) {
            int end = Math.min(i + k, n) - 1;
            reverse(chars, i, end);
        }
        return new String(chars);
    }

    private void reverse(char[] chars, int i, int end) {
        for (int j = i; j < end; j++) {
            char tmp = chars[j];
            chars[j] = chars[end];
            chars[end--] = tmp;
        }
    }

}

性能

目标

给你两个整数数组 nums1 和 nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

说明：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

进阶：

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小，哪种方法更优？
• 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

思路

求两个数组 nums1 和 nums2 的交集（不考虑元素顺序），比如 a b c b 与 e b d 的交集为 b。

使用哈希表对数组 nums1 的元素值计数，遍历 nums2 获取对应元素在 nums1 中的数量，如果大于0，将元素加入列表，并将数量减一。

如果已经排好序可以直接使用双指针，每次比较移动元素值小的指针。

交集的最大元素不会超过两个数组长度的最小值，因此初始化时可以取长度较小的数组进行计数。

如果 nums2 存储在磁盘上，根据上面的讨论，我们对 nums1 计数，每次从磁盘读取一部分数据进行判断即可。

代码

/**
 * @date 2025-01-30 21:37
 */
public class Intersect350 {

    public int[] intersect_v2(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            intersect_v2(nums2, nums1);
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] res = new int[nums1.length];
        int j = 0;
        int index = 0;
        for (int i = 0; i < nums2.length && j < nums1.length; i++) {
            while (j < nums1.length && nums2[i] > nums1[j]) {
                j++;
            }
            if (j == nums1.length) {
                break;
            }
            if (nums2[i] == nums1[j]) {
                res[index++] = nums1[j];
                j++;
            }
        }

        return Arrays.copyOfRange(res, 0, index);
    }

    public int[] intersect_v1(int[] nums1, int[] nums2) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i : nums1) {
            cnt.merge(i, 1, Integer::sum);
        }
        List<Integer> list = new ArrayList<>();
        for (int i : nums2) {
            int value = cnt.getOrDefault(i, 0) - 1;
            if (value >= 0) {
                list.add(i);
                cnt.put(i, value);
            }
        }
        return list.stream().mapToInt(i -> i).toArray();
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

说明：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= 10^5

思路

判断下标距离小于等于 k 的窗口内是否存在重复元素，窗口内的元素个数为 k + 1。

代码

/**
 * @date 2024-07-04 22:36
 */
public class ContainsNearbyDuplicate219 {

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>(k);
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (!set.add(nums[right])) {
                return true;
            }
            if (right - left == k) {
                set.remove(nums[left++]);
            }
        }
        return false;
    }

}

性能

目标

给你一个字符串 num ，表示一个大整数。如果一个整数满足下述所有条件，则认为该整数是一个 优质整数 ：

• 该整数是 num 的一个长度为 3 的 子字符串 。
• 该整数由唯一一个数字重复 3 次组成。

以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数，则返回一个空字符串 "" 。

注意：

• 子字符串 是字符串中的一个连续字符序列。
• num 或优质整数中可能存在 前导零 。

示例 1：

输入：num = "6777133339"
输出："777"
解释：num 中存在两个优质整数："777" 和 "333" 。
"777" 是最大的那个，所以返回 "777" 。

示例 2：

输入：num = "2300019"
输出："000"
解释："000" 是唯一一个优质整数。

示例 3：

输入：num = "42352338"
输出：""
解释：不存在长度为 3 且仅由一个唯一数字组成的整数。因此，不存在优质整数。

说明：

• 3 <= num.length <= 1000
• num 仅由数字（0 - 9）组成

思路

判断字符串中是否存在 三个连续相同的数字，如果有多个返回数字最大的那个。

可以使用一个变量记录连续相同的字符个数，如果不同就重置 cnt 为 1。

代码

/**
 * @date 2025-01-08 8:48
 */
public class LargestGoodInteger2264 {

    public String largestGoodInteger(String num) {
        char c = 0;
        int n = num.length();
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (num.charAt(i) == num.charAt(i - 1)) {
                cnt++;
            } else {
                cnt = 1;
                continue;
            }
            if (cnt == 3 && c < num.charAt(i)) {
                c = num.charAt(i);
            }
        }
        return c > 0 ? new String(new char[]{c, c, c}) : "";
    }

}

性能

目标

给你一个下标从 0 开始的字符串 s ，该字符串由用户输入。按键变更的定义是：使用与上次使用的按键不同的键。例如 s = "ab" 表示按键变更一次，而 s = "bBBb" 不存在按键变更。

返回用户输入过程中按键变更的次数。

注意：shift 或 caps lock 等修饰键不计入按键变更，也就是说，如果用户先输入字母 'a' 然后输入字母 'A' ，不算作按键变更。

示例 1：

输入：s = "aAbBcC"
输出：2
解释： 
从 s[0] = 'a' 到 s[1] = 'A'，不存在按键变更，因为不计入 caps lock 或 shift 。
从 s[1] = 'A' 到 s[2] = 'b'，按键变更。
从 s[2] = 'b' 到 s[3] = 'B'，不存在按键变更，因为不计入 caps lock 或 shift 。
从 s[3] = 'B' 到 s[4] = 'c'，按键变更。
从 s[4] = 'c' 到 s[5] = 'C'，不存在按键变更，因为不计入 caps lock 或 shift 。

示例 2：

输入：s = "AaAaAaaA"
输出：0
解释： 不存在按键变更，因为这个过程中只按下字母 'a' 和 'A' ，不需要进行按键变更。

说明：

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

思路

已知字符串 s，计算用户输入该字符串时按键的变更次数，不区分大小写。

根据题意比较相邻字符忽略大小写后是否相同，可以使用 |32 将字符都转为小写后比较。

代码

/**
 * @date 2025-01-07 8:46
 */
public class CountKeyChanges3019 {

    /**
     * A 65 010 00001 Z 90  010 11010
     * a 97 011 00001 Z 122 011 11010
     * 31   000 11111
     * 32   001 00000
     * 只有低 5 位不同，因此我们可以 &31 或者 |32
     */
    public int countKeyChanges_v1(String s) {
        int res = 0;
        int n = s.length();
        for (int i = 1; i < n; i++) {
            if ((s.charAt(i) | 32) != (s.charAt(i - 1) | 32)) {
                res++;
            }
        }
        return res;
    }

}

性能