数据结构与算法刷题之【深搜&宽搜递归&分治&剪枝回溯】篇

算法刷题 0 次阅读 33171 字 约 166 分钟

文章目录

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》...有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：image-20220818095030215

2、剑指offerII：image-20220818095104757

力扣总记录数：image-20220818095148897

加油加油！

基础知识

回溯

1、什么是回溯法？

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以为使用了递归，其实还隐藏着回溯 (opens new window)。

回溯是递归的副产品，只要有递归就会有回溯。

2、回溯法的效率？

回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

3、回溯法解决的问题？

回溯法，一般可以解决如下几种问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

相信大家看着这些之后会发现，每个问题，都不简单！

另外，会有一些同学可能分不清什么是组合，什么是排列？

组合是不强调元素顺序的，排列是强调元素顺序。

例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。

记住组合无序，排列有序，就可以了。

4、如何理解回溯？

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一颗高度有限的树（N叉树）。

这块可能初学者还不太理解，后面的回溯算法解决的所有题目中，我都会强调这一点并画图举相应的例子，现在有一个印象就行。

回溯法模板

起名：backtracking

1、回溯算法中函数返回值一般为void。

2、参数：因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

3、终止条件：什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

回溯搜索的遍历过程：在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

回溯法解决的问题都可以抽象为树形结构（N叉树）。

模板框架：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

剑指offer

剑指 Offer 17. 打印从1到最大的n位数【简单】

题目链接：剑指 Offer 17. 打印从1到最大的n位数

题目内容：输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

思路：

1、迭代计算

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
class Solution {
    public int[] printNumbers(int n) {
        int num = 1;
        for (int i = 1; i <= n; i++) {
            num *= 10;
        }
        int[] res = new int[num - 1];
        for (int i = 1; i < num; i++) {
            res[i - 1] = i;
        }
        return res;
    }
}

本题实际上核心考察的是大数问题，只不过题目并没有出清楚。

思路：dfs+回溯

class Solution {
    
	private char[] nums = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    private List<String> res;
    private StringBuilder str;

    //n表示几位数
    //示例：1、2、3、4...99
    public List<String> printNumbers(int n) {
        res = new ArrayList<>();
        str = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            dfs(0, i);
        }
        return res;
    }

    /**
     * x表示当前是第几位，len表示有多少位
     * @param x
     * @param len
     */
    public void dfs(int x, int len) {
        if (x == len) {
            res.add(str.toString());
            return;
        }
        int start = x == 0 ? 1 : 0;
        for (int i = start; i < nums.length; i++) {
            str.append(nums[i]);
            dfs(x + 1, len);
            str.deleteCharAt(str.length() - 1);
        }
    }
    
    public static void main(String[] args) {
        Test test = new Test();
        List<String> s = test.printNumbers(5);
        System.out.println(s);
    }
}

image-20220808234304916

剑指 Offer 12. 矩阵中的路径【简单】

题目链接：剑指 Offer 12. 矩阵中的路径

题目内容：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路：

1、dfs+回溯+剪枝

复杂度分析：

  • 时间复杂度O(3^k^.MN)，3指的就是上下左右四个方向舍去回头方向，k为字符串长度，MN就是矩阵数量。
  • 空间复杂度：O(K)，递归深度不会超过k长度。
class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null) {
            return false;
        }
        char[] wordArr = word.toCharArray();
        //所有位置都可以看作是起点
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (dfs(board, wordArr, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        //边界条件，以及当前是否已经访问过
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] != word[k]) {
            return false;
        }
        //若是此时k已经到末尾了,表示符合条件
        if (k == word.length - 1){
            return true;
        }
        //覆盖当前的元素
        board[i][j] = '1';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        //回溯（能够从第一个if中过去的，肯定是board[i][j] = word[k]的，所以这里可以直接进行回溯）
        board[i][j] = word[k];
        return res;
    }
}

剑指 Offer 64. 求1+2+…+n【中等】

题目链接：剑指 Offer 64. 求1+2+…+n

题目内容：求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路：数学运算或者递归。

1、乘除法

复杂度分析：时间复杂度O(n)、空间复杂度O(1)

class Solution {
    public int sumNums(int n) {
        return (n + 1) * n / 2;
    }
}

2、递归

复杂度分析：时间复杂度O(n)、空间复杂度O(n)

递归的话需要你判断得到一个出口，又题目不给你if，如何解决？

①通过异常捕捉

class Solution {
    public int sumNums(int n) {
        try {
            int a = 1 / n;
        }catch(Exception e) {
            return 0;
        }
        return n + sumNums(n - 1);
    }
}

②通过与运算

