标签： easy

目标

给你一个下标从 0 开始的二维整数数组 nums 。

返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数，返回 0 。

注意：

• 如果某个整数大于 1 ，且不存在除 1 和自身之外的正整数因子，则认为该整数是一个质数。
• 如果存在整数 i ，使得 nums[i][i] = val 或者 nums[i][nums.length - i - 1]= val ，则认为整数 val 位于 nums 的一条对角线上。

在上图中，一条对角线是 [1,5,9] ，而另一条对角线是 [3,5,7] 。

示例 1：

输入：nums = [[1,2,3],[5,6,7],[9,10,11]]
输出：11
解释：数字 1、3、6、9 和 11 是所有 "位于至少一条对角线上" 的数字。由于 11 是最大的质数，故返回 11 。

示例 2：

输入：nums = [[1,2,3],[5,17,7],[9,11,10]]
输出：17
解释：数字 1、3、9、10 和 17 是所有满足"位于至少一条对角线上"的数字。由于 17 是最大的质数，故返回 17 。

说明：

• 1 <= nums.length <= 300
• nums.length == numsi.length
• 1 <= nums[i][j] <= 4 * 10^6

思路

求 n x n 矩阵对角线上的最大质数，对角线指 (i, i) 与 (i, n - 1 - i) 上的元素。

由于本题只需判断对角线上的元素值是否是质数，总个数不超过 2n 即 600 个。可以直接枚举元素，判断元素值是否存在 1 和它本身以外的因子。

代码

/**
 * @date 2025-03-18 9:06
 */
public class DiagonalPrime2614 {

    public int diagonalPrime(int[][] nums) {
        int n = nums.length;
        int m = nums[0].length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i][i] > res && isPrime(nums[i][i])) {
                res = nums[i][i];
            }
            if (nums[i][m - 1 - i] > res && isPrime(nums[i][m - 1 - i])) {
                res = nums[i][m - 1 - i];
            }
        }
        return res;
    }

    public boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        if (num <= 3) {
            return true;
        }
        if (num % 2 == 0 || num % 3 == 0) {
            return false;
        }
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

有 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;
    }
}

性能