我的CSDN博客直达

Pow(x,n)(分治)

在这里插入图片描述
分治法
采用分治的思想,求x的n次方,可以先求x的n/2次方

如果n为偶数x^n = x^(n/2)* x^(n/2)
如果n为奇数x^n = x^(n/2)* x^(n/2) *x

public class Main {
    public double myPow(double x, int n) {
        if (x == 1) return 1;//特殊用例,加快速度
        if (x == -1) return n % 2 == 0 ? 1 : -1;//特殊用例,加快速度
        if (n == -2147483648) return 0;//一个特殊的坑人的用例
        if (n < 0) {//负数次方处理
            n = -n;
            x = 1 / x;
        }
        return pow(x, n);
    }

    double pow(double x, int n) {
        if (n == 0) return 1;
        //求n/2次方的值
        double half = myPow(x, n / 2);
        return n % 2 == 0 ? half * half : half * half * x;
    }
}

为运算表达式设计优先级(分治)

在这里插入图片描述
分治算法典型应用
分治法

class Solution {
     public List<Integer> diffWaysToCompute(String input) {
        List<Integer> ways = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (int l : left) {
                    for (int r : right) {
                        switch (c) {
                            case '+':
                                ways.add(l + r);
                                break;
                            case '-':
                                ways.add(l - r);
                                break;
                            case '*':
                                ways.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        //只有数字没有符号的情况
        if (ways.size() == 0) {
            ways.add(Integer.valueOf(input));
        }
        return ways;
    }
}

子集(回溯)

在这里插入图片描述
回溯法
解法一:
每次遍历加一个大于原来数下标的数到集合,把集合加入到结果集

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    ans.add(new ArrayList<>());//初始化空数组
    for(int i = 0;i<nums.length;i++){
        List<List<Integer>> ans_tmp = new ArrayList<>();
        //遍历之前的所有结果
        for(List<Integer> list : ans){
            List<Integer> tmp = new ArrayList<>(list);
            tmp.add(nums[i]); //加入新增数字
            ans_tmp.add(tmp);
        }
        ans.addAll(ans_tmp);
    }
    return ans;
}

解法二:
将添加值的问题分为加值不加值两种

public class Main {
    List<List<Integer>> res;
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        if (nums == null) return res;
        dfs(nums, new ArrayList<Integer>(), 0);
        return res;
    }

    /**
     * @param nums  入参数组
     * @param list  传入每层的数组
     * @param level 层数
     */
    private void dfs(int[] nums, List<Integer> list, int level) {

        if (level == nums.length) {
            res.add(new ArrayList<>(list));//因为list是传入的引用,所以需要new一个list加入
            return;
        }
        //不需要这个参数的集合
        dfs(nums, list, level + 1);
        //将值加入列表,再进行下探
        list.add(nums[level]);
        dfs(nums, list, level + 1);
        //reserve
        list.remove(list.size() - 1);//真的list 引用,操作完了之后必须reserve
    }
}

子集II(回溯)

在这里插入图片描述
思路:

  • 数组排序
  • 每次遍历加一个大于原来数下标的数到集合,把集合加入到结果集
  • 如果两个数的值相同,第二次就不用加入遍历了,避免重复
public class Solution {

    List<List<Integer>> res;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        res = new ArrayList<>();
        if (nums == null) return res;
        Arrays.sort(nums);
        dfs(nums, new ArrayList<Integer>(), 0);
        return res;
    }


    private void dfs(int[] nums, List<Integer> list, int start) {
        res.add(new ArrayList<>(list));
        for (int i = start;i<nums.length;i++){
            //和上一个数字相同,跳过
            if (i>start&&nums[i]==nums[i-1])continue;

            list.add(nums[i]);
            dfs(nums, list, i + 1);
            //reserve
            list.remove(list.size() - 1);
        }
    }
}

迭代法
这个题还有一个比较经典的玩法就是迭代法
遍历入参集合,每次都把已有的集合复制一份,然后把值加入到复制的集合中

