代码随想录算法训练营第二十天

其他:

今日总结
往期打卡

---

39. 组合总和

跳转: 39. 组合总和

学习: 代码随想录公开讲解

问题:

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路:

回溯,可以当成组合问题一次一次的选,也可以每个元素多次的选(不过效率不高).

复杂度:

• 时间复杂度: $O(2^n)$
• 空间复杂度: $O(n^2)$

代码(一层选一个):

class Solution {List<List<Integer>> ans;private final List<Integer> path = new ArrayList<>();int target;void dfs(int[] candidates, int sum,int index){if(sum>target) return;if(sum==target) ans.add(new ArrayList<>(path));for(int i=index;i<candidates.length;i++){path.add(candidates[i]);dfs(candidates,sum+candidates[i],i);path.remove(path.size()-1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {ans = new ArrayList<>();this.target = target;dfs(candidates,0,0);return ans;}
}

代码(每个选0-n次):

class Solution {List<List<Integer>> ans;int target;int[] candidates;private final List<Integer> path = new ArrayList<>();int n;void dfs(int index,int value){if(value>target) return;if(value == target){ans.add(new ArrayList<>(path));return;}if(index<0) return;int sum = 0;while(sum+value<=target){dfs(index-1,value+sum);path.add(candidates[index]);sum+=candidates[index];}int count = sum/candidates[index];path.removeAll(path.subList(path.size()-sum/candidates[index],path.size()));}public List<List<Integer>> combinationSum(int[] candidates, int target) {ans = new ArrayList<>();this.target = target;this.candidates = candidates;n = candidates.length;dfs(n-1,0);return ans;}
}

---

40. 组合总和 II

跳转: 40. 组合总和 II

学习: 代码随想录公开讲解

问题:

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

思路:

每层同种元素只能选一个,为了更好的分辨同种元素,可以先排序

复杂度:

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(n)$

代码(回溯):

class Solution {List<List<Integer>> ans;private final List<Integer> path = new ArrayList<>();int target;void dfs(int[] candidates, int sum, int index) {if (sum == target) {ans.add(new ArrayList<>(path));return;}for (int i = index; i < candidates.length; i++) {if (sum + candidates[i] > target) {break;}if (i > index && candidates[i] == candidates[i - 1]) {continue;}path.add(candidates[i]);dfs(candidates, sum + candidates[i], i + 1);path.remove(path.size() - 1);}}public List<List<Integer>> combinationSum2(int[] candidates, int target) {ans = new ArrayList<>();Arrays.sort(candidates);// System.out.println(Arrays.toString(candidates));this.target = target;dfs(candidates, 0, 0);return ans;}
}

---

131. 分割回文串

跳转: 131. 分割回文串

学习: 代码随想录公开讲解

问题:

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

思路:

在回文串位置切割,切割到最后一个位置时返回

复杂度:

• 时间复杂度: $O(n^3)$
• 空间复杂度: $O(n^2)$

代码:

class Solution {List<List<String>> ans;List<String> path = new ArrayList<>();void dfs(String s,int startIndex){if(startIndex==s.length()){ans.add(new ArrayList<>(path));}for(int i=startIndex+1;i<=s.length();i++){if(isPalindrome(s,startIndex,i-1)){path.add(s.substring(startIndex,i));}else continue;dfs(s,i);path.remove(path.size()-1);}}boolean isPalindrome(String s,int startIndex,int endIndex){while(startIndex<endIndex){if(s.charAt(startIndex++)!=s.charAt(endIndex--)) return false;}return true;}public List<List<String>> partition(String s) {ans = new ArrayList<>();dfs(s,0);return ans;}
}

---

2176. 统计数组中相等且可以被整除的数对(每日一题)

跳转: 2176. 统计数组中相等且可以被整除的数对

问题:

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 <= i < j < n ，nums[i] == nums[j] 且 (i * j) 能被 k 整除的数对 (i, j) 的 数目 。

思路:

直接两层for循环遍历,遇到满足条件的位置+1

复杂度:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

代码:

class Solution {public int countPairs(int[] nums, int k) {int n = nums.length;int ans = 0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(nums[i]==nums[j]&&i*j%k==0) ans++;}}return ans;}
}

---

总结

练习了带条件的组合回溯

往期打卡

代码随想录算法训练营第十九天

代码随想录算法训练营第十八天

代码随想录算法训练营第十七天

代码随想录算法训练营周末三

代码随想录算法训练营第十六天

代码随想录算法训练营第十五天

代码随想录算法训练营第十四天

代码随想录算法训练营第十三天

代码随想录算法训练营第十二天

代码随想录算法训练营第十一天

代码随想录算法训练营周末二

代码随想录算法训练营第十天

代码随想录算法训练营第九天

代码随想录算法训练营第八天

代码随想录算法训练营第七天

代码随想录算法训练营第六天

代码随想录算法训练营第五天

代码随想录算法训练营周末一

代码随想录算法训练营第四天

代码随想录算法训练营第三天

代码随想录算法训练营第二天

代码随想录算法训练营第一天