标签： easy

目标

有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流，以 任意 顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。

实现 OrderedStream 类：

• OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
• String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
  • 如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1 。
  • 否则，返回一个空列表。

示例：

输入
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

解释
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc")，返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa")，返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb")，返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee")，返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd")，返回 ["ddddd", "eeeee"]

说明：

• 1 <= n <= 1000
• 1 <= id <= n
• value.length == 5
• value 仅由小写字母组成
• 每次调用 insert 都会使用一个唯一的 id
• 恰好调用 n 次 insert

思路

将编号为 id 的数据放入对应的位置上，pos 从 0 开始，如果 pos 位置上有数据，就输出自身及其后面非空的数据。

代码

/**
 * @date 2025-02-24 8:50
 */
public class OrderedStream1656 {

    static class OrderedStream {

        private final String[] buffer;

        private int pos = 1;

        public OrderedStream(int n) {
            buffer = new String[n + 1];
        }

        public List<String> insert(int idKey, String value) {
            List<String> res = new ArrayList<>();
            if (idKey != pos) {
                buffer[idKey] = value;
                return res;
            }
            buffer[pos] = value;
            while (pos < buffer.length && buffer[pos] != null) {
                res.add(buffer[pos++]);
            }
            return res;
        }
    }

}

性能

目标

给你一个下标从 0 开始的字符串数组 words 。

如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。

• 例如，"abca" 和 "cba" 相似，因为它们都由字符 'a'、'b'、'c' 组成。
• 然而，"abacba" 和 "bcfd" 不相似，因为它们不是相同字符组成的。

请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= words.length - 1 。

示例 1：

输入：words = ["aba","aabb","abcd","bac","aabc"]
输出：2
解释：共有 2 对满足条件：
- i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。 
- i = 3 且 j = 4 ：words[3] 和 words[4] 只由字符 'a'、'b' 和 'c' 。 

示例 2：

输入：words = ["aabb","ab","ba"]
输出：3
解释：共有 3 对满足条件：
- i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。 
- i = 0 且 j = 2 ：words[0] 和 words[2] 只由字符 'a' 和 'b' 组成。 
- i = 1 且 j = 2 ：words[1] 和 words[2] 只由字符 'a' 和 'b' 组成。 

示例 3：

输入：words = ["nba","cba","dba"]
输出：0
解释：不存在满足条件的下标对，返回 0 。

说明：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 仅由小写英文字母组成

思路

找出字符串数组 words 中由相同字母组成的单词对数目。

将构成单词的字母组合使用掩码表示，统计掩码相同的单词个数 n，从中任选 2 个组合的方法有 n * (n - 1) / 2。也可以直接在循环中累加结果，每增加一个 mask 相同的单词，组合数增加 prevCnt，即与前面的单词一一组合。

代码

/**
 * @date 2025-02-22 12:06
 */
public class SimilarPairs2506 {

    public int similarPairs_v1(String[] words) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (String word : words) {
            int mask = 0;
            int length = word.length();
            for (int i = 0; i < length; i++) {
                int offset = word.charAt(i) - 'a';
                mask |= 1 << offset;
            }
            int prevCnt = map.getOrDefault(mask, 0);
            res += prevCnt;
            map.put(mask, prevCnt + 1);
        }
        return res;
    }

    public int similarPairs(String[] words) {
        Map<Integer, Integer> map = new HashMap<>();
        for (String word : words) {
            int mask = 0;
            int length = word.length();
            for (int i = 0; i < length; i++) {
                int offset = word.charAt(i) - 'a';
                mask |= 1 << offset;
            }
            map.merge(mask, 1, Integer::sum);
        }
        return map.values().stream().mapToInt(x -> x * (x - 1) / 2).sum();
    }

}

性能

目标

给你一个 正 整数 n 。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。

返回整数数组 answer ，其中 answer = [even, odd] 。

示例 1：

输入：n = 17
输出：[2,0]
解释：17 的二进制形式是 10001 。 
下标 0 和 下标 4 对应的值为 1 。 
共有 2 个偶数下标，0 个奇数下标。

示例 2：

输入：n = 2
输出：[0,1]
解释：2 的二进制形式是 10 。 
下标 1 对应的值为 1 。 
共有 0 个偶数下标，1 个奇数下标。

说明：

• 1 <= n <= 1000

思路

返回正整数 n 偶数比特位与奇数比特位为 1 的个数。

可以遍历 n 的 bit 位进行统计，也可以使用掩码调用库函数统计。

代码

/**
 * @date 2025-02-20 8:39
 */
public class EvenOddBit2595 {

    public int[] evenOddBit_v2(int n) {
        // 提取偶数位 0101
        int even = n & 0x55555555;
        // 提取奇数位 1010
        int odd = n & 0xAAAAAAAA;
        return new int[]{Integer.bitCount(even), Integer.bitCount(odd)};
    }

    public int[] evenOddBit_v1(int n) {
        int even = 0;
        int odd = 0;
        while (n > 0) {
            even += n & 1;
            n >>= 1;
            odd += n & 1;
            n >>= 1;
        }
        return new int[]{even, odd};
    }

}

性能

目标

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

示例：

输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6

说明：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

思路

有一个非递减有序整数数组，数组中恰好有一个整数出现次数大于元素总数的 25%，返回这个整数。

检查长度为 n / 4 + 1 的窗口首尾元素是否相等即可。

代码

/**
 * @date 2025-02-17 8:41
 */
public class FindSpecialInteger1287 {

    public int findSpecialInteger_v1(int[] arr) {
        int n = arr.length;
        int left = 0, right = n / 4;
        while (right < n) {
            if (arr[right] == arr[left]) {
                return arr[left];
            }
            left++;
            right++;
        }
        return -1;
    }

}

性能

目标

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

示例 1：

输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]
解释：
- 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
- 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
- 下标 5 的元素 --> 右侧没有其他元素，替换为 -1

示例 2：

输入：arr = [400]
输出：[-1]
解释：下标 0 的元素右侧没有其他元素。

说明：

• 1 <= arr.length <= 10^4
• 1 <= arr[i] <= 10^5

思路

将数组中的元素替换为其后面元素的最大值。

最大值不算当前元素，因此在将后面元素最大值赋值给当前元素时会丢失当前元素，导致前面元素的最大值丢失。而如果先将当前元素与后续元素最大值进行更新，最大值就就包含了当前元素。因此需要临时变量保存当前元素值，再用临时变量更新最大值。

代码

/**
 * @date 2025-02-16 17:28
 */
public class ReplaceElements1299 {

    public int[] replaceElements(int[] arr) {
        int n = arr.length;
        int max = -1;
        for (int i = n - 1; i >= 0; i--) {
            int tmp = arr[i];
            arr[i] = max;
            max = Math.max(tmp, max);
        }
        return arr;
    }
}

性能

目标

给定一个非负整数数组 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;
    }

}

性能