Tag: 回溯

解法一：

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList();
        if(digits.length() == 0){
            return res;
        }
        int len = digits.length();
        for(int i = 0;i < len;i++){
            String s = get(digits.charAt(i));
            int l = res.size();
            if(l == 0){
                for (int j = 0; j < s.length(); j++) {
                    res.add(String.valueOf(s.charAt(j)));
                }
            }else {
                ArrayList temp = new ArrayList();
                temp.addAll(res);
                for(int j = 0;j < s.length()-1;j++){
                    res.addAll(temp);
                }
                for(int k = 0;k < res.size();k++){
                    res.set(k,res.get(k) + s.charAt(k / l));
                }
            }
        }
        return res;
    }
    public String get(char i){
        switch(i){
            case '2' : return "abc";
            case '3' : return "def";
            case '4' : return "ghi";
            case '5' : return "jkl";
            case '6' : return "mno";
            case '7' : return "qprs";
            case '8' : return "tuv";
            case '9' : return "wxyz";
        }
        return null;
    }
}

T4mako4/17/26About 2 min

022_括号生成

解法一：

class Solution {
    public ArrayList<ArrayList<String>> all = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<>();
        res.add("()");
        if(n == 1){
            return res;
        }
        all.add(res);
        for (int i = 2; i <= n; i++) {
            res = add(res,i);
            ArrayList<String> temp = new ArrayList<>();
            temp.addAll(res);
            all.add(temp);
        }
        return res;
    }
    public ArrayList add(ArrayList<String> list,int size){
        ArrayList res = new ArrayList();
        HashSet<String> set = new HashSet();
        for(String i : list){
            set.add("()"+i);
            set.add(i+"()");
            set.add("("+i+")");
            set.remove(i);
        }
        if(size >= 4){
            for (int i = 2; i <= size - 2; i++) {
                int j = size - i;
                for (String s1 : all.get(i - 1)){
                    for(String s2 : all.get(j - 1)){
                        set.add(s1+s2);
                    }
                }
            }
        }
        Object[] strs =set.toArray();
        for(Object i : strs){
            res.add((String)i);
        }
        return res;
    }
}

T4mako4/17/26About 1 min

039_组合总和

class Solution {
     public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(0,target,candidates,new ArrayList<Integer>(),res,0);
        return res;
    }
    public void dfs(int sum,int target,int[] candidates,ArrayList<Integer> list,List<List<Integer>> res,int i){
        if(sum == target){
            res.add(list);
            //防止太大了
        }else if(target - sum >= candidates[i]){
            //i从list中最大值对应candidates数组位置开始
            for (; i < candidates.length; i++) {
                //防止太大了
                if(sum + candidates[i] > target){
                    break;
                }
                ArrayList<Integer> l = new ArrayList<>(list);
                l.add(candidates[i]);
                dfs(sum + candidates[i],target,candidates,l,res,i);
            }
        }
    }
}

T4mako4/17/26Less than 1 minute

040_组合总和II

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        if(target < candidates[0]){
            return res;
        }
        dfs(0,target,candidates,new ArrayList<Integer>(),res,0);
        return res;
    }
    public void dfs(int sum,int target,int[] candidates,ArrayList<Integer> list,List<List<Integer>> res,int begin){
        if(sum == target){
            res.add(list);
        }else if(begin < candidates.length && target - sum >= candidates[begin]){
            for (int i = begin; i < candidates.length; i++) {
                if(i > begin && candidates[i] == candidates[i-1]) continue;
                if(sum + candidates[i] > target){
                    break;
                }
                ArrayList<Integer> l = new ArrayList<>(list);
                l.add(candidates[i]);
                dfs(sum + candidates[i],target,candidates,l,res,i+1);
            }
        }
    }
}

T4mako4/17/26Less than 1 minute

046_全排列

解法一：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        def(0,temp,nums,res);
        return res;
    }
    public void def(int n,ArrayList<Integer> temp,int[] nums,List<List<Integer>> res){
        if(n == nums.length){
            res.add(temp);
        }
        for(int i : nums){
            if(!temp.contains(i)){
                ArrayList<Integer> clone = (ArrayList<Integer>) temp.clone();
                clone.add(i);
                def(n+1,clone,nums,res);
            }
        }
    }
}

