网站开发需求清单,WordPress用户发表插件,服务器cpu,网站流量统计软件本题是扩展题#xff0c;真实考过#xff0c;看这个题之前先看一下39题
Leetcode面试经典150题-39.组合总数-CSDN博客
给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数…本题是扩展题真实考过看这个题之前先看一下39题
Leetcode面试经典150题-39.组合总数-CSDN博客
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。 示例 1:
输入: candidates [10,1,2,7,6,1,5], target 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates [2,5,2,1,2], target 5,
输出:
[
[1,2,2],
[5]
] 提示:
1 candidates.length 1001 candidates[i] 501 target 30
其他的就不多说了上代码看不懂的请留言或者私信收到第一时间解答
class Solution {/**这个题目对比第39题难度极大吧我觉得这哪是中等难度百分百的hard难度这个题对比39题的不同是每个位置的数只能使用一次但是有可能有的位置的数是重复的而重复的集合也应该被考虑这里我的解题思路是既然有重复的数那就过滤出一个数组放数另外一个数组放这个数出现的频率来试试这个解法*/public ListListInteger combinationSum2(int[] candidates, int target) {/**先统计词频 */MapInteger,Integer map new HashMap();for(int num : candidates) {map.put(num, map.getOrDefault(num, 0) 1);}/**统计完词频之后把原来的数组分为两个数组这里我想先排序所以这里先统计出数字数组稍后再统计词频数组 */int[] nums new int[map.keySet().size()];int curIndex 0;for(int num : map.keySet()) {nums[curIndex ] num;}/**排个序用于剪枝*/Arrays.sort(nums);/**统计词频数组 */int[] counts new int[nums.length];for(int i 0; i nums.length; i) {counts[i] map.get(nums[i]);}return process(nums, counts, 0, target);}public ListListInteger process(int[] nums, int[] counts, int curIndex, int targetLeft) {ListListInteger ans new ArrayList();if(targetLeft 0) {ans.add(new ArrayList());return ans;}/**如果targetLeft不为0但是我们没有数了失败返回空集合 */if(curIndex nums.length) {return ans;}/**我们是按照从小到大排序的数组如果targetLeft已经比当前数小了也没必要继续尝试了 */if(targetLeft nums[curIndex]) {return ans;}/**其他情况正常尝试,当前数可以尝试Math.min(count[curIndex], targetLeft/nums[curIndex])次*/for(int i 0; i Math.min(counts[curIndex], targetLeft/nums[curIndex]); i) {ListListInteger next process(nums, counts, curIndex 1, targetLeft - i * nums[curIndex]);for(ListInteger list : next) {/**当前数加了多少个就加入多少个到next中的集合中因为确实是使用了这么多个 */for(int num 0; num i; num ) {list.add(nums[curIndex]);}/**加入到当前数的集合 */ans.add(list);}}return ans;}
}
