刷题-回溯
2022-06-04  学习

回溯的题,这类题老是忘

  1. 虽然不是回溯,力扣1091

    最短、最优解这些用广度优先搜索,找到所有解的两个都行,但一般还是深度优先搜索更好写。

  2. 深度优先搜索

    力扣695, 200, 547, 130

  3. 回溯

    力扣17, 93, 79, 257,46,47,77,39,216,78,90,131

    93题:复原IP地址

    class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> list = new ArrayList<>();
            if(s.length() < 4){
                return list;
            }
            backtrack(s, new StringBuilder(), 0, list);
            return list;
        }
    
        private void backtrack(String s, StringBuilder prefix, int num, List<String> list){
            if(num == 4 || s.length() == 0){
                if(num == 4 && s.length() == 0){
                    list.add(prefix.toString());
                }
                return;
            }
            int n = s.length();
            for(int i=0; i<n && i<=2; ++i){
                if(i != 0 && s.charAt(0) == '0'){
                    return;
                }
                String curr = s.substring(0, i+1);
                if(Integer.valueOf(curr) <= 255){
                    if(num != 0){
                        curr = "." + curr;
                    }
                    prefix.append(curr);
                    backtrack(s.substring(i+1), prefix, num+1, list);
                    prefix.delete(prefix.length()-curr.length(), prefix.length());
                }
            }
        }
    }

    力扣257

    class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> list = new ArrayList<>();
            dfs(root, new StringBuilder(), list);
            return list;
        }
    
        private void dfs(TreeNode root, StringBuilder path, List<String> list){
            path.append(root.val + "");
            if(root.left == null && root.right == null){
                list.add(path.toString());
                return;
            }
            if(root.left != null){
                dfs(root.left, new StringBuilder(path).append("->"), list);
            }
            if(root.right != null){
                dfs(root.right, new StringBuilder(path).append("->"), list);
            }
        }
    }

    力扣47

    for(int i=0; i<n; ++i){
                   if(!isVisited[i]){
                       isVisited[i] = true;
                       path.add(nums[i]);
                       backtrack(nums, list, path, isVisited);
                       path.remove(path.size()-1);
                       isVisited[i] = false;
                       //111123, 回溯后,跳到最后一个1,for循环那还有一个++i,从2开始
                       while(i < n-1 && nums[i] == nums[i+1]){
                           ++i;
                       }
                   }
               }
  • 有顺序的,排列:for循环从0开始
  • 没顺序的,组合:for循环从start开始,传参

力扣131

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> list = new ArrayList<>();
        List<String> path = new ArrayList<>();
        backtrack(s, list, path);
        return list;
    }

    private void backtrack(String s, List<List<String>> list, List<String> path){
        if(s.length() == 0){
            list.add(new ArrayList<>(path));
            return;
        }
        int n = s.length();
        for(int i=0; i<n; ++i){
            if(check(s, i)){
                path.add(s.substring(0, i+1));
                backtrack(s.substring(i+1), list, path);
                path.remove(path.size()-1);
            }
        }
    }

    private boolean check(String s, int k){
        int i = 0, j = k;
        while(i < j){
            if(s.charAt(i++) != s.charAt(j--)){
                return false;
            }
        }
        return true;
    }
}