class Solution {
    public int sumNums(int n) {
        //将n > 1作为放行条件，利用&运算来控制右边是否执行，当n=0时，此时会直接返回n
        boolean flag = n > 1 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

剑指 Offer 49. 丑数【中等】

题目链接：剑指 Offer 49. 丑数

题目内容：我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

思路：

1、动态规划

状态定义：dp[i]，i表示第i+1的丑数值
转移方程：dp[i]=min(dp[a]×2,dp[b]×3,dp[c]×5) 
	需要维护a、b、c三个索引
初始化状态：dp[0]=1
返回值：dp[n-1]

复杂度分析：时间复杂度O(n)、空间复杂度O(1)

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        //初始化
        dp[0] = 1;
        //实际上过程中枚举了所有的丑数情况
        for (int i = 1; i < n; i++) {
            int num2 = dp[a] * 2, num3 = dp[b] * 3, num5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            //计数+1（只要是相等数的情况，那么就需要加一，防止出现重复）
            if (dp[i] == num2) {
                a++;
            }
            if (dp[i] == num3) {
                b++;
            }
            if (dp[i] == num5){
                c++;
            }
        }
        return dp[n - 1];
    }
}

牛客网

斐波那契数列【入门】

题目链接：斐波那契数列

题目内容：大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。斐波那契数列是一个满足 fib(x)=\left{ \begin{array}{rcl} 1 & {x=1,2}\ fib(x-1)+fib(x-2) &{x>2}\ \end{array} \right.fib(x)={1fib(x−1)+fib(x−2)x=1,2x>2 的数列数据范围：1\leq n\leq 401≤n≤40 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) ，本题也有时间复杂度 O(logn)O(log**n) 的解法

思路1：迭代

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
public class Solution {
    public int Fibonacci(int n) {
        int ans = 1;
        int a = 1;
        int b = 1;
        for (int i = 2;i < n;i++) {
            ans = a + b;
            a = b;
            b = ans;
        }
        return ans;
    }
}

没有重复项数字的全排列【中等】

题目链接：没有重复项数字的全排列

题目内容：给出一组数字，返回该组数字的所有排列

思路1：全排列递归方案。

复杂度分析：

  • 时间复杂度:![img](https://www.nowcoder.com/equation?tex=O(n * n!)&preview=true)。n为num数组的长度。
  • 空间复杂度:img。返回的结果的空间。
import java.util.*;

public class Solution {
    
    //结果集
    private ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        LinkedList<Integer> list = new LinkedList<>();
        recurison(num, list);
        return res;
    }
    
    public void recurison(int[] num, LinkedList<Integer> list) {
        //出口
        if (list.size() == num.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        //全排列方案列举
        for (int i = 0; i < num.length; i++) {
            //过滤掉重复项
            if (list.contains(num[i])) {
                continue;
            }
            list.add(num[i]);
            //递归处理
            recurison(num, list);
            //为了方便删除最后一个元素，所以选中LinkedList
            list.removeLast(); 
        }
    }
    
}

思路2（推荐）：优化思路1，其中的判断某个值在集合中是否存在，采用空间换时间的思路，使用一个visted数组来进行表示状态。

class Solution {

    //结果集
    private List<List<Integer>> res = new ArrayList<List<Integer>>();

    public List<List<Integer>> permute(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        recursion(nums, list, new boolean[nums.length]);
        return res;
    }

    public void recursion(int[] nums, ArrayList<Integer> list, boolean[] visited) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //优化处：使用一个boolean数组来表示该元素是否访问过状态
            if (visited[i]) {
                continue;
            }
            list.add(nums[i]);
            visited[i] = true;
            recursion(nums, list, visited);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }

}

有重复项数字的全排列【中等】

题目链接：有重复项数字的全排列

题目内容：给出一组可能包含重复项的数字，返回该数字的非重复排列。结果以字典升序排列。

思路1：在本章节牛客网题目1优化题解中修改两处即可解决

复杂度分析：

  • 时间复杂度:O(n×n!)，其中 n 为数组的长度。
  • 空间复杂度:O(n)。返回的结果。
import java.util.*;

public class Solution {
    
    //结果集
    private ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        //修改操作2：对nums排序
        Arrays.sort(nums);
        recursion(nums, list, new boolean[nums.length]);
        return res;
    }
    
    public void recursion(int[] nums, ArrayList<Integer> list, boolean[] visited) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //修改操作1：
            //i > 0 && nums[i] == nums[i - 1] && !visited[i]处理的是递归下去情况中出现重复的排列情况
            //举例：112   第一轮：112 121  第二轮的第一个数字，此时为1，visited[1]为false，此时重点来了看后面的条件，若是当前值与之前的相同并且前面的此时并没有访问过，那么跳过这个情况
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            list.add(nums[i]);
            visited[i] = true;
            recursion(nums, list, visited);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

岛屿数量【中等】

题目链接：岛屿数量

题目内容：给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

思路1：dfs，通过消减方法来解决，递归操作是将临近得上下左右1->0。

复杂度分析：

  • 时间复杂度：O(m*n)
  • 空间复杂度：O(m*n)
import java.util.*;


public class Solution {
    
    public void dfs(char[][] grid, int i, int j) {
        //进行1->0
        grid[i][j] = '0';
        //四个方法进行递归操作
        //上
        if (i - 1 >= 0 && grid[i - 1][j] == '1') {
            dfs(grid, i - 1, j);
        }
        //下
        if (i + 1 < grid.length && grid[i + 1][j] == '1') {
            dfs(grid, i + 1, j);
        }
        //左
        if (j - 1 >= 0 && grid[i][j - 1] == '1') {
            dfs(grid, i, j - 1);
        }
        //右
        if (j + 1 < grid[i].length && grid[i][j + 1] == '1') {
            dfs(grid, i, j + 1);
        }
    }
    
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    //思路：采用消减法
    public int solve (char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    //递归：消减
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
}

思路2：bfs，利用队列来进行推断周边是否为岛屿。

复杂度分析：

  • 时间复杂度：O(m*n)
  • 空间复杂度：O(min(m, n))
import java.util.*;


public class Solution {
    
    class Pos {
        public int i;
        public int j;
        public Pos(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    //bfs
    public int solve (char[][] grid) {
        int count = 0;
        //队列存储坐标
        Deque<Pos> queue = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    grid[i][j] = '0';
                    //将对应得坐标添加到队列中
                    queue.offer(new Pos(i , j));
                    while (!queue.isEmpty()) {
                        //获取到队列中得一个结点
                        Pos pos = queue.poll();
                        int x = pos.i;
                        int y = pos.j;
                        //四个方向来进行试探
                        //上
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                            grid[x - 1][y] = '0';
                            queue.offer(new Pos(x-1, y));
                        }
                        //下
                        if (x + 1 < grid.length && grid[x + 1][y] == '1') {
                            grid[x + 1][y] = '0';
                            queue.offer(new Pos(x+1, y));
                        }
                        //左
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                            grid[x][y - 1] = '0';
                            queue.offer(new Pos(x, y - 1));
                        }
                        //右
                        if (y + 1 < grid[i].length && grid[x][y + 1] == '1') {
                            grid[x][y + 1] = '0';
                            queue.offer(new Pos(x, y + 1));
                        }
                    }
                }
            }
        }
        return count;
    }
}