public class Main {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null) return res;
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> tmp_list = new ArrayList<>();//使用tmp_list,保证遍历时取的数都是上一轮的
            for (List list : res) {
                List<Integer> curlist = new ArrayList<>(list);
                curlist.add(nums[i]);
                tmp_list.add(curlist);
            }
            res.addAll(tmp_list);
        }
        return res;
    }
}

电话号码的字母组合(回溯)

在这里插入图片描述
回溯法

public class Main {
    Map<Character, String> map;
    List<String> res;

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0 || digits == null) return new ArrayList<>();
        //初始化
        map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        res = new LinkedList<>();

        search("", digits, 0);
        return res;

    }

    private void search(String s, String digits, int level) {
        //退出条件,长度够了
        if (level == digits.length()) {
            res.add(s);
            return;
        }
        //获取第level个数字对应的字母
        String cur = map.get(digits.charAt(level));
        //遍历字母并依次下探
        for (int i = 0; i < cur.length(); i++) {
            search(s + cur.charAt(i), digits, level + 1);
        }
    }
}

单词搜索(回溯)

在这里插入图片描述
回溯法DFS解法

搜索到以word的第一个字母开头的位置,然后进行深度优先遍历

public class Solution {
    int m;
    int n;

    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) return true;
        if (board == null || board.length == 0 || board[0].length == 0) return false;

        m = board.length;
        n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                if (board[r][c] == word.charAt(0) && dfs(0, r, c, visited, board, word))
                    return true;
        return false;
    }

    private boolean dfs(int curlen, int r, int c, boolean[][] visited, char[][] board, String word) {

        if (curlen == word.length()) return true;

        if (r == -1 || c == -1 || r == m || c == n
                || board[r][c] != word.charAt(curlen) || visited[r][c])
            return false;

        visited[r][c] = true;


        if (dfs(curlen + 1, r + 1, c, visited, board, word)) return true;
        if (dfs(curlen + 1, r - 1, c, visited, board, word)) return true;
        if (dfs(curlen + 1, r, c + 1, visited, board, word)) return true;
        if (dfs(curlen + 1, r, c - 1, visited, board, word)) return true;

        //reserve
        visited[r][c] = false;

        return false;
    }
}

组合(回溯)

在这里插入图片描述
在这里插入图片描述
回溯法

public class Main {
    List<List<Integer>> res;
    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();
        if (n <= 0 || k <= 0 || n < k) {
            return res;
        }
        findCombinations(n, k, 1, new Stack<>());
        return res;
    }
    private void findCombinations(int n, int k, int begin, Stack<Integer> pre) {
        //当数目够了k就加入结果集并退出
        if (pre.size() == k) {
            res.add(new ArrayList<>(pre));
            return;
        }

        //进一步下探,添加一个数,并下探它后面的数继续进行添加
        for (int i = begin; i <= n; i++) {
            pre.add(i);
            findCombinations(n, k, i + 1, pre);
            pre.pop();
        }
    }
}

for 循环里 i 从 start 到 n,其实没必要到 n。比如,n = 5,k = 4,temp.size( ) == 1,此时代表我们还需要(4 - 1 = 3)个数字,如果 i = 4 的话,以后最多把 4 和 5 加入到 temp 中,而此时 temp.size() 才等于 1 + 2 = 3,不够 4 个,所以 i 没必要等于 4,i 循环到 3 就足够了。
所以,需要对下探条件进行修改,对整个递归树进行剪枝,减去图中绿色的数(图自题解
在这里插入图片描述
推算出剪枝规则是i <= n - (k -temp.size()) + 1

于是优化后的代码如下

public class Main {
    List<List<Integer>> res;
    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();
        if (n <= 0 || k <= 0 || n < k) {
            return res;
        }
        findCombinations(n, k, 1, new Stack<>());
        return res;
    }
    private void findCombinations(int n, int k, int begin, Stack<Integer> pre) {
        //当数目够了k就加入结果集并退出
        if (pre.size() == k) {
            res.add(new ArrayList<>(pre));
            return;
        }

        //进一步下探,添加一个数,并下探它后面的数继续进行添加
        for (int i = begin; i <= n - (k - pre.size()) + 1; i++) {
            pre.add(i);
            findCombinations(n, k, i + 1, pre);
            pre.pop();
        }
    }

}

