Java算法语法学习 美丽子集的数目 - 力扣 Map接口

题目

2597. 美丽子集的数目 - 力扣（LeetCode）

给你一个由正整数组成的数组 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

解题思路

动态规划

1. 把数组按照模 k 的结果，分成k组
2. 从第一组选一些数，从第二组选一些数。第一组中的数字 x 和第二组中的数字 y，二者相差一定不等于 k（不同余）。
3. 只需考虑每组内选数字的方案数，根据乘法原理把各个组的方案数相乘，即为答案
4. 动态规划

设 a 的长度为 m。考虑最大的数 a[m−1] 选或不选：

• 选 a[m−1]及子问题 设 c 为 a[m−1] 的出现次数，由于大小为 c 的集合有 $2^c-1$ 个非空子集，所以选至少一个 a[m−1] 的方案数为 $2^c-1$。
• 如果 a[m−1] − a[m−2] = k 不选， 则变成 a[m - 2] 的子问题

题解

灵神代码
来源：力扣（LeetCode）

class Solution {public int beautifulSubsets(int[] nums, int k) {// 使用HashMap存储每个余数对应的TreeMap，TreeMap按键排序Map<Integer, TreeMap<Integer, Integer>> cnts = new HashMap<>();// 统计每个数字模k的结果，并记录其出现次数for (int x : nums) {cnts.computeIfAbsent(x % k, i -> new TreeMap<>()).merge(x, 1, Integer::sum);}// 初始化答案为1，表示空集int ans = 1;// 遍历每个余数对应的TreeMapfor (TreeMap<Integer, Integer> cnt : cnts.values()) {int m = cnt.size(); // 当前TreeMap中元素的数量int[] f = new int[m + 1]; // 动态规划数组，f[i]表示前i个元素的美丽子集数量f[0] = 1; // 空集是一个美丽子集int i = 1; // 当前处理的索引int pre = 0; // 上一个处理的键值// 遍历当前TreeMap中的每个键值对for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {int x = e.getKey(); // 当前键值int c = e.getValue(); // 当前键值的出现次数// 如果当前键值与上一个键值相差k，则需要考虑不能同时选择的情况if (i > 1 && x - pre == k) {f[i] = f[i - 1] + f[i - 2] * ((1 << c) - 1);} else {f[i] = f[i - 1] << c;}pre = x; // 更新上一个键值i++; // 更新当前索引}// 将当前TreeMap的结果乘到总答案中ans *= f[m];}// 减去1是因为初始时将空集也算进去了return ans - 1;}
}

统计数组中每个数字按模k分组的出现次数，并保持数值有序

// 使用HashMap存储每个余数对应的TreeMap，TreeMap按键排序
Map<Integer, TreeMap<Integer, Integer>> cnts = new HashMap<>();// 统计每个数字模k的结果，并记录其出现次数for (int x : nums) {cnts.computeIfAbsent(x % k, i -> new TreeMap<>()).merge(x, 1, Integer::sum);}

外层HashMap：键是数字对k取模的余数，用于快速定位余数对应的分组
内层TreeMap：值是有序映射，维护该余数下所有原始数字及其出现次数，按键（数字大小）自动排序

computeIfAbsent(x%k, ...)：余数分组不存在时创建新TreeMap，保证分组结构 merge(x, 1, Integer::sum)：合并相同数字的计数，存在则累加，不存在则初始化为1

作用

快速访问：通过余数直接定位到对应的数字集合
有序存储：TreeMap保持数字自然顺序，便于后续有序遍历或范围查询
高效计数：merge操作简化了频次统计逻辑，避免显式判断键是否存在

适用场景：需要同时按余数分组、维护数值顺序，并统计数值出现次数的算法问题（如某些数对匹配、余数互补检查等问题）

merge(x, 1, Integer::sum)

Java 中 Map 接口提供的一个方法，用于合并指定键的值。
merge 方法的签名如下：

default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)

key: 要合并的键。
value: 如果键不存在时要插入的值。
remappingFunction: 一个函数，用于合并现有的值和新值。

解释

在代码中，merge(x, 1, Integer::sum) 的作用是：

检查键是否存在:

如果键 x 不存在于 TreeMap 中，则将其插入，并将值设置为 1。

合并现有值:

如果键 x 已经存在于 TreeMap 中，则使用 Integer::sum 函数将现有值与 1 相加。

示例