T4mako4/17/26About 1 min

047_全排列II

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        boolean[] vis = new boolean[nums.length];
        def(0,temp,nums,res,vis);
        return res;
    }
    public void def(int n,ArrayList<Integer> temp,int[] nums,List<List<Integer>> res,boolean[] vis){
        if(n == nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i = 0;i < nums.length ; i++){
            if(vis[i] || (i > 0 && nums[i-1] == nums[i] && !vis[i - 1])){
                continue;
            }
            vis[i] = true;
            temp.add(nums[i]);
            def(n+1,temp,nums,res,vis);
            vis[i] = false;
            temp.remove(n);
        }
    }
}

T4mako4/17/26Less than 1 minute

095_不同的二叉搜索树II

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        List<TreeNode> res = add(1, n);
        return res;
    }

    public List<TreeNode> add(int left,int right){
        List<TreeNode> res = new LinkedList<>();
        if(left > right){
            res.add(null);
            return res;
        }
        for (int i = left; i <= right; i++) {
            List<TreeNode> leftList = add(left, i - 1);
            List<TreeNode> rightList = add(i + 1, right);
            for (TreeNode leftTree : leftList) {
                for (TreeNode rightTree : rightList) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    res.add(root);
                }
            }
        }
        return res;
    }
}

T4mako4/17/26About 1 min

113_路径总和II

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
       List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        List list = new ArrayList();
        list.add(root.val);
        path(root,root.val,targetSum,res,list);
        return res;
    }
    public void path(TreeNode root, int sum,int target, List<List<Integer>> res,List<Integer> list){
        if(root.left != null){
            list.add(root.left.val);
            sum += root.left.val;
            TreeNode temp = root.left;
            path(temp,sum,target,res,list);
            sum -= list.get(list.size() - 1);
            list.remove(list.size() - 1);
        }
        if(root.right != null){
            list.add(root.right.val);
            sum += root.right.val;
            TreeNode temp = root.right;
            path(temp,sum,target,res,list);
            sum -= list.get(list.size() - 1);
            list.remove(list.size() - 1);
        }
        if(root.left == null && root.right == null && sum == target){
            res.add(new ArrayList<>(list));
        }
    }
}

T4mako4/17/26Less than 1 minute

79. 单词搜索

题目描述

解法：回溯

class Solution {
    public boolean exist(char[][] board, String word) {
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board[0].length; col++) {
            if (dfs(row, col, 0, board, word, new boolean[board.length][board[0].length], new StringBuilder())) {
                return true;
            }
        }
    }
    return false;
}

public boolean dfs(int row, int col, int i, char[][] board, String word, boolean[][] flag, StringBuilder check) {
    if (i >= word.length()) {
        return false;
    }
    
    if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || flag[row][col] || word.charAt(i) != board[row][col]) {
        return false;
    }

    check.append(board[row][col]);
    if (i + 1 == word.length() && word.equals(check.toString())) {
        return true;
    }
    
    flag[row][col] = true;
    if (dfs(row - 1, col, i + 1, board, word, flag, check) ||
        dfs(row + 1, col, i + 1, board, word, flag, check) ||
        dfs(row, col - 1, i + 1, board, word, flag, check) ||
        dfs(row, col + 1, i + 1, board, word, flag, check)) {
        return true;
    }
    
    flag[row][col] = false;
    check.deleteCharAt(check.length() - 1);
    return false;
}


}

T4mako3/25/24Less than 1 minute

52. N 皇后 II

题目描述

解法：

可以根据第 51 题的 N 皇后求得所有结果，计算结果个数
最简便的方法，记住答案，直接返回即可

class Solution {
    public int totalNQueens(int n) {
        int result[] = {1, 0, 0 ,2, 10, 4, 40, 92, 352};
        return result[n - 1];
    }
}

T4mako3/10/24Less than 1 minute