淘宝客自建网站,南充做网站电话,网站建设具体步骤应该怎么做,各地持续优化防控措施LeetCode 40 组合总和|| 本题思路#xff1a;由于解集中不能包含重复的组合#xff0c;所以要进行去重的操作。
首先要将数组先进行一个排序操作然后在树层进行去重操作#xff01;#xff08;不懂的可以去看代码随想录讲解视频#xff09;利用一个 used 数组来表示…LeetCode 40 组合总和|| 本题思路由于解集中不能包含重复的组合所以要进行去重的操作。
首先要将数组先进行一个排序操作然后在树层进行去重操作不懂的可以去看代码随想录讲解视频利用一个 used 数组来表示数组中的元素是否已经用过 首先是要找到出口该题的出口就是sum target 的时候就要 return如果等于的时候就要保存结果。 然后在树层进行去重 class Solution {ListInteger path new ArrayList();ListListInteger res new ArrayList();int sum 0;public ListListInteger combinationSum2(int[] candidates, int target) {int[] used new int[candidates.length];Arrays.sort(candidates);backtracking(candidates,target,sum,0,used);return res;}public void backtracking(int[] candidates, int target, int sum, int startIndex,int[] used){if(sum target){return;}if(sum target){res.add(new ArrayList(path));return;}for(int i startIndex; i candidates.length; i){if(i 0 candidates[i] candidates[i-1] used[i-1] 0){continue;}path.add(candidates[i]);sum candidates[i];used[i] 1;backtracking(candidates,target,sum,i1,used);sum - candidates[i];used[i] 0;path.removeLast();}}
}LeetCode 39 组合总和 本题思路和上题一样但是不用进行去重操作
首先找到终止条件如果 sum target 就 return如果 等于 target 就保存路径元素。
class Solution {ListInteger path new ArrayList();ListListInteger res new ArrayList();int sum 0;public ListListInteger combinationSum(int[] candidates, int target) {backtracking(candidates,target,0,sum);return res;}public void backtracking(int[] candidates,int target,int startIndex,int sum){if(sum target){return;}if(sum target){// 将路径元素存起来res.add(new ArrayList(path));return;}for(int i startIndex; i candidates.length; i){path.add(candidates[i]);sum candidates[i];backtracking(candidates,target,i,sum);sum - candidates[i];path.removeLast();}}}LeetCode 131 分割回文串 本题思路首先找到终止条件就是 startIndex s.length()此时就要开始记录路径的元素。 关于判断 s 是否是 回文串的逻辑放在 for 循环里面判断如果是就放进去不是就不放到 path 中所以在终止条件记录元素的时候可以直接记录保存。
class Solution {ListString path new ArrayList();ListListString res new ArrayList();public ListListString partition(String s) {backtracking(s,0);return res;}public void backtracking(String s, int startIndex){if(startIndex s.length()){res.add(new ArrayList(path));return;}for(int i startIndex; i s.length(); i){if(judge(s,startIndex,i)){String str s.substring(startIndex, i 1);path.add(str);}else{continue;}backtracking(s,i1);path.removeLast();}}public boolean judge(String s, int start, int end){while(start end){if(s.charAt(start) ! s.charAt(end)){return false;}start;end--;}return true;}}
