月度归档： 2025 年 3 月

目标

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

说明：

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

思路

有一个整数数组 nums，最多可以对它执行 k 次操作，每次操作可以任选一个数将其左移 1 位。求操作后数组所有元素的最大或值。

操作集中到同一个数上可以将最高有效位移到最高，少一次操作最高位就低一位。问题的关键在于，如果所有数字都有相同的最高有效位，移哪个是不确定的。

这时就需要枚举操作数了，每选择一个操作数就需要重新计算其余元素的或值。由于或运算没有逆运算，我们无法撤销已经或进去的值。

直接的想法是计算或前缀、后缀，枚举所有元素，将其左移 k 次，然后与前后缀进行或运算，取最大值。

网友提供了另一种基于位运算的解法，计算全体元素的或值，同时计算所有 bit 位上存在重复 1 的位置，通过异或运算将当前元素对或值的贡献抵消，然后补上重复位置上的 1。

代码

/**
 * @date 2025-03-21 0:08
 */
public class MaximumOr2680 {

    public long maximumOr_v1(int[] nums, int k) {
        int n = nums.length;
        int or = 0;
        int multiBits = 0;
        for (int i = 0; i < n; i++) {
            multiBits = multiBits | or & nums[i];
            or = or | nums[i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, or ^ nums[i] | multiBits | ((long) nums[i] << k));
        }
        return res;
    }

    public long maximumOr(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] | nums[i - 1];
            suffix[n - i] = suffix[n - i + 1] | nums[n - i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, prefix[i] | suffix[i + 1] | ((long) nums[i] << k));
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：

• 二维数组应该 只 包含数组 nums 中的元素。
• 二维数组中的每一行都包含 不同 的整数。
• 二维数组的行数应尽可能 少 。

返回结果数组。如果存在多种答案，则返回其中任何一种。

请注意，二维数组的每一行上可以存在不同数量的元素。

示例 1：

输入：nums = [1,3,4,1,2,3,1]
输出：[[1,3,4,2],[1,3],[1]]
解释：根据题目要求可以创建包含以下几行元素的二维数组：
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
可以证明无法创建少于三行且符合题目要求的二维数组。

示例 2：

输入：nums = [1,2,3,4]
输出：[[4,3,2,1]]
解释：nums 中的所有元素都不同，所以我们可以将其全部保存在二维数组中的第一行。

说明：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= nums.length

思路

将数组转化为二维数组，要求每一行元素没有重复，并且行数尽可能地少。

使用哈希表对相同元素计数，将所有 key 放入一行并将所有 key 的计数减一，如果计数减为 0 则删除 key，直到哈希表为空，时间复杂度为 O(n)。

也可以将哈希表改为数组相当于计数排序。

代码

/**
 * @date 2025-03-19 0:21
 */
public class FindMatrix2610 {

    public List<List<Integer>> findMatrix(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        List<List<Integer>> res = new ArrayList<>();
        while (!map.isEmpty()) {
            res.add(new ArrayList<>());
            List<Integer> list = res.get(res.size() - 1);
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, Integer> entry = iterator.next();
                list.add(entry.getKey());
                entry.setValue(entry.getValue() - 1);
                if (entry.getValue() == 0) {
                    iterator.remove();
                }
            }
        }
        return res;
    }

}

性能

目标

给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串 ：

• 字符串是一个空字符串，或者
• 字符串可以记作 AB ，其中 A 和 B 都是 平衡字符串 ，或者
• 字符串可以写成 [C] ，其中 C 是一个 平衡字符串 。

你可以交换 任意 两个下标所对应的括号 任意 次数。

返回使 s 变成 平衡字符串 所需要的 最小 交换次数。

示例 1：

输入：s = "][]["
输出：1
解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
最终字符串变成 "[[]]" 。

示例 2：

输入：s = "]]][[["
输出：2
解释：执行下述操作可以使字符串变成平衡字符串：
- 交换下标 0 和下标 4 对应的括号，s = "[]][][" 。
- 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
最终字符串变成 "[[][]]" 。

示例 3：

输入：s = "[]"
输出：0
解释：这个字符串已经是平衡字符串。

说明：

• n == s.length
• 2 <= n <= 10^6
• n 为偶数
• s[i] 为'[' 或 ']'
• 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2

思路

有一个长度为偶数 n 的字符串，有 n / 2 个 [ 和 ]。定义括号能够匹配的字符串是平衡字符串。每一次操作可以交换任意两个下标对应的括号，求将字符串变平衡的最少操作次数。