字符串的排列【中等】

牛客网代码不通过

题目链接：字符串的排列

题目内容：输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

dfs递归拼接：

import java.util.*;

public class Solution {
    
    private ArrayList<String> list = new ArrayList<>();
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        dfs(new StringBuilder(), chars, new boolean[str.length()]);
        return list;
    }
    
    public void dfs(StringBuilder builder, char[] chars, boolean visited[]) {
        if (builder.length() == chars.length) {
            list.add(builder.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (visited[i] || (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1])) {
                continue;
            }
            builder.append(chars[i]);
            visited[i] = true;
            dfs(builder, chars, visited);
            //回溯
            builder.deleteCharAt(builder.length() - 1);
            visited[i] = false;
        }
    }
    
}

swap交换方式：

import java.util.*;


public class Solution {
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        char[] ch = str.toCharArray();
        ArrayList<String> list = new ArrayList<>();
        fun(list, ch, 0);
        return list;
    }
    
    public void fun(ArrayList<String> list, char[] chars,int index) {
        if (index == chars.length) {
            String str = new String(chars);
            if (!list.contains(str)) {
                list.add(str);
            }
        }else {
            for (int j = index; j < chars.length; j++) {
                swap(chars, index, j);
                fun(list, chars, index + 1);
                swap(chars, index, j);
            }
        }
    }
    
    public void swap(char[] chars, int i, int j) {
        if (i != j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    }
    
}

优化算法：

1、通过使用剪枝来进行删减掉重复得字符，如下。

image-20220717160503662

class Solution {
    public String[] permutation(String s) {
        char[] ch = s.toCharArray();
        ArrayList<String> list = new ArrayList<>();
        fun(list, ch, 0);
        return (String[])list.toArray(new String[0]);
    }

    public void fun(ArrayList<String> list, char[] chars,int index) {
        if (index == chars.length) {
            list.add(new String(chars));
        }
        for (int i = index; i < chars.length; i++) {
            boolean flag = true;
            //剪枝 （帅死了）
            for (int j = index; j < i; j++) {
                //含义：若是之前交换过得元素与当前交换得元素值若是一致，那么没有必要了
                if (chars[j] == chars[i]) {
                    flag = false;
                }
            }
            if (flag) {
                swap(chars, index, i);
                fun(list, chars, index + 1);
                swap(chars, index, i);
            }
        }
    }
    
    public void swap(char[] chars, int i, int j) {
        if (i != j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    }
}

2、优化点，可以将list集合优化为set。

括号生成【中等】

学习：leetcode题解

题目链接：22. 括号生成

题目内容：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

说明：递归的条件主要是围绕这括号的一个数量来进行决定的，不断往下递归，最终出口：left == n && right == n

image-20220722110013225

思路1：递归+回溯。【推荐】

  • 通过利用StringBuilder来进行拼接，不会造成频繁创建字符串的情况。

复杂度分析：

  • 时间复杂度：O(2^n^)
  • 空间复杂度：O(n)
import java.util.*;


public class Solution {
    
    private ArrayList<String> res = new ArrayList<>();
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        recursion(new StringBuilder(), 0, 0, n);
        return res;
    }
    
