标签： medium

目标

给你一个由正整数组成的数组 nums 和一个 正 整数 k 。

如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

示例 1：

输入：nums = [2,4,6], k = 2
输出：4
解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。

示例 2：

输入：nums = [1], k = 1
输出：1
解释：数组 nums 中的美丽数组有：[1] 。
可以证明数组 [1] 中只存在 1 个美丽子集。

说明：

• 1 <= nums.length <= 18
• 1 <= nums[i], k <= 1000

思路

返回数组的美丽子序列个数，美丽指子序列中任意两个元素的差的绝对值不等于 k。

由于数组长度不大，可以回溯枚举子序列，并针对每一子序列，两两比较，判断差的绝对值是否等于 k。

更好的处理方法是使用哈希表记录元素的出现次数，回溯枚举子序列时直接判断当前元素加减 k 的绝对值是否存在于哈希表中。

代码

/**
 * @date 2025-03-07 0:09
 */
public class BeautifulSubsets2597 {

    public int beautifulSubsets(int[] nums, int k) {
        return dfs(0, new ArrayList<>(), nums, k);
    }

    public int dfs(int index, List<Integer> path, int[] nums, int k) {
        if (index == nums.length) {
            return path.size() > 0 ? 1 : 0;
        }
        int res = 0;
        res += dfs(index + 1, path, nums, k);
        for (Integer num : path) {
            if (Math.abs(num - nums[index]) == k) {
                return res;
            }
        }
        path.add(nums[index]);
        res += dfs(index + 1, path, nums, k);
        path.remove(path.size() - 1);
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：

• 选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
• 选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
• 将 nums[i] 和 nums[j] 都减去 2^k 。

如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。

请你返回数组 nums 中 美丽子数组 的数目。

子数组是一个数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [4,3,1,2,4]
输出：2
解释：nums 中有 2 个美丽子数组：[3,1,2] 和 [4,3,1,2,4] 。
- 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：
  - 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [1, 1, 0] 。
  - 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 0, 0] 。
- 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
  - 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 22 ，子数组变成 [0, 3, 1, 2, 0] 。
  - 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 2, 0, 2, 0] 。
  - 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [0, 0, 0, 0, 0] 。

示例 2：

输入：nums = [1,10,4]
输出：0
解释：nums 中没有任何美丽子数组。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^6

思路

有一个下标从 0 开始的数组 nums，每次操作可以任选两个不同下标的元素，如果它们在二进制下的第 k 位是 1，那么将这两个元素减去 2^k，即把这两个元素的第 k 位置 0。如果对 nums 的子数组执行任意次操作后可以将子数组所有元素变为 0，称该子数组为 美丽子数组。返回数组 nums 的美丽子数组数目。

通过分析可以知道，累加美丽子数组中所有元素在二进制下每个bit位上 1 的个数，可以发现每个位置上 1 的个数都是偶数。可以通过异或运算来判断是否是美丽子数组。

代码

/**
 * @date 2025-03-06 8:37
 */
public class BeautifulSubarrays2588 {

    public long beautifulSubarrays(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        Map<Integer, List<Integer>> map = new HashMap<>();
        map.computeIfAbsent(prefix[0], x -> new ArrayList<>()).add(0);
        for (int i = 1; i <= n; i++) {
            prefix[i] = nums[i - 1] ^ prefix[i - 1];
            map.computeIfAbsent(prefix[i], x -> new ArrayList<>()).add(i);
        }
        long res = 0;
        for (List<Integer> value : map.values()) {
            int size = value.size();
            res += (size - 1L) * size / 2;
        }
        return res;
    }

}

性能

目标

给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。

请你返回结果字符串。如果无法做到，则返回一个 空串 。

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，"abcc” 字典序比 "abcd" 小，因为不同的第一个位置是在第四个字符，显然 'c' 比 'd' 小。

示例 1：

