建设校园网站必要性,百度关键词排名技术,肇庆网站建设公司,济南网站建设0531soso文章目录 题目解题思路题解统计数组中每个数字按模k分组的出现次数#xff0c;并保持数值有序作用 **merge(x, 1, Integer::sum)**解释**检查键是否存在**:**合并现有值**: 示例在代码中的应用**计算余数**:**存储余数及其出现次数**: merge 的常见用法统计频率合并字符串合并… 文章目录 题目解题思路题解统计数组中每个数字按模k分组的出现次数并保持数值有序作用 **merge(x, 1, Integer::sum)**解释**检查键是否存在**:**合并现有值**: 示例在代码中的应用**计算余数**:**存储余数及其出现次数**: merge 的常见用法统计频率合并字符串合并集合合并自定义对象合并列表 题目
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解题思路 动态规划 把数组按照模 k 的结果分成k组从第一组选一些数从第二组选一些数。第一组中的数字 x 和第二组中的数字 y二者相差一定不等于 k不同余。只需考虑每组内选数字的方案数根据乘法原理把各个组的方案数相乘即为答案动态规划 设 a 的长度为 m。考虑最大的数 a[m−1] 选或不选 选 a[m−1]及子问题 设 c 为 a[m−1] 的出现次数由于大小为 c 的集合有 2 c − 1 2^c-1 2c−1 个非空子集所以选至少一个 a[m−1] 的方案数为 2 c − 1 2^c-1 2c−1。如果 a[m−1] − a[m−2] k 不选 则变成 a[m - 2] 的子问题 题解 灵神代码 来源力扣LeetCode class Solution {public int beautifulSubsets(int[] nums, int k) {// 使用HashMap存储每个余数对应的TreeMapTreeMap按键排序MapInteger, TreeMapInteger, 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 (TreeMapInteger, 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.EntryInteger, 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存储每个余数对应的TreeMapTreeMap按键排序
MapInteger, TreeMapInteger, 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 相加。
示例
设有一个 TreeMapInteger, Integer初始为空。执行以下操作
TreeMapInteger, Integer map new TreeMap();
map.merge(1, 1, Integer::sum); // map 现在是 {11}
map.merge(1, 1, Integer::sum); // map 现在是 {12}
map.merge(2, 1, Integer::sum); // map 现在是 {12, 21}
map.merge(2, 1, Integer::sum); // map 现在是 {12, 22}在代码中的应用
在代码中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};MapString, Integer frequencyMap new HashMap();for (String word : words) {frequencyMap.merge(word, 1, Integer::sum);}System.out.println(frequencyMap); // 输出: {banana2, orange1, apple3}}
}合并字符串
import java.util.HashMap;
import java.util.Map;public class StringMerger {public static void main(String[] args) {MapString, 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.EntryString, 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) {MapString, SetInteger 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.EntryString, SetInteger 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) {MapString, 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.EntryString, Account entry : accountMap.entrySet()) {System.out.println(entry.getKey() : entry.getValue());}// 输出:// Alice: Account{nameAlice, balance150.0}// Bob: Account{nameBob, balance200.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) {MapString, ListInteger 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.EntryString, ListInteger entry : map.entrySet()) {System.out.println(entry.getKey() : entry.getValue());}// 输出:// a: [1, 3]// b: [2, 5]// c: [4]}
}merge 方法是一个非常强大的工具可以用于多种类型的合并操作。通过提供一个键、一个默认值和一个合并函数可以灵活地处理不同的数据结构和逻辑。 键不存在时: 插入默认值。 键存在时: 使用提供的合并函数将现有值与新值合并。