    public void recursion (StringBuilder str, int left, int right, int n) {
        //筛选条件
        if (left > n || right > n || left < right) {
            return;
        }
        //递归出口条件
        if (left == n && right == n) {
            res.add(str.toString());
            return;
        }
        //递归+回溯
        //递归(
        str.append('(');
        recursion(str, left + 1, right, n);
        str.deleteCharAt(str.length() - 1);
        //添加右边)
        str.append(')');
        recursion(str, left, right + 1, n);
        str.deleteCharAt(str.length() - 1);
    }
    
}

思路2：直接递归，无回溯。使用的是String字符串。

  • 额外说明：在使用条件进行递归时，在最后进行回溯会出现问题！

复杂度分析：

  • 时间复杂度：O(2^n^)
  • 空间复杂度：O(n*2^n^)
import java.util.*;


public class Solution {
    
    private ArrayList<String> res = new ArrayList<>();
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        recursion("", 0, 0, n);
        return res;
    }
    
    public void recursion (String str, int left, int right, int n) {
        //递归出口条件
        if (left == n && right == n) {
            res.add(str);
            return;
        }
        //递归(
        if (left < n) {
            recursion(str + '(', left + 1, right, n);
        }
        if (right < n && left > right) {
            recursion(str + ')', left, right + 1, n);
        }
    }
    
}

N皇后问题【中等】

题目链接：N皇后问题

题目内容：N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，要求：任何两个皇后不同行，不同列也不在同一条斜线上，求给一个整数 n ，返回 n 皇后的摆法数。

思路1：递归，并利用集合容器来进行解决。

复杂度分析：

  • 时间复杂度：O(n!)
  • 空间复杂度：O(n)
import java.util.*;


public class Solution {
    
    private int result = 0;
    //使用三个容器
    Set<Integer> columns = new HashSet<>();//存储行号
    Set<Integer> posSet = new HashSet<>();//存储正对角线
    Set<Integer> conSet = new HashSet<>();//存储斜对角线
    
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    public int Nqueen (int n) {
        compute(0, n);
        return result;
    }
    
    //i表示行号、n表示边长
    //j就是列号，i-j就是斜号，i+j就是正斜
    public void compute(int i, int n) {
        if (i == n) {
            result++;
            return;
        }
        //全排列
        for (int j = 0; j < n; j++) {
            if (columns.contains(j) || posSet.contains(i - j) || conSet.contains(i + j)) {
                continue;
            }
            columns.add(j);
            posSet.add(i - j);
            conSet.add(i + j);
            //递归
            compute(i + 1, n);
            columns.remove(j);
            posSet.remove(i - j);
            conSet.remove(i + j);
        }
    }
    
}

思路2【推荐】：通过使用数组来进行解决，这里使用三个数组，同样分别对应上方的集合容器。

复杂度分析：

  • 时间复杂度：O(n!)
  • 空间复杂度：O(n)
import java.util.*;


public class Solution {
    
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    private int result = 0;
    //使用三个容器
    private boolean[] columns;
    private boolean[] posSet;//正斜线
    private boolean[] conSet;//反斜线
    
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    public int Nqueen (int n) {
        this.columns = new boolean[n];
        //开辟两倍的空间，足以为[0, 2 * n - 1]
        this.posSet = new boolean[n * 2];
        this.conSet = new boolean[n * 2];
        compute(0, n);
        return result;
    }
    
    //i表示行号、n表示边长
    //j就是列号，i-j就是斜号，i+j就是正斜
    public void compute(int i, int n) {
        if (i == n) {
            result++;
            return;
        }
        //全排列
        for (int j = 0; j < n; j++) {
            //注意是：j - i + n
            if (!columns[j] && !posSet[j - i + n] && !conSet[i + j]) {
                columns[j] = posSet[j - i + n] = conSet[i + j] =  true;
                compute(i + 1, n);
                //回溯
                columns[j] = posSet[j - i + n] = conSet[i + j] = false;
            }
        }
    }
}

矩阵中的最长自增路径【中等】

视频：LeetCode每日打卡.329.矩阵中的最长递增路径：特别清晰，看一遍就懂。

题目链接：矩阵最长递增路径

题目内容：给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。 你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。并输出这条最长路径的长度。

思路1：采用记忆化dp+dfs来实现自增路径。

  • dp中记录的是上下左右能够走的路径最大值。
import java.util.*;


public class Solution {
    
