今日任务

39. 组合总和

40.组合总和II

131.分割回文串

 93.复原IP地址 

39. 组合总和

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> now_ans = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        combination(candidates, target, 0);
        return ans;
    }
    public void combination(int[] candidates, int target, int index){
        if(target == 0){
            ans.add(new ArrayList<Integer>(now_ans));
            return ;
        }
        if(candidates[index] > target) return;
        for(int i = index; i < candidates.length; i++){
            if (candidates[i] > target) break;
            now_ans.add(candidates[i]);
            combination(candidates, target-candidates[i], i);
            now_ans.removeLast();
        }
        return ;
    }
}

40.组合总和II

和上一题的不同在于这题需要去重复

如何在深度搜索的时候进行去重复呢？

在于每一层上的不重复行为

while(i > index && i < candidates.length && candidates[i] == candidates[i-1]) i++;
            if(i >= candidates.length) break;
            if(candidates[i] > target) break;

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> now_ans = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        combination(candidates, target, 0);
        return ans;
    }
    public void combination(int[] candidates, int target, int index){
        if(target == 0){
            ans.add(new ArrayList<>(now_ans));
            return;
        }
        if(index >= candidates.length || candidates[index] > target) return;
        for(int i = index; i < candidates.length; i++){
            while(i > index && i < candidates.length && candidates[i] == candidates[i-1]) i++;
            if(i >= candidates.length) break;
            if(candidates[i] > target) break;
            now_ans.add(candidates[i]);
            combination(candidates, target - candidates[i], i+1);
            now_ans.removeLast();
        }
        return;
    }
}

131.分割回文串

class Solution {
    List<List<String>> ans = new ArrayList<>();
    LinkedList<String> now_ans = new LinkedList<>();
    public List<List<String>> partition(String s) {
        combianation(s, 0);
        return ans;
    }
    public void combianation(String s, int index){
        if(index >= s.length()) {
            ans.add(new ArrayList<>(now_ans));
            return;
        }
        for(int i = index; i < s.length(); i++){
            if(ispalindrome(s, index, i)){
                now_ans.add(s.substring(index, i+1));
                combianation(s, i+1);
                now_ans.removeLast();
            }
        }
        return;
    }
    public Boolean ispalindrome(String s, int start, int end){
        while(start < end){
            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}

93.复原IP地址

细节真的超级多的一题

首先如果首位为0的话 only地址该位为0 就会成立

其次关于这题的数据结构知识的应用

对于我来说java的各种list的使用以及string的使用还是有些陌生

如何将我们的LinkedList转换为String

LinkedList的增删较为方便，使用add以及removeLast()

ArrayList的方便在于取值以及可以无限增加的大小 使用get进行取值

其次，还是要强调java的“”和‘’并不通用，String和char是不通用的，可以使用

""+s.charAt(index)进行转换

class Solution {
    List<String> ans = new ArrayList<String>();
    LinkedList<String> now_ans = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        if(s.length() < 4) return ans;
        combination(s,0,0);
        return ans;
    }

    public void combination(String s, int index, int num){
        if(index >= s.length() && num == 4){
            ArrayList<String> temp1 = new ArrayList<>(now_ans);
            String temp = temp1.get(0) + "." +  temp1.get(1) + '.' +  temp1.get(2) + '.' + temp1.get(3);
            ans.add(temp);
            return;
        }
        if(index >= s.length() || num >= 4) return;

        if(s.charAt(index) == '0'){
            now_ans.add(""+s.charAt(index));
            combination(s, index + 1, num + 1);
            now_ans.removeLast();
            return;
        }

        for(int i = 1; i <= 3; i++){
            if((i+index) > s.length()) break;
            String temp2 = s.substring(index, index + i);
            int temp3 = 0;
            for(int j = 0; j < i; j++) temp3 = temp3 * 10 + (temp2.charAt(j) - '0');
            if(temp3 <= 255) {
                now_ans.add(temp2);
                combination(s, index + i, num + 1);
                now_ans.removeLast();
            }
        }
        return;
    }
}

78.子集

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

从这题开始回归python啦！！询问了老师的意见

JAVA在刷题中用到的在项目中

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []
        self.backtracking(nums, result, path, 0)
        return result
    
    def backtracking(self, nums, result, path, index):
        result.append(path[:])
        for i in range(index, len(nums)):
            path.append(nums[i])
            self.backtracking(nums, result, path, i+1)
            path.pop()

90.子集II

和上面的去重复方式一样，但是记住使用continue更稳妥

虽然我也不是很清楚不用continue多加一层while+break有什么错

记住需要sort.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = []
        now_ans = []
        nums.sort()
        self.combination(nums,result, now_ans, 0)
        return result

    def combination(self, nums, result, now_ans, index):
        result.append(now_ans[:])
        for i in range(index, len(nums)):
            if i > index and nums[i] == nums[i-1]:
                continue
            now_ans.append(nums[i])
            self.combination(nums, result, now_ans, i+1)
            now_ans.pop()

        
        return