组合总和(回溯)

在这里插入图片描述

public class Solution {
    List<List<Integer>> res;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList<>();
        backtrack(new ArrayList<>(), 0, target, candidates);
        return res;
    }

    private void backtrack(List<Integer> tempCombination, int start, int target, int[] candidates) {
        if (target == 0) {
            res.add(new ArrayList<>(tempCombination));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                //当前层
                tempCombination.add(candidates[i]);
                //下探
                backtrack(tempCombination, i, target - candidates[i], candidates);
                //reserve
                tempCombination.remove(tempCombination.size() - 1);
            }
        }
    }
}

组合总和II(回溯)

在这里插入图片描述
与上一题相比,要做好防重复的准备
首先可以先到加一个标记位,然后每次检查下就好了,但是重复数字可能造成重复结果,且样例少不了变态的几十个重复的。
所以,先对入参进行排序,如果发现重复的,判断用不用得上,用不上就依次跳过

public class Solution {
    List<List<Integer>> res;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        res = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] visited = new boolean[candidates.length];
        backtrack(new ArrayList<>(), 0, target, candidates, visited);
        return res;
    }

    private void backtrack(List<Integer> tempCombination, int start, int target, int[] candidates, boolean[] visited) {
        if (target == 0) {
            res.add(new ArrayList<>(tempCombination));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            //当前节点等于上一个节点,且上一个节点没有被访问过,直接跳过(如果上一个都没用上,当前这个就更没用了)
            if (i != 0 && candidates[i] == candidates[i - 1] && !visited[i - 1]) continue;
            if (candidates[i] <= target) {
                //当前层
                tempCombination.add(candidates[i]);
                visited[i] = true;
                //下探(因为不能重复,所以i要+1)
                backtrack(tempCombination, i + 1, target - candidates[i], candidates, visited);
                //reserve
                visited[i] = false;
                tempCombination.remove(tempCombination.size() - 1);
            }
        }
    }
}

组合总和III(回溯)

在这里插入图片描述

class Solution {
     List<List<Integer>> res;

    public List<List<Integer>> combinationSum3(int k, int n) {
        res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        backtrack(k, n, tmp, 1);
        return res;
    }

    private void backtrack(int k, int n, List<Integer> tmp, int start) {
        //k,n都刚好终止则符合
        if (k == 0 && n == 0) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        //单个条件终止,说明这条路径不行
        if (k == 0 || n == 0) return;

        for (int i = start; i <= 9; i++) {
            //当前层
            tmp.add(i);
            //下探
            backtrack(k - 1, n - i, tmp, i + 1);
            //reserve
            tmp.remove(tmp.size() - 1);
        }
    }
}

全排列(回溯)

在这里插入图片描述
这个题组合一样,都是标准的回溯的模板解决

public class Main {