[[]] 和 [][] 都是平衡字符串，如何确定该与哪个括号交换才能使操作次数最小？对于 ]][[ 和 ][][，第一个与最后一个交换之后变为平衡字符串 [][] 和 [[]]。而如果选择与倒数第二个 [ 交换，会变成 []][，需要再交换一次才能变为平衡字符串。

平衡字符串有这样的性质：其前缀中 [ 的个数总是大于等于 ] 的个数。如果发现 ] 的个数超过 [，那么必须要进行交换。最好将它交换到最后，因为这样可以减少它在前面前缀中对 ] 的贡献，将交换操作尽可能地延后，减小必须进行交换的次数。

也可以先将平衡的括号消掉，剩下的必然是 ]]]......[[[ 的形式。交换一次最多可以抵消 4 个，最少抵消 2 个，即 (stack.size() + 2) / 4。

代码

/**
 * @date 2025-03-17 16:32
 */
public class MinSwaps1963 {

    public int minSwaps_v1(String s) {
        int n = s.length();
        int left = 0, right = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '[') {
                left++;
            } else if (c == ']' && left > 0) {
                left--;
            } else {
                right++;
            }
        }
        return (left + right + 2) / 4;
    }

    public int minSwaps(String s) {
        int n = s.length();
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return (stack.size() + 2) / 4;
    }

}

性能

目标

给你一个字符串 word 和一个 非负 整数 k。

返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。

示例 1：

输入：word = "aeioqq", k = 1
输出：0
解释：
不存在包含所有元音字母的子字符串。

示例 2：

输入：word = "aeiou", k = 0
输出：1
解释：
唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。

示例 3：

输入：word = "ieaouqqieaouqq", k = 1
输出：3
解释：
包含所有元音字母并且恰好含有一个辅音字母的子字符串有：
word[0..5]，即 "ieaouq"。
word[6..11]，即 "qieaou"。
word[7..12]，即 "ieaouq"。

说明：

• 5 <= word.length <= 2 * 10^5
• word 仅由小写英文字母组成。
• 0 <= k <= word.length - 5

思路

求给定字符串 word 的子字符串中至少包含 5 个元音且恰好包含 k 个辅音的子字符串个数。

与 3305.元音辅音字符串计数I 相比，字符串长度范围变成了 2 * 10^5。

恰好型滑动窗口，区间 [left, right] 满足条件不代表 [left, right + 1] 满足条件，可能辅音数量超过了 k，这样就不能累加前面的起点数量，需要重新遍历起点排除一个辅音，退化成暴力解法。

题解提到 恰好 k 个辅音字母 = 至少 k 个辅音字母 - 至少 k + 1 个辅音字母，这样就可以使用两个滑动窗口来求解。

代码

/**
 * @date 2025-03-13 17:03
 */
public class CountOfSubstrings3306 {

    public long countOfSubstrings(String word, int k) {
        return slidingWindow(word, k) - slidingWindow(word, k + 1);
    }

    public long slidingWindow(String word, int k) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
        Map<Character, Integer> map = new HashMap<>();
        int n = word.length();
        int consonantCnt = 0;
        long res = 0;
        int left = 0;
        for (int right = 0; right < n; right++) {
            char c = word.charAt(right);
            if (vowels.contains(c)) {
                Integer cnt = map.getOrDefault(c, 0);
                map.put(c, cnt + 1);
            } else {
                consonantCnt++;
            }
            while (left <= right && consonantCnt >= k && map.size() == 5) {
                c = word.charAt(left++);
                if (vowels.contains(c)) {
                    map.merge(c, -1, Integer::sum);
                    if (map.get(c) == 0) {
                        map.remove(c);
                    }
                } else {
                    consonantCnt--;
                }

            }
            res += left;
        }
        return res;
    }
}

性能

目标

给你一个字符串 word 和一个 非负 整数 k。

返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。

示例 1：

输入：word = "aeioqq", k = 1
输出：0
解释：
不存在包含所有元音字母的子字符串。

示例 2：

输入：word = "aeiou", k = 0
输出：1
解释：
唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。

示例 3：

输入：word = "ieaouqqieaouqq", k = 1
输出：3
解释：
包含所有元音字母并且恰好含有一个辅音字母的子字符串有：
word[0..5]，即 "ieaouq"。
word[6..11]，即 "qieaou"。
word[7..12]，即 "ieaouq"。

说明：

• 5 <= word.length <= 250
• word 仅由小写英文字母组成。
• 0 <= k <= word.length - 5

思路

求给定字符串 word 的子字符串中至少包含 5 个元音且恰好包含 k 个辅音的子字符串个数。

暴力枚举子数组。

代码

/**
 * @date 2025-03-12 8:42
 */
public class CountOfSubstrings3305 {

    public int countOfSubstrings(String word, int k) {
        int n = word.length();
        Set<Character> vowel = new HashSet<>();
        Collections.addAll(vowel, 'a', 'e', 'i', 'o', 'u');
        Map<Character, Integer> map = new HashMap<>();
        int consonantCnt = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = word.charAt(j);
                if (vowel.contains(c)) {
                    Integer cnt = map.getOrDefault(c, 0);
                    map.put(c, cnt + 1);
                } else {
                    consonantCnt++;
                }
                if (consonantCnt == k && map.size() == 5) {
                    res++;
                } else if (consonantCnt > k) {
                    break;
                }
            }
            map.clear();
            consonantCnt = 0;
        }
        return res;
    }

}

性能