    private int[][] dp;
    private int res;
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    //核心：找到一条递增的路线，记录最长
    public int solve (int[][] matrix) {
        //初始化默认为0
        this.dp = new int[matrix.length][matrix.length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                res = Math.max(res, dfs(i, j, matrix, Integer.MIN_VALUE));
            }
        }
        return res;
    }
    
    public int dfs(int i, int j, int[][] matrix, int prev) {
        //越界情况
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[i].length) {
            return 0;
        }
        //若是当前值<prev值的话
        if (prev >= matrix[i][j]) {
            return 0;
        }
        //若是当前dp不为0时，直接返回
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        //当前未进行搜索情况
        dp[i][j] = 1;
        int up = dfs(i - 1, j, matrix, matrix[i][j]);
        int down = dfs(i + 1, j, matrix, matrix[i][j]);
        int left = dfs(i, j - 1, matrix, matrix[i][j]);
        int right = dfs(i, j + 1, matrix, matrix[i][j]);
        //拿的是当前的dp值以及上下左右能够递增的最大值来进行比较
        dp[i][j] = Math.max(dp[i][j], Math.max(Math.max(up, down), Math.max(left, right)) + 1);
        return dp[i][j];
    }
    
}

leetcode

79.单词搜索【中等】

题目链接：79. 单词搜索

题目内容：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路：

1、dfs深搜+回溯+剪枝

[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]] ["oath","pea","eat","rain"]

复杂度分析：时间复杂度O(m.n.3^L^)，其中mn指的是对应矩阵的长宽，L指的是单词的长度；空间复杂度O(1)

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] arr = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (dfs(board, arr, i, j, arr.length)) {
                    return true;
                }
            }
        }
        return false;
    }

    //进行深搜，限制的包含有字幕的长度
    public boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (k == 0) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length ||  board[i][j] != word[word.length - k]) {
            return false;
        }
        //进行dfs
        board[i][j] = '1';
        //进行上下左右
        boolean res = dfs(board, word, i + 1, j, k - 1) || dfs(board, word, i - 1, j, k - 1) || 
                      dfs(board, word, i, j - 1, k - 1) || dfs(board, word, i, j + 1, k - 1);
        board[i][j] = word[word.length - k];
        return res;
    }
}

image-20220816170642146

212. 单词搜索 II【困难】

题目链接：212. 单词搜索 II

题目内容：给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用

思路：

1、暴力法，dfs+回溯+剪枝。在中间使用了两个剪枝才勉强ac，不过最终的时间效率特别低。

复杂度分析：时间复杂度O(mn4^l^.s)，s指的是单词数量；空间复杂度O(n)

class Solution {

    //水平垂直相邻(上下左右)
    public List<String> findWords(char[][] board, String[] words) {
        List<String> list = new ArrayList();
        int count = board.length * board[0].length;
        for (int i = 0; i < words.length; i++) {
            //剪枝2：单词的字符数量>矩形框中所有的字符
            if (words[i].length() <= count) {
                list.add(words[i]);   
            }
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                for (int k = list.size() - 1; k >= 0; k--) {
                    String word = list.get(k);
                    //剪枝1：若是当前单词中没有出现该字符则不进行dfs
                    if (!word.contains(board[i][j] + "")) {
                        continue;
                    }
                    char[] arr = word.toCharArray();
                    //遍历四个字母
                    if (dfs(board, arr, i, j, arr.length)) {
                        list.remove(word);
                        res.add(word);
                    }
                }
            }
        }
        return res;
    }

    //进行深搜，限制的包含有字幕的长度
    public boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (k == 0) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length ||  board[i][j] != word[word.length - k]) {
            return false;
        }
        //进行dfs
        board[i][j] = '.';
        //进行上下左右
        boolean res = dfs(board, word, i + 1, j, k - 1) || dfs(board, word, i - 1, j, k - 1) || 
                      dfs(board, word, i, j - 1, k - 1) || dfs(board, word, i, j + 1, k - 1);
        board[i][j] = word[word.length - k];
        return res;
    }
}

image-20220816194533858

对其优化，同样也是暴力，只不过在这里使用了set来存储元素，设置递归深度最大为10，然后在每次取结果时来进行判断是否存在：

  • 时间复杂度O(mn4^l^)
class Solution {

    Set<String> set = new HashSet<>();
    List<String> ans = new ArrayList<>();
    char[][] board;
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int n, m;
    boolean[][] vis = new boolean[15][15];