    List<List<Integer>> res;

    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        backtrack(new ArrayList<>(), nums);
        return res;
    }

    private void backtrack(List<Integer> tmpList, int[] nums) {

        if (tmpList.size() == nums.length) {
            res.add(new ArrayList<>(tmpList));//切记要新new一个加入
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (tmpList.contains(nums[i])) continue;//已经存在了,就跳过
            //当前层业务
            tmpList.add(nums[i]);
            //下探
            backtrack(tmpList, nums);
            //reserve
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

全排列II(回溯)

在这里插入图片描述
与上一个题全排列相比,本题存在两个新的问题

  1. if(tempList.contains(nums[i])) continue;这句代码是通过比较值不同跳过的,而现在值可以相同
  2. 如果有两个相同的值,则会产生两次一样的结果

针对上述两个问题,进行如下的升级
首先将nums进行排序,重新定义个一个old集合存放访问过的值的下标,使即使值相同也能判断是否访问过

针对重复现象,改为如下代码去重

            //判断上一个元素和自己是不是一样的,一样说明上次就加进去了,不用重复操作了
            // !old.contains(i - 1)是为了保证前一个数是因为回溯被还原了的才跳过,否则不能跳过
            if (i > 0 && !old.contains(i - 1) && nums[i - 1] == nums[i]) {
                continue;
            }

视频讲解剪枝原理参考大佬的题解

public class Main {

    List<List<Integer>> res;

    public List<List<Integer>> permuteUnique(int[] nums) {
        res = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> old = new ArrayList<>();
        backtrack(new ArrayList<>(), nums, old);
        return res;
    }

    private void backtrack(List<Integer> tmpList, int[] nums, List<Integer> old) {

        if (tmpList.size() == nums.length) {
            res.add(new ArrayList<>(tmpList));//切记要新new一个加入
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //当前下标的值已经被使用过了
            if (old.contains(i)) {
                continue;
            }

            //判断上一个元素和自己是不是一样的,一样说明上次就加进去了,不用重复操作了
            // !old.contains(i - 1)是为了保证前一个数是因为回溯被还原了的才跳过,否则不能跳过
            if (i > 0 && !old.contains(i - 1) && nums[i - 1] == nums[i]) {
                continue;
            }
            //当前层业务    
            old.add(i);        
            tmpList.add(nums[i]);
            //下探
            backtrack(tmpList, nums, old);
            //reserve
            old.remove(old.size() - 1);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

N皇后(回溯)

在这里插入图片描述
超经典回溯题,思路见代码注解

public class Main {

    List<List<String>> res;

    //标记列是否被攻击
    int[] rows;
    //标记次对角线是否被攻击
    int[] secondMain;
    //标记主对角线是否被攻击
    int[] main;
    //存储皇后的位置
    int[] queens;
    //n皇后
    int n;

    public List<List<String>> solveNQueens(int n) {
        //初始化
        res = new ArrayList<>();
        rows = new int[n];
        secondMain = new int[2 * n - 1];
        main = new int[2 * n - 1];
        queens = new int[n];
        this.n = n;

        //回溯算法从第0行开始查找皇后的位置
        backtrack(0);

        return res;
    }

    //回溯算法放置皇后
    private void backtrack(int row) {
        if (row >= n) return;
        //从第一列开始尝试放皇后
        for (int col = 0; col < n; col++) {
            //检测是否会被攻击,如果没有攻击再进行下一步操作
            if (isNotUnderAttrack(row, col)) {
                //在当前位置放置皇后
                placeQueen(row, col);
                // 放置完成判断现在是否是最后一行,如果是就存储这个方案
                if (row == n - 1) addSolution();
                //下探 在下一行放皇后
                backtrack(row + 1);
                //回溯,将上一个皇后去掉
                removeQueen(row, col);

            }
        }

    }

    //回溯,去掉皇后和皇后的攻击范围
    private void removeQueen(int row, int col) {

        //移除row行的皇后
        queens[row] = 0;
        //更新列攻击范围
        rows[col] = 0;
        //更新主对角线攻击范围
        main[row - col + n - 1] = 0;
        //更新次对角线攻击范围
        secondMain[row + col] = 0;

    }

    //将满足条件的皇后位置放入结果集
    private void addSolution() {
        List<String> solution = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            //记录当前行皇后位置
            int col = queens[i];
            StringBuilder builder = new StringBuilder();
            for (int j = 0; j < col; j++) builder.append(".");
            builder.append("Q");
            for (int j = 0;j<n-col-1;j++)builder.append(".");
            solution.add(builder.toString());
        }
        res.add(solution);
    }

    //指定位置放置皇后
    private void placeQueen(int row, int col) {
        //存放皇后
        queens[row] = col;
        //更新列攻击范围
        rows[col] = 1;
        //更新主对角线攻击范围
        main[row - col + n - 1] = 1;
        //更新次对角线攻击范围
        secondMain[row + col] = 1;
    }

    //检验位置是否会被攻击
    private boolean isNotUnderAttrack(int row, int col) {
        //对于列,直接判断列位置是否为0
        //对于主对角线,row的值恒为col-n+1,所以将row - col + n - 1=0表示
        //对于次对角线,row+col的值可以表示一条线
        return rows[col] + main[row - col + n - 1] + secondMain[row + col] == 0;
    }
}