输入：palindrome = "abccba"
输出："aaccba"
解释：存在多种方法可以使 "abccba" 不是回文，例如 "zbccba", "aaccba", 和 "abacba" 。
在所有方法中，"aaccba" 的字典序最小。

示例 2：

输入：palindrome = "a"
输出：""
解释：不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。

说明：

• 1 <= palindrome.length <= 1000
• palindrome 只包含小写英文字母。

思路

有一个回文字符串，可以修改其中一个字符使其不是回文，求修改后字典序最小的字符串。如果无法破会回文串，返回空串。

根据题意，字符串长度为 1 直接返回空串。

要使字典序最小，只需使字符串最左边的字符为 a，但是需考虑能否破坏回文串。于是就有了贪心解法，从左到右将对应位置上的字符修改为 a，判断是否是回文，不是回文直接返回。如果均为 a，将最后一个字符替换为 b。

注意不要改中间的字符，它不会破坏回文串。

代码

/**
 * @date 2025-03-05 0:06
 */
public class BreakPalindrome1328 {

    public String breakPalindrome(String palindrome) {
        int n = palindrome.length();
        if (n == 1) {
            return "";
        }
        int l = 0, r = n - 1;
        char[] chars = palindrome.toCharArray();
        while (l < r) {
            if (chars[r] != 'a') {
                chars[l] = 'a';
                return new String(chars);
            }
            l++;
            r--;
        }
        chars[n - 1] = 'b';
        return new String(chars);
    }

}

性能

目标

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

说明：

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

思路

返回将字符串划分为回文子串的所有可能方案。

定义 dp[i] 表示将前 i + 1 个字符划分为回文子串的所有可能方案。dp[i] 可以取 dp[i - 1] 每种方案的最后一或两个回文，判断能否与当前字符合并成新的回文。

代码

/**
 * @date 2025-03-01 20:16
 */
public class Partition131 {

    public List<List<String>> partition(String s) {
        int n = s.length();
        List<List<String>>[] dp = new List[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new ArrayList<>();
        }
        char[] chars = s.toCharArray();
        dp[0].add(new ArrayList<>());
        dp[0].get(0).add((String.valueOf(chars[0])));
        for (int i = 1; i < n; i++) {
            dp[i] = new ArrayList<>();
            for (List<String> list : dp[i - 1]) {
                // 首先将单个字符加入
                List<String> tmp = new ArrayList<>(list);
                tmp.add(String.valueOf(chars[i]));
                dp[i].add(tmp);
                String cur = String.valueOf(chars[i]);
                // 判断能与最后一个回文合并成新的回文
                if (list.get(list.size() - 1).equals(cur)) {
                    tmp = new ArrayList<>(list.subList(0, list.size() - 1));
                    tmp.add(list.get(list.size() - 1) + cur);
                    dp[i].add(tmp);
                }
                // 判断能否与后两个回文合并成新的回文
                if (list.size() > 1 && list.get(list.size() - 2).equals(cur)) {
                    tmp = new ArrayList<>(list.subList(0, list.size() - 2));
                    tmp.add(list.get(list.size() - 2) + list.get(list.size() - 1) + cur);
                    dp[i].add(tmp);
                }
            }
        }
        return dp[n - 1];
    }

}

性能

时间复杂度 O(n * 2^n)，假设每个字符之间都有一个逗号，考虑选或不选共有 2^(n - 1) 种划分。前 i + 1 个 字符有 2^i 种划分， 等比数列求和得到 2^n - 1。

目标

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

• BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
• void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。
• string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
• string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。

示例：

输入：
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
输出：
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

解释：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // 你原本在浏览 "leetcode.com" 。访问 "google.com"
browserHistory.visit("facebook.com");     // 你原本在浏览 "google.com" 。访问 "facebook.com"
browserHistory.visit("youtube.com");      // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
browserHistory.back(1);                   // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1);                   // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1);                // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com");     // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
browserHistory.forward(2);                // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
browserHistory.back(2);                   // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7);                   // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"

