【数据结构与算法】之回溯、滑动窗口、分治算法经典问题

前言

本文为 【数据结构与算法】回溯、滑动窗口、分治算法 相关经典问题分享~，下边将对 回溯算法（包括全排列问题、N皇后问题），滑动窗口算法，分值算法（包括归并排序、快速排序）等进行详尽介绍~

📌博主主页：小新要变强 的主页
👉Java全栈学习路线可参考：【Java全栈学习路线】最全的Java学习路线及知识清单，Java自学方向指引，内含最全Java全栈学习技术清单~
👉算法刷题路线可参考：算法刷题路线总结与相关资料分享，内含最详尽的算法刷题路线指南及相关资料分享~
👉Java微服务开源项目可参考：企业级Java微服务开源项目（开源框架，用于学习、毕设、公司项目、私活等，减少开发工作，让您只关注业务！）

---

目录

一、回溯算法

回溯算法要做的事情很基础，就是穷举，可以说就是暴力穷举。解决回溯问题，实际上就是对一个决策树的遍历过程。回溯，我们可以这么理解，比如我们走迷宫，沿着一条路，走到底发现是思路，就要回到原来的出发点，再次选择一条新的路劲，其实这就是回溯。

在回溯的过程中，需要注意以下几点：

• （1）路径
• （2）选择的列表
• （3）结束条件

1️⃣全排列问题

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

示例 1：
输入： nums = [1,2,3] ； 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入： nums = [0,1] ；输出：[[0,1],[1,0]]

示例 3：
输入： nums = [1] ； 输出： [[1]]

方法签名： List> permute(int[] nums)

