标签： easy

目标

给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。

示例 1：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

示例 2：

输入：nums = [2,3]
输出：[2,3]

说明：

• 2 <= nums.length <= 2 * 10^4
• nums.length 是偶数
• nums 中一半是偶数
• 0 <= nums[i] <= 1000

进阶：可以不使用额外空间解决问题吗？

思路

数组 nums 长度为偶数，其元素一半为偶数，另一半为奇数。调整数组元素的顺序，使得奇数下标中的元素为奇数，偶数下标的元素为偶数。

使用奇偶两个指针，步长为2，找到不满足条件的元素并交换。

代码

/**
 * @date 2025-02-04 19:04
 */
public class SortArrayByParityII922 {

    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int even = 0, odd = 1;
        while (even < n && odd < n) {
            while (even < n && nums[even] % 2 == 0) {
                even += 2;
            }
            if (even >= n) {
                break;
            }
            while (odd < n && nums[odd] % 2 == 1) {
                odd += 2;
            }
            int tmp = nums[even];
            nums[even] = nums[odd];
            nums[odd] = tmp;
        }
        return nums;
    }

}

性能

目标

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

输入：s = "aba"
输出：true

示例 2：

输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。

示例 3：

输入：s = "abc"
输出：false

说明：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成

思路

判断给定字符串是否是回文，如果不是，能否删除任意一个字符使之变成回文。

当不满足回文条件时，分别考虑删掉其中一个字符，判断剩余子串是否是回文即可。

代码

/**
 * @date 2025-02-03 18:24
 */
public class ValidPalindrome680 {

    public boolean validPalindrome(String s) {
        int n = s.length();
        int i = 0;
        for (; i < n / 2; i++) {
            // 找到第一个不满足回文的字符下标
            if (s.charAt(i) != s.charAt(n - 1 - i)) {
                break;
            }
        }
        if (i == n / 2) {
            return true;
        }
        // 尝试删掉左边/右边字符判断剩余字符是否是回文
        boolean res = true;
        for (int j = i; j < n / 2; j++) {
            // 删掉 n - 1 - i，即 n - 2 - j
            if (s.charAt(j) != s.charAt(n - 2 - j)) {
                res = false;
            }
        }
        if (res) {
            return true;
        }
        // 这里是 j <= n /2，例如 abc，i + 1 指向 b
        for (int j = i + 1; j <= n / 2; j++) {
            // 这里是 n - 1 - i， 即 n - j，相当于删除了 i，但是右指针是不变的
            if (s.charAt(j) != s.charAt(n - j)) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

给定一个字符串 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;
    }

}

性能