标签： easy

目标

给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces 。

数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值 之前 。

• 例如，s = "EnjoyYourCoffee" 且 spaces = [5, 9] ，那么我们需要在 'Y' 和 'C' 之前添加空格，这两个字符分别位于下标 5 和下标 9 。因此，最终得到 "Enjoy Your Coffee" 。

请你添加空格，并返回修改后的字符串。

示例 1：

输入：s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
输出："Leetcode Helps Me Learn"
解释：
下标 8、13 和 15 对应 "LeetcodeHelpsMeLearn" 中加粗斜体字符。
接着在这些字符前添加空格。

示例 2：

输入：s = "icodeinpython", spaces = [1,5,7,9]
输出："i code in py thon"
解释：
下标 1、5、7 和 9 对应 "icodeinpython" 中加粗斜体字符。
接着在这些字符前添加空格。

示例 3：

输入：s = "spacing", spaces = [0,1,2,3,4,5,6]
输出：" s p a c i n g"
解释：
字符串的第一个字符前可以添加空格。

说明：

• 1 <= s.length <= 3 * 10^5
• s 仅由大小写英文字母组成
• 1 <= spaces.length <= 3 * 10^5
• 0 <= spaces[i] <= s.length - 1
• spaces 中的所有值 严格递增

思路

在字符串的指定位置添加空格。

代码

/**
 * @date 2025-03-30 0:08
 */
public class AddSpaces2109 {

    public String addSpaces(String s, int[] spaces) {
        StringBuilder sb = new StringBuilder(s.length() + spaces.length);
        int start = 0;
        for (int i : spaces) {
            sb.append(s, start, i).append(' ');
            start = i;
        }
        sb.append(s.substring(start));
        return sb.toString();
    }
}

性能

目标

给你一个下标从 0 开始的字符串 s ，重复执行下述操作 任意 次：

• 在字符串中选出一个下标 i ，并使 c 为字符串下标 i 处的字符。并在 i 左侧（如果有）和 右侧（如果有）各 删除 一个距离 i 最近 的字符 c 。

请你通过执行上述操作任意次，使 s 的长度 最小化 。

返回一个表示 最小化 字符串的长度的整数。

示例 1：

输入：s = "aaabc"
输出：3
解释：在这个示例中，s 等于 "aaabc" 。我们可以选择位于下标 1 处的字符 'a' 开始。接着删除下标 1 左侧最近的那个 'a'（位于下标 0）以及下标 1 右侧最近的那个 'a'（位于下标 2）。执行操作后，字符串变为 "abc" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 3 。

示例 2：

输入：s = "cbbd"
输出：3
解释：我们可以选择位于下标 1 处的字符 'b' 开始。下标 1 左侧不存在字符 'b' ，但右侧存在一个字符 'b'（位于下标 2），所以会删除位于下标 2 的字符 'b' 。执行操作后，字符串变为 "cbd" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 3 。

示例 3：

输入：s = "dddaaa"
输出：2
解释：我们可以选择位于下标 1 处的字符 'd' 开始。接着删除下标 1 左侧最近的那个 'd'（位于下标 0）以及下标 1 右侧最近的那个 'd'（位于下标 2）。执行操作后，字符串变为 "daaa" 。继续对新字符串执行操作，可以选择位于下标 2 的字符 'a' 。接着删除下标 2 左侧最近的那个 'a'（位于下标 1）以及下标 2 右侧最近的那个 'a'（位于下标 3）。执行操作后，字符串变为 "da" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 2 。

说明：

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

思路

每次操作可以从字符串 s 中任选一个字符 c，同时删除其左侧与右侧距离最近的相同字符。求执行操作任意次后字符串的最小长度。

由于选中的字符不会被删除，本质是返回字符串中不同字符的个数。

代码

/**
 * @date 2025-03-28 0:20
 */
public class MinimizedStringLength2716 {

    /**
     * 位运算，将出现过的字符保存到 mask 中
     */
    public int minimizedStringLength_v1(String s) {
        int n = s.length();
        int mask = 0;
        for (int i = 0; i < n; i++) {
            mask |= 1 << (s.charAt(i) - 'a');
        }
        return Integer.bitCount(mask);
    }

    public int minimizedStringLength(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(s.charAt(i));
        }
        return set.size();
    }
}

性能

目标

给你一个下标从 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();
    }

}

性能