    public List<String> findWords(char[][] _board, String[] words) {
        board = _board;
        m = board.length; n = board[0].length;
        int count = m * n;
        //所有单词添加到set集合中
        for (String w : words) set.add(w);
        for (int i = 0; i < words.length; i++) {
            set.add(words[i]);   
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vis[i][j] = true;
                sb.append(board[i][j]);
                dfs(i, j, sb);
                vis[i][j] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return ans;
    }
    void dfs(int i, int j, StringBuilder sb) {
        if (sb.length() > 10) return ;//深度>10直接结束
        if (set.contains(sb.toString())) { 
            ans.add(sb.toString());
            set.remove(sb.toString());
        }
        for (int[] d : dirs) {
            int dx = i + d[0], dy = j + d[1];
            if (dx < 0 || dx >= m || dy < 0 || dy >= n) continue;
            if (vis[dx][dy]) continue;
            vis[dx][dy] = true;
            sb.append(board[dx][dy]);
            dfs(dx, dy, sb);
            vis[dx][dy] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

image-20220816194453703

2、前缀树+dfs【最优解】：

复杂度分析：时间复杂度O(m×n×3^l^)；空间复杂度O(k.l)

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {

    class TrieNode {
        boolean isEnd = false;
        TrieNode[] children = new TrieNode[26];
    }

    //定义方向
    int[][] directions = {{-1, 0}, {1, 0}, {0, - 1}, {0, 1}};

    public List<String> findWords(char[][] board, String[] words) {
        //构建前缀树
        TrieNode root = buildTrieTree(words);
        //构建结果集
        List<String> result = new ArrayList<>();
        StringBuilder str = new StringBuilder();
        //每个结点来做遍历操作
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                dfs(board, i, j, str, result, root, root);
            }
        }
        return result;
    }

    /**
     * 构建前缀树
     * @param words
     * @return
     */
    private TrieNode buildTrieTree(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            char[] arr = word.toCharArray();
            TrieNode cur = root;
            for (int i = 0; i < arr.length; i++) {
                if (cur.children[arr[i] - 'a'] == null) {
                    cur.children[arr[i] - 'a'] = new TrieNode();
                }
                cur = cur.children[arr[i] - 'a'];
            }
            //单词的末尾要进行标识
            cur.isEnd = true;
        }
        return root;
    }

    /**
     * 在前缀树中删除某个单词
     * @param root
     * @param word
     * @return
     */
    private void delete(TrieNode root, String word) {
        delete(root, word, 0);
    }

    //递归操作删除（因为前缀树的深度未知）
    private boolean delete(TrieNode root, String word, int i) {
        //递归到最后一层
        //极端情况删除的是dog，实际上还有dogs，那么此时我们只需要对这个g的标志符号去除掉即可
        if (i == word.length() - 1) {
            //例如dog，到了最后一个结点g，一定要预防dogs类似情况，也就是g后面是否有孩子结点
            //拿到对应的结点
            TrieNode curr = root.children[word.charAt(i) - 'a'];
            //若是有孩子结点
            if (hasChildren(curr)) {
                curr.isEnd = false;
                return false;
            }else {
                root.children[word.charAt(i) - 'a'] = null;
                return true;
            }
        }else {
            //这是最底部的上面一个个结点，例如dogs，中的g、o、d，不仅仅要考虑下层情况还要考虑当前的字符结点是否是单词以及是否有孩子结点
            if (delete(root.children[word.charAt(i) - 'a'], word, i + 1)  //若是下一级结点返回的是true才允许被删除
                && !root.children[word.charAt(i) - 'a'].isEnd  //当前结点不是单词
                && !hasChildren(root.children[word.charAt(i) - 'a'])  //当前的结点的后缀没有结点存在
            ) {
                //真正执行删除操作
                root.children[word.charAt(i) - 'a'] = null;
                return true;
            }
            return false;
        }
    }

    //判断是否有孩子
    private boolean hasChildren(TrieNode root) {
        for (TrieNode node : root.children) {
            if (node != null) {
                return true;
            }
        }
        return false;
    }

    /**
     * dfs深搜
     */
    public void dfs(char[][] board, int i, int j, StringBuilder str, List<String> result, TrieNode root, TrieNode node) {
        //前置过滤
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||  //边界情况
                board[i][j] == '#' ||  //没有重复访问过
                node == null || node.children[board[i][j] - 'a'] == null  //对应递归的前缀树结点是否为空以及孩子结点是否存在对应的字符
        ){
            return;
        }

        char ch = board[i][j];
        //符合条件，并且当前结点中是有对应单词的
        //添加到对应的结果集中
        str.append(ch);
        //若是当前某个字符结点是单词末尾，此时需要进行添加到结果集
        if (node.children[board[i][j] - 'a'].isEnd) {
            String word = str.toString();
            //添加到结果集中
            result.add(word);
            //从前缀树中删除该单词
            delete(root, word);
        }

        //字符数组来标识已经访问过的
        board[i][j] = '#';

        //进行dfs
        for (int k = 0; k < directions.length; k++) {
            int _i = i + directions[k][0], _j = j + directions[k][1];
            //注意这里使用的结点要使用上面提前接收board[i][j]的变量ch
            dfs(board, _i, _j, str, result, root, node.children[ch - 'a']);
        }

        //字符数组重新进行标识
        board[i][j] = ch;

        //回溯
        str.deleteCharAt(str.length() - 1);
    }
}

image-20220816221259907

面试题13. 机器人的运动范围【中等】

题目链接：面试题13. 机器人的运动范围

题目内容：地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

思路：数位和计算（注意题目要求为行坐标和列坐标的数位之和大于k）以及递归

1、dfs+数位和计算

class Solution {

    private int res = 0;

    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        dfs(visited, 0, 0, k);
        return res;
    }

    public void dfs(boolean[][] visited, int i, int j,int k) {
        //越界情况
        if (i == visited.length || j == visited[i].length) {
            return;
        }
        //数位和计算以及剪枝
        if ((sums(i) + sums(j)) > k || visited[i][j]) {
            return;
        }
        //若是该格子没有访问过计数+1
        if (!visited[i][j]) {
            this.res++;
            visited[i][j] = true;
        }
        dfs(visited, i + 1, j, k);
        dfs(visited, i, j + 1, k);
    }

    public int sums(int num) {
        int res = 0;
        while (num != 0) {
            res += num % 10;
            num = num / 10;
        }
        return res;
    }
}