代码如下：

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> permute = solution.permute(new int[]{2, 4, 5, 6});
        System.out.println(permute);
    }
    
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        // 定义数组的长度
        int n = nums.length;
        // 定义一个栈用来存放数据，使用队列，集合也行
        Deque<Integer> deque = new ArrayDeque<>();
        // 用来保存一个数字有没有使用过
        boolean[] used = new boolean[n];

        backtrack(n, nums, res, 0,deque,used);

        return res;
    }

    public void backtrack(int n, int[] nums, List<List<Integer>> res, int first, Deque<Integer> deque, boolean[] used) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<>(deque));
            return;
        }
        for (int i = 0; i < n; i++) {
            // 已经使用过的就不管了
            if(used[i]){
                continue;
            }
            // 给栈中添加元素
            deque.addLast(nums[i]);
            used[i] = true;
            // 继续递归填下一个数
            backtrack(n, nums, res, first + 1,deque,used);
            // 撤销状态
            deque.removeLast();
            used[i] = false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2️⃣N皇后问题

• n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
• 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
• 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

代码如下：

public class Find8Queen {

    public static void main(String[] args) {
        Find8Queen find8Queen = new Find8Queen();
        find8Queen.solveNQueens(4);
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        check(0, new int[n], res);
        System.out.println(res);
        return res;
    }

    /**
     * 该方法用来检测当前列放置的queen，是否能满足条件
     *
     * @param current 当前列
     * @param queens  保存满足条件的一种情况的数组
     * @param res     结果
     */
    private void check(int current, int[] queens, List<List<String>> res) {
        // 已经试探到了最后一列了
        if (current == queens.length) {
            // 生成改种情况的棋牌，每个棋盘都是一个List [.Q.., ...Q, Q..., ..Q.]
            List<String> board = generateBoard(queens);
            // 将棋盘加入结果集当中
            res.add(board);
            return;
        }
        for (int i = 0; i < queens.length; i++) {
            // 一个一个的放皇后去尝试，
            queens[current] = i;
            // 检查这个皇后是否满足条件，行、列、斜线都没有
            // 如果满足条件，就结束了，否则回溯
            if (judge(current, queens)) {
                check(current + 1, queens, res);
            }
        }
    }

    /**
     * @param n       当前列
     * @param queens 当前情况的  [1,3,0.2]  
     * @return       是否满足条件
     */
    private boolean judge(int n, int[] queens) {

        // n代表要检验的列 i代表每一列
        for (int i = 0; i < n; i++) {
            // 同一行: 不需要判断
            // 同一列：queens[i] == queens[n]，过一遍看看有没有
            // 统一斜线： Math.abs(n-i) == Math.abs(queens[n] - queens[i])
            if (queens[i] == queens[n] || Math.abs(n - i) == Math.abs(queens[n] - queens[i])) {
                return false;
            }
        }
        return true;
    }

    // 根据结果生成棋盘 [1,3] 第一行第一个，第二行第三个
    public List<String> generateBoard(int[] queens) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < queens.length; i++) {
            char[] row = new char[queens.length];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';

            board.add(new String(row));
        }
        return board;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

二、滑动窗口

给你两个字符串S和T，请在S中找到包含T中全部字母的最短子串。如果S中没有这样一个子串，则返回空，如果存在这样一个子串，则可以认为答案是唯一的

比如： 输入 “ABCDEFGHIG” T=“CGI” 应该返回 “CDEFGHI”

这个题目是可以进行暴力破解的，但是时间复杂度太高，我们需要使用一些更加优雅的解决方案：

【滑动窗口】 的思路是这个样子的：

• （1）我们可以使用双指针中的左右指针技巧，初始化 left = right = 0，把索引【左闭右开）称之为一个窗口；
• （2）我们可以不断的增加right指针扩大窗口[left,right）,直至窗口中的字符串满足要求；
• （3）此时我们在不断的缩小left，同时，每次增加left，都要更新一轮结果；
• （4）重复以上步骤，直至left到达S的尽头。

暴力破解代码如下：

public class SildingWindow {

    public static String minWindow(String s, String t) {
        // 排除一些特殊情况
        if(s == null || t == null || "".equals(s) || "".equals(t) || t.length() > s.length()){
            return "";
        }
        if (s.equals(t)) return s;

        // 将字符串转化成字符数组方便操作
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();

        // 定义两个指针，空来控制范围 [left,right)
        int left = 0,right = 1;

        // 定义保存结果的变量
        int offset = 0,minLen = Integer.MAX_VALUE;

        // 核心的迭代逻辑
        while (left < charS.length){
            while (right < charS.length + 1){
                // 检查left和right之间的字符是否满足条件
                if(check(charS,left,right,charT)){
                    if(minLen > right - left){
                        minLen = right - left;
                        offset = left;
                    }
                }
                right++;
            }
            left++;
            right = left+1;
        }

        return new String(charS,offset,minLen == Integer.MAX_VALUE ? 0: minLen );
    }

    private static boolean check(char[] charS, int left, int right, char[] charT) {
        // 特殊情况
        if(right - left < charT.length){
            return false;
        }

        // 转化charT中的每个字符出现的次数一定小于等于charS中对应字符的次数
        int[] numsS = new int[128];
        int[] numsT = new int[128];

        for (int i = left; i < right; i++) {
            numsS[charS[i]]++;
            if(i-left < charT.length){
                numsT[charT[i-left]]++;
            }
        }

        for (int i = 0; i < numsT.length; i++) {
            if(numsS[i] < numsT[i]){
                return false;
            }
        }

        return true;

    }

    public static void main(String[] args) {
        System.out.println(minWindow("a","a"));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

滑动窗口解法代码如下：

public class SildingWindow2 {

    public static String minWindow(String s, String t) {
        // 排除一些特殊情况
        if(s == null || t == null || "".equals(s) || "".equals(t) || t.length() > s.length()){
            return "";
        }
        if (s.equals(t)) return s;

        // 将字符串转化成字符数组方便操作
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();

        // 定义两个指针，空来控制范围 [left,right)
        int left = 0,right = 1;

        // 定义保存结果的变量
        int offset = 0,minLen = Integer.MAX_VALUE;

        //
        // 转化charT中的每个字符出现的次数一定小于等于charS中对应字符的次数
        int[] numsS = new int[128];
        int[] numsT = new int[128];

        char currentWord = 128;
        boolean flag = false;

        for (int i = 0; i < charT.length; i++) {
            numsT[charT[i]]++;
        }

        // 核心的迭代逻辑
        while (left < charS.length && right <= charS.length) {
            while (right < charS.length + 1) {
                numsS[charS[right - 1]]++;
                if(flag && charS[right-1] != currentWord){
                    right++;
                    continue;
                }

                // 检查left和right之间的字符是否满足条件
                // 如果满足条件，1、记录最优解，2、右指针暂定
                if (right-left >= charT.length && check(numsS, numsT)) {
                    // 右指针如果满足条件，左指针开始走
                    while (left < right) {
                        if (check(numsS, numsT)) {
                            if (minLen > right - left) {
                                minLen = right - left;
                                offset = left;
                            }
                            numsS[charS[left]]--;
                            currentWord = charS[left];
                            left++;
                        } else {
                            flag = true;
                            break;
                        }
                    }
                    numsS[charS[right - 1]]--;
                    break;
                }
                right++;
            }
        }

        return new String(charS,offset,minLen == Integer.MAX_VALUE ? 0: minLen );
    }

    private static boolean check(int[] numsS, int[] numsT) {

        for (int i = 0; i < numsT.length; i++) {
            if(numsS[i] < numsT[i]){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(minWindow("DSACDFESDECDS","ECDF"));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

性能分析 ：

• 时间复杂度： 最坏情况下左右指针对 s 的每个元素各遍历一遍，哈希表中对 s 中的每个元素各插入、删除一次，对 t 中的元素各插入一次。每次检查是否可行会遍历整个 t 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 C，则渐进时间复杂度为： $$O(C\cdot |s|+|t|)$$
• 空间复杂度： 这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 C ，则渐进空间复杂度为：$$O(C)$$

三、分治思想

1️⃣归并排序

归并排序是一种稳定的排序方法，它也是一种十分高效的排序，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。

归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n·logn）的时间复杂度。代价是需要额外的内存空间。

代码如下：

public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int []arr){
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int []temp = new int[arr.length];
        sort(arr,0,arr.length-1,temp);
    }


    // 核心的递归方法
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left < right){
            int mid = (left+right)/2;
            //左边归并排序，使得左子序列有序
            sort(arr,left,mid,temp);
            //右边归并排序，使得右子序列有序
            sort(arr,mid+1,right,temp);
            //将两个有序子数组合并操作
            merge(arr,left,mid,right,temp);
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left; //左序列指针
        int j = mid+1; //右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        //将左边剩余元素填充进temp中
        while(i<=mid){
            temp[t++] = arr[i++];
        }
        //将右序列剩余元素填充进temp中
        while(j<=right){
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

2️⃣快速排序

快速排序同样使用分治法来把一个串（list）分为两个子串（sub-lists），然后分别进行排序。具体算法描述如下：

• 从数组中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后:");
        for (int i : arr) {
            System.out.println(i);
        }
    }

    private static void quickSort(int[] arr, int low, int high) {

        if (low >= high) {
        	return;
        }
        // 找寻排序后的基准数据所处的正确索引
        int index = getIndex(arr, low, high);

        // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
        // quickSort(arr, 0, index - 1); 之前的版本，这种姿势有很大的性能问题，谢谢大家的建议
        quickSort(arr, low, index - 1);
        quickSort(arr, index + 1, high);     
    }

    private static int getIndex(int[] arr, int low, int high) {
        // 基准数据
        int pivot = arr[low];
        while (low < high) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            // 如果队尾元素小于pivot了,需要将其赋值给low
            arr[low] = arr[high];
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            // 当队首元素大于pivot时,需要将其赋值给high
            arr[high] = arr[low];

        }
        // 跳出循环时low和high相等,此时的low或high就是pivot的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是pivot,所以需要将pivot赋值给arr[low]
        arr[low] = pivot;
        return low; // 返回tmp的正确位置
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

---

后记

👉Java全栈学习路线可参考：【Java全栈学习路线】最全的Java学习路线及知识清单，Java自学方向指引，内含最全Java全栈学习技术清单~
👉算法刷题路线可参考：算法刷题路线总结与相关资料分享，内含最详尽的算法刷题路线指南及相关资料分享~