每日一算法：深度优先算法

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。如其名，该算法深入到可能的分支上，直到目标节点被找到或者已经没有其他节点可以继续深入，此时算法回溯到上一节点，以探索未被遍历的路径。深度优先搜索是一个递归算法，它利用了后进先出的栈结构，在图的遍历中特别有效。

深度优先搜索的步骤：

1. 选择起点：从图中的某个顶点开始遍历。
2. 访问节点：访问当前节点。如果该节点是目标节点，则搜索成功，返回结果。
3. 递归遍历：对当前节点的所有未访问的相邻节点，采用深度优先搜索的方式递归遍历。
4. 回溯：当当前节点的所有相邻节点都被访问过，或者在相邻节点中没有找到目标节点，算法回溯到上一节点继续执行步骤3。
5. 结束条件：当所有节点都被访问过，或者找到目标节点，算法结束。

深度优先搜索的特点：

• 内存消耗较小：由于只需存储一条从根节点到当前节点的路径，因此相较于宽度优先搜索，其内存消耗通常较小。
• 找到解后停止：在搜索到解后，可以立即停止，不需要遍历整个图。
• 可能陷入死循环：在遍历图时，如果不记录已经访问过的节点，可能会陷入无限循环的情况。
• 不保证最短路径：深度优先搜索不保证找到的路径是最短的，它只是尽可能深地搜索图。

深度优先搜索的应用：

• 解决迷宫问题：可以用来寻找从起点到终点的路径。
• 排列组合问题：可以用来生成所有可能的排列组合。
• 拓扑排序：在有向无环图中，深度优先搜索可以用来进行拓扑排序。
• 解决连通性问题：可以用来判断两个节点是否连通，或者整个图的连通分量。

深度优先搜索的伪代码：

DFS(node):
  if node is visited:
    return

  mark node as visited
  for each node_neighbor in node.adjacent_nodes:
    if node_neighbor is not visited:
      DFS(node_neighbor)

在实际编程中，深度优先搜索可以通过递归实现，也可以通过显式地使用栈来实现非递归版本。递归版本的实现较为简洁，但在遇到深度非常大的图时可能会导致栈溢出。非递归版本虽然代码复杂一些，但可以避免栈溢出的问题。

案例

1.全排列

问题描述：

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

代码实现：

public static List<List<Integer>> res = new LinkedList<>();

    /**
     * 输入一组不重复的数字，返回它们的全排列
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }

    public static void backtrack(int[] nums, LinkedList<Integer> track) {
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (track.contains(num)) {
                continue;
            }
            track.add(num);
            backtrack(nums, track);
            track.removeLast();
        }
    }

2.N皇后问题

问题描述：

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

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

代码实现：

public static List<String[][]> result = new LinkedList<>();

    /**
     * N皇后问题
     * 如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
     *
     * @param n 皇后个数
     * @return 满足条件的所有方式
     */
    public static List<String[][]> solveNQueens(int n) {


        String[][] strings = new String[n][n];

        Arrays.fill(strings, ".");

        backtrack(strings, 0);

        return result;
    }

    public static void backtrack(String[][] strings, int i) {

        if (i >= strings.length) {
            result.add(strings);
            return;
        }

        for (int j = 0; j < strings.length; j++) {
            if (!isValid(strings, i, j)) {
                continue;
            }
            strings[i][j] = "Q";
            backtrack(strings, i + 1);
            strings[i][j] = ".";
        }

    }

    /**
     * i行j列放置皇后是否满足要求
     * @param strings 棋盘布局
     * @param i 行
     * @param j 列
     * @return 是否满足要求
     */
    public static boolean isValid(String[][] strings, int i, int j) {
        //判断同一行是否已经有
        for (int k = 0; k < i; k++) {
            if ("Q".equals(strings[i][k])) {
                return false;
            }
        }
        //判断左上方是否有
        for (int m = i - 1, n = j - 1; m >= 0 && n >= 0; m--, n--) {
            if ("Q".equals(strings[m][n])) {
                return false;
            }
        }
        //判断右上方是否有
        for (int m = i - 1, n = j + 1; m >= 0 && n <= j; m--, n++) {
            if ("Q".equals(strings[m][n])) {
                return false;
            }
        }
        return true;
    }

3.子集问题

问题描述：

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

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

代码实现：

public static List<List<Integer>> res2 = new LinkedList<>();

    /**
     * 子集问题
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     *
     * @param nums 数组
     * @return 所有可能的子集
     */
    public static List<List<Integer>> subsets(int[] nums) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, 0, track);
        return res2;
    }

    public static void backtrack(int[] nums, int start, LinkedList<Integer> track) {

        res2.add(new LinkedList<>(track));

        for (int i = start; i < nums.length; i++) {
            track.add(nums[i]);
            backtrack(nums, i + 1, track);
            track.removeLast();
        }

    }

4.组合问题

问题描述：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合

代码实现：

public static List<List<Integer>> res3 = new LinkedList<>();

    /**
     * 组合问题
     * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     * @param n
     * @param k
     * @return 所有可能的组合
     */
    public static List<List<Integer>> combine(int n, int k) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(n, 1, k, track);
        return res3;
    }

    public static void backtrack(int n, int start, int k, LinkedList<Integer> track) {

        if (track.size() == k) {
            res3.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i <= n; i++) {
            track.add(i);
            backtrack(n, i + 1, k, track);
            track.removeLast();
        }

    }