说明：

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage 和 url 都只包含 '.' 或者小写英文字母。
• 最多调用 5000 次 visit， back 和 forward 函数。

思路

设计一个浏览器历史记录管理器，记录在同一个标签页的浏览历史，允许前进/后退 steps 步（不能超出浏览记录的范围）。如果打开新页面，当前页面记录会覆盖前进的记录。

使用栈模拟，记录 cur 与 tail 两个指针，前进取 Math.min(tail, cur + steps)，后退取 Math.max(0, cur - steps)，访问新页面 ++cur; tail = cur;。

代码

/**
 * @date 2025-02-26 8:48
 */
class BrowserHistory {

    String[] history = new String[5000];
    int tail = 0;
    int cur = 0;

    public BrowserHistory(String homepage) {
        history[0] = homepage;
    }

    public void visit(String url) {
        history[++cur] = url;
        tail = cur;
    }

    public String back(int steps) {
        cur = Math.max(0, cur - steps);
        return history[cur];
    }

    public String forward(int steps) {
        cur = Math.min(tail, cur + steps);
        return history[cur];
    }
}

性能

目标

给定 m 个数组，每个数组都已经按照升序排好序了。

现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。

返回最大距离。

示例 1：

输入：[[1,2,3],[4,5],[1,2,3]]
输出：4
解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

示例 2：

输入：arrays = [[1],[1]]
输出：0

说明：

• m == arrays.length
• 2 <= m <= 10^5
• 1 <= arrays[i].length <= 500
• -10^4 <= arrays[i][j] <= 10^4
• arrays[i] 以 升序 排序。
• 所有数组中最多有 10^5 个整数。

思路

有一个二维数组，其中的每个数组都按升序排列。任选其中两个数组，从每个数组中选两个元素，求这两个元素距离的最大值，距离指差的绝对值。

显然应该选取最大值与最小值的差，但题目限制是从两个数组中取。我们可以求得最大与次最大、最小与次最小，同时记录所属数组。

如果有多个最值相同，从哪个数组中取有影响吗？由于我们从每个组只取首尾两个元素，最值与次最值一定来自不同的组，所以最值的比较可以使用 >= 和 <=。如果最值来自相同的组，那么只需比较最大值与次最小值，次最大值与最小值。

网友题解使用变量记录前面的最大与最小值，那么最大距离为 Math.max(res, Math.max(curMax - preMin, preMax - curMin))。

代码

/**
 * @date 2025-02-19 8:57
 */
public class MaxDistance624 {

    public int maxDistance_v1(List<List<Integer>> arrays) {
        int res = 0;
        int preMax = Integer.MIN_VALUE / 2;
        int preMin = Integer.MAX_VALUE / 2;
        for (List<Integer> array : arrays) {
            int n = array.size();
            Integer curMax = array.get(n - 1);
            Integer curMin = array.get(0);
            res = Math.max(res, Math.max(curMax - preMin, preMax - curMin));
            preMax = Math.max(preMax, curMax);
            preMin = Math.min(preMin, curMin);
        }
        return res;
    }

    public int maxDistance(List<List<Integer>> arrays) {
        int[] max = new int[]{Integer.MIN_VALUE, -1};
        int secondMax = Integer.MIN_VALUE;
        int[] min = new int[]{Integer.MAX_VALUE, -1};
        int secondMin = Integer.MAX_VALUE;
        for (int i = 0; i < arrays.size(); i++) {
            List<Integer> array = arrays.get(i);
            int n = array.size();
            if (min[0] >= array.get(0)) {
                secondMin = min[0];
                min[0] = array.get(0);
                min[1] = i;
            } else if (secondMin > array.get(0)) {
                secondMin = array.get(0);
            }
            if (max[0] <= array.get(n - 1)) {
                secondMax = max[0];
                max[0] = array.get(n - 1);
                max[1] = i;
            } else if (secondMax < array.get(n - 1)) {
                secondMax = array.get(n - 1);
            }
        }
        if (max[1] != min[1]) {
            return max[0] - min[0];
        } else {
            return Math.max(max[0] - secondMin, secondMax - min[0]);
        }
    }

}