17. 电话号码的字母组合【中等】

学习：leetcode题解

题目链接：17. 电话号码的字母组合

题目内容：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母

思路：

1、递归（dfs）

思路：由于循环的个数不确定，则需要使用递归来进行求解。

代码：时间复杂度O(3m×4n)、空间复杂度O(m+n)

class Solution {

    /**
     * 根据指定字符生成字符串
     * @param ch 数字字符
     * @return
     */
    public String generateNumtoString(char ch){
        String[] arr = new String[] {
            "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
        };
        if (ch - '2' <= arr.length){
            return arr[ch - '2'];
        }
        return null;
    }

    private List<String> letters = new ArrayList<>();


    /**
     * 全排列 ：abc、def、ghip
     * @param arr 数组集合
     * @param curIndex 当前要遍历的指定数组
     * @param curArrIndex 当前排列的个数
     * @param genStr 当前生成的字符串
     */
    public void quanpailie(String[] arr, int curIndex, int curArrIndex, String genStr){
        //生成每组的排列个数
        if(curArrIndex == arr.length){
            letters.add(genStr);
            return;
        }
        String curArr = arr[curIndex];//取得当前要遍历的数组
        String temp = genStr; //临时保存原先状态
        for (int i = 0; i < curArr.length(); i++) { //枚举所有情况
            genStr += curArr.charAt(i);
            quanpailie(arr,curIndex + 1, curArrIndex + 1, genStr);
            genStr = temp; //回溯
        }
    }

    public List<String> letterCombinations(String digits) {
        if (Objects.equals("",digits)){
            return new ArrayList<>();
        }
        String[] arrs = new String[digits.length()];
        for (int i = 0; i < digits.length(); i++) {
            arrs[i] = generateNumtoString(digits.charAt(i));
        }
        //使用全排列进行求解
        quanpailie(arrs,0, 0, "");
        return letters;
    }

}

image-20211208151438197

小优化：对于回溯操作的字符串替换使用StringBuilder，时间、空间效率大幅度提升！

public void quanpailie(String[] arr, int curIndex, int curArrIndex, StringBuilder str){
    ...
    for (int i = 0; i < curArr.length(); i++) { 
        str.append(curArr.charAt(i));
        ...
        str.deleteCharAt(curArrIndex);//回溯优化
    }
}

2、基于NO1优化（进行回溯）

思路：核心优化点就是在字符串回溯、拼接上

/**
     * 根据指定字符生成字符串
     * @param ch 数字字符
     * @return
     */
public String generateNumToStr(char ch){
    String[] arr = new String[] {
        "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
    };
    if (ch - '2' <= arr.length){
        return arr[ch - '2'];
    }
    return null;
}

private List<String> letters = new ArrayList<>();

/**
     * 全排列 ：abc、def、ghip
     * @param phones 电话数字映射的字符串数组
     * @param index 当前排列的数字位置
     * @param genStr 当前生成的字符串
     */
public void quanpailie(String[] phones, int index, StringBuilder genStr){
    //生成每组的排列个数
    if(index == phones.length){
        letters.add(genStr.toString());
        return;
    }
    String curArr = phones[index];//取得当前要遍历的数组
    for (int i = 0; i < curArr.length(); i++) { //枚举所有情况
        genStr.append(curArr.charAt(i));
        quanpailie(phones,index + 1, genStr);
        genStr.deleteCharAt(index);
    }
}

public List<String> letterCombinations(String digits) {
    if (Objects.equals("",digits)){
        return new ArrayList<>();
    }
    String[] arrs = new String[digits.length()];
    for (int i = 0; i < digits.length(); i++) {
        arrs[i] = generateNumToStr(digits.charAt(i));
    }
    //使用全排列进行求解
    quanpailie(arrs,0, new StringBuilder(""));
    return letters;
}

image-20211208153059789

78. 子集【中等】

学习：leetcode题解

题目链接：78. 子集

题目内容：

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

思路：

1、递归回溯

思路：在递归方法调用过程中使用一个begin来进行直接控制组合，整个结果集添加操作在方法一开始进行，添加新的子集在循环中进行！

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

    //nums = [1,2,3]  =》 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        if (nums.length == 0){
            return res;
        }
        recursion(nums,0, new ArrayList<>());
        return res;
    }

    /**
     * 回溯过程中记录节点
     * @param nums
     * @param begin
     * @param pre
     */
    public void recursion(int nums[],int begin,List<Integer> pre){
        res.add(new ArrayList<>(pre)); /集合的深拷贝
        for (int i = begin; i < nums.length; i++) {  //begin用于间接直接控制组合
            pre.add(nums[i]);
            recursion(nums,i + 1, pre);
            pre.remove(pre.size() - 1);
        }
    }
}