设有一个 TreeMap<Integer, Integer>，初始为空。执行以下操作：

TreeMap<Integer, Integer> map = new TreeMap<>();
map.merge(1, 1, Integer::sum); // map 现在是 {1=1}
map.merge(1, 1, Integer::sum); // map 现在是 {1=2}
map.merge(2, 1, Integer::sum); // map 现在是 {1=2, 2=1}
map.merge(2, 1, Integer::sum); // map 现在是 {1=2, 2=2}

在代码中的应用

在代码中，merge(x, 1, Integer::sum) 用于统计每个数字模 k 后的结果及其出现次数。

步骤如下：

计算余数:

对于每个数字 x，计算其模 k 的结果 x % k。

存储余数及其出现次数:

使用 computeIfAbsent 方法确保 HashMap 中存在键 x % k 对应的 TreeMap。
使用 merge(x, 1, Integer::sum) 将键 x 在 TreeMap 中的值增加 1。如果 x 不存在于 TreeMap 中，则将其初始化为 1。

merge 的常见用法

default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)

merge 方法在 Java 中非常灵活，可以用于各种场景。

统计频率

用于统计某个键出现的次数。

import java.util.HashMap;
import java.util.Map;public class FrequencyCounter {public static void main(String[] args) {String[] words = {"apple", "banana", "apple", "orange", "banana", "apple"};Map<String, Integer> frequencyMap = new HashMap<>();for (String word : words) {frequencyMap.merge(word, 1, Integer::sum);}System.out.println(frequencyMap); // 输出: {banana=2, orange=1, apple=3}}
}

合并字符串

import java.util.HashMap;
import java.util.Map;public class StringMerger {public static void main(String[] args) {Map<String, StringBuilder> map = new HashMap<>();String[] words = {"hello", "world", "hello"};for (String word : words) {map.merge(word, new StringBuilder(word), (existing, replacement) -> existing.append(", ").append(replacement));}for (Map.Entry<String, StringBuilder> entry : map.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue().toString());}// 输出:// hello: hello, hello// world: world}
}

合并集合

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;public class SetMerger {public static void main(String[] args) {Map<String, Set<Integer>> map = new HashMap<>();String[] keys = {"a", "b", "a", "c", "b"};int[] values = {1, 2, 3, 4, 5};for (int i = 0; i < keys.length; i++) {map.merge(keys[i], new HashSet<>(Set.of(values[i])), (existing, replacement) -> {existing.addAll(replacement);return existing;});}for (Map.Entry<String, Set<Integer>> entry : map.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}// 输出:// a: [1, 3]// b: [2, 5]// c: [4]}
}

合并自定义对象

import java.util.HashMap;
import java.util.Map;class Account {private String name;private double balance;public Account(String name, double balance) {this.name = name;this.balance = balance;}public void deposit(double amount) {this.balance += amount;}@Overridepublic String toString() {return "Account{name='" + name + "', balance=" + balance + "}";}
}public class CustomObjectMerger {public static void main(String[] args) {Map<String, Account> accountMap = new HashMap<>();String[] names = {"Alice", "Bob", "Alice"};double[] amounts = {100.0, 200.0, 50.0};for (int i = 0; i < names.length; i++) {accountMap.merge(names[i], new Account(names[i], amounts[i]), (existing, replacement) -> {existing.deposit(replacement.balance);return existing;});}for (Map.Entry<String, Account> entry : accountMap.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}// 输出:// Alice: Account{name='Alice', balance=150.0}// Bob: Account{name='Bob', balance=200.0}}
}

合并列表

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class ListMerger {public static void main(String[] args) {Map<String, List<Integer>> map = new HashMap<>();String[] keys = {"a", "b", "a", "c", "b"};int[] values = {1, 2, 3, 4, 5};for (int i = 0; i < keys.length; i++) {map.merge(keys[i], new ArrayList<>(List.of(values[i])), (existing, replacement) -> {existing.addAll(replacement);return existing;});}for (Map.Entry<String, List<Integer>> entry : map.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}// 输出:// a: [1, 3]// b: [2, 5]// c: [4]}
}

merge 方法是一个非常强大的工具，可以用于多种类型的合并操作。通过提供一个键、一个默认值和一个合并函数，可以灵活地处理不同的数据结构和逻辑。

键不存在时: 插入默认值。
键存在时: 使用提供的合并函数将现有值与新值合并。