性能

目标

请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。

子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。

请你实现 RangeFreqQuery 类：

• RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
• int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。

一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。

示例 1：

输入：
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
输出：
[null, 1, 2]

解释：
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。

说明：

• 1 <= arr.length <= 10^5
• 1 <= arr[i], value <= 10^4
• 0 <= left <= right < arr.length
• 调用 query 不超过 10^5 次。

思路

设计一个数据结构，能够求出给定元素在子数组中的出现次数。

可以使用哈希表保存每个元素的下标列表（从小到大），查询时根据 value 获取下标列表，二分查找左边界的下界（第一个大于等于左边界的下标）和右边界的上界（最后一个小于等于右边界的下标）。注意二分查找的范围是 0 ~ list.size()，但是比较的则是原数组中的下标。构建时间复杂度为 O(n)，查询时间复杂度为 O(logn)。

代码

/**
 * @date 2025-02-18 15:57
 */
public  class RangeFreqQuery {

    public Map<Integer, List<Integer>> valueIndexMap = new HashMap<>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            valueIndexMap.putIfAbsent(arr[i], new ArrayList<>());
            valueIndexMap.get(arr[i]).add(i);
        }
    }

    public int query(int left, int right, int value) {
        List<Integer> list = valueIndexMap.get(value);
        if (list == null) {
            return 0;
        }
        return getUpperBound(right, list) - getLowerBound(left, list) + 1;
    }

    public int getUpperBound(int target, List<Integer> list) {
        int l = 0, r = list.size() - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (list.get(m) > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

    public int getLowerBound(int target, List<Integer> list) {
        int l = 0, r = list.size() - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (list.get(m) < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

}

性能

目标

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。

• 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
• 将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。

返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

示例 1：

输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。

示例 2：

输入：grid = [[-1]]
输出：[-1]
解释：球被卡在箱子左侧边上。

示例 3：

输入：grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
输出：[0,1,2,3,4,-1]

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j] 为 1 或 -1

思路

矩阵 m x n 上方有 n 个球，矩阵元素值为 1 表示格子有 左上右下 的斜线挡板，值为 -1 表示有 左下右上 的斜线挡板。返回 n 个球下落的出口下标，如果被卡在箱子中用 -1 表示。

直接根据题意模拟即可，如果当前格子元素值为 1，判断其右侧格子（如果有的话），如果为 -1 则卡住，否则下落到 (i + 1, j + 1)， 当行下标等于 m - 1 时，判断出口记录列下标即可。

代码

/**
 * @date 2025-02-15 20:33
 */
public class FindBall1706 {

    public int[] findBall_v2(int[][] grid) {
        int n = grid[0].length;
        int[] res = new int[n];
        for (int j = 0; j < n; j++) {
            res[j] = fall(grid, j);
        }
        return res;
    }

    public int fall(int[][] grid, int pos){
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            int offset = grid[i][pos];
            pos += offset;
            if (pos == n || pos < 0 || grid[i][pos] != offset) {
                pos = -1;
                break;
            }
        }
        return pos;
    }

    public int[] findBall(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] res = new int[n];
        for (int j = 0; j < n; j++) {
            int pos = j;
            for (int i = 0; i < m; i++) {
                if (grid[i][pos] == 1 && (pos == n - 1 || grid[i][pos + 1] == -1)) {
                    pos = -1;
                    break;
                } else if (grid[i][pos] == -1 && (pos == 0 || grid[i][pos - 1] == 1)) {
                    pos = -1;
                    break;
                } else {
                    pos += grid[i][pos];
                }
            }
            res[j] = pos;
        }
        return res;
    }

}

性能