image-20211216083240202

46. 全排列【中等】

学习：回溯算法入门级详解 + 练习（持续更新）：讲的较详细推荐

题目链接：46. 全排列

题目内容：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路：

1、递归回溯

思路：根据题意画出对应回溯情况的二叉树，确定边界条件（出口）以及一些必要的辅助数组、集合等即可。

image-20211220163812224

所需要的一些必要条件如(对应该题)：出口（深度都为3），收集全排序的集合(res)，深搜+回溯产生出来的过程结果集（path），还有最核心的一个问题就是在进行深搜过程中如何排除掉已添加到path的某个结果值？可使用一个与nums数组同大小的状态数组来进行记录，在深搜过程中枚举判断即可！

  • 根据图来推出所需要的情况及条件，那么我们就可以来编写递归的函数方法了，对应参数也就是上面举出的。
public List<List<Integer>> permute(int[] nums) {
    //全排列结果集、一组结果集、标记访问数组（默认为false）
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] visitArr = new boolean[nums.length];
    recall(nums,path,0,visitArr,res);
    return res;
}

/**
     * 回溯求得全排列
     * @param nums 待全排列数据集集合
     * @param path 待添加入的一组数据
     * @param depth 深度
     * @param visitArr 标记是否访问数组
     * @param res 全排列结果集
     */
private void recall(int[] nums, List<Integer> path, int depth, boolean[] visitArr,
                    List<List<Integer>> res) {
    //出口条件，到达指定的深度结束
    if (depth == nums.length){
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        //若是没有访问过的情况
        if (!visitArr[i]){
            path.add(nums[i]);
            visitArr[i] = true;
            recall(nums,path,depth + 1,visitArr,res);
            //回溯
            path.remove(path.size() - 1);
            visitArr[i] = false;
        }
    }

}

image-20211220164336912

77. 组合【中等】

学习：leetcode题解、 代码随想录—第77题. 组合

题目链接：77. 组合

题目内容：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例 1：
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：
输入：n = 1, k = 1
输出：[[1]]

思路：

1、回溯+剪枝

思路：使用一个startIndex变量来进行调节范围，这里采用递归回溯的方法来进行组合。

代码：

//用于记录所有组合的列表
List<List<Integer>> result = new ArrayList<>();
//记录每个组合。(频繁添加、删除使用链表集合)
LinkedList<Integer> path = new LinkedList<>();

public List<List<Integer>> combine(int n, int k) {
    combineHelper(n, k, 1);
    return result;
}

/**
  * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
  * @param n 组合数的范围
  * @param k 组合数的数量
  * @param startIndex 用于记录本地递归集合中哪个值开始遍历
  */
private void combineHelper(int n, int k, int startIndex){
    //终止条件
    if(path.size() == k){ //这里用于限制组合数
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = startIndex; i <= n ; i++) {
        path.add(i);
        combineHelper(n,k,i+1);
        path.removeLast();//回溯：删除组合中的最后一个元素
    }
}

image-20211109200842856

上面的题解其实会有一些额外无意义的操作，例如n=4，k=4时，若是起始点为startIndex+1，之后的每组递归掉用其实都凑不齐4个，那么这些操作我们其实可以进行避免，也就是进行剪枝操作（避免递归调用）：

这里引用代码回想录题解的图（原图地址在右边文章链接里）：第77题. 组合

image-20211109222831974

将上面的第26行代码修改为：

//k - item.size()：等待组合的剩余数量
//n=4，k=2情况：对于上来第一波循环其范围则为  i<= 4-(2-0)+1，也就是i<=3，因为每组是2个，所以直接会将i=4的情况直接进行剪枝！
for (int i = startIndex; i <= n - (k - item.size()) + 1; i++) {

image-20211109223331009

51. N 皇后【困难，与牛客的7相同】

题目链接：51. N 皇后

题目内容：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

思路：采用数组来表示是否访问的状态。

class Solution {
    
    private int num = 0;

    public int totalNQueens(int n) {
        dfs(n, 0, new boolean[n], new boolean[n * 2], new boolean[n * 2]);
        return num;
    }

    //pos正、con：斜
    public void dfs(int n, int i, boolean[] columns, boolean pos[], boolean con[]) {
        if (i == n) {
            num++;
            return;
        }
        //全排列
        for (int j = 0; j < n; j++) {
            //  1 2 3     正：1(0,0)、5(1,1)、9(2,2)   2(0,1)、6(1,2)  3(0,2)  7(2,0)   j-i+n
            //  4 5 6     反：i+j
            //  7 8 9
            //只有当行、正斜、反斜方向都没有出现过时，才能够往下执行
            if (!columns[j] && !pos[j - i + n] && !con[i + j]) {
                columns[j] = pos[j - i + n] = con[i + j] = true;
                dfs(n, i + 1, columns, pos, con);
                columns[j] = pos[j - i + n] = con[i + j] = false;
            }
        }
    }

}
深度优先搜索广度优先搜索回溯分治剪枝

评论区请在客户端页面查看