算法(一)

发表于2022-05-03更新于2023-04-25字数统计3.6k阅读时长25分阅读次数

前言

程序 = 数据结构 + 算法。这是一篇整理算法知识的博客，内容包括二分查找、常见排序算法、深度优先搜索算法、广度优先搜索算法以及回溯。对于算法的理论讲解并不多，想要学习理论的朋友可以学习《算法导论3th》。代码使用java语言编写，但我个人认为C++做算法题会更加简洁一些🤣。

二分查找

需要记住二分查找的代码模板，这里可以选择左右都是闭区间while(l <= r)。

69. x 的平方根 (Easy)

给你一个非负整数x，计算并返回x的算术平方根。结果只保留整数部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int mySqrt(int x) {
        // 设置二分查找的上界，可以是x，也可是它的平方根。
        int r = 46340;
        int l = 0;
        while (l <= r) {
            int mid = (l+r)/2;
            if (mid * mid > x) {
                r = mid - 1;
            } else if (mid * mid < x) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return r;
    }
}

注：这道题使用牛顿迭代法求零点，速度更快。

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

也是二分查找，类似于实现C++算法中的lower_bound和upper_bound。核心部分代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
while(l<=r)
{
    int m = (l+r)/2;
    if(target < nums[m])
        r = m-1;
    else if(target > nums[m])
        l = m+1;
    else
    {
        res = m;
        lower ? r=m-1 : l=m+1;
    }
}

排序

  1. 快排

在数组中找到一个pivot，将小于pivot的数和大于pivot的分成两边，然后对两边分别递归调用快排。

注意，选择nums[first]为pivot之后，将该位置想象成一个空洞，先从右边向左找到第一个小于pivot的数，将其填到空洞里面(和空洞交换位置)，这时空洞在last位置，然后从左往右找到第一个大于pivot的数，将其填到空洞里面。最终的结果是空洞将小于pivot的数和大于pivot的分成两边，最后将pivot填到空洞里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quickSort(int[] nums, int l, int r) {
    if (l >= r) {
        return;
    }
    int first = l, last = r, pivot = nums[first];
    while (first < last) {
        while (first < last && nums[last] >= pivot) {
            -- last;
        }
        nums[first] = nums[last];
        while (first < last && nums[first] <= pivot) {
            ++ first;
        }
        nums[last] = nums[first];
    }
    nums[first] = pivot;
    quickSort(nums, l, first-1);
    quickSort(nums, first+1, r);
}
  1. 归并排序

分治思想，先将数组的左右两半部分都排好序，然后再将两半进行合并（Merge）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void mergeSort(int[] nums, int l, int r) {
    if (l >= r) 
        return;
    int m = l + (r - l) / 2;
    mergeSort(nums, l, m);
    mergeSort(nums, m+1, r);
    int[] tmp = new int[r - l + 1];
    int left = l, right = m+1, index = 0;
    while (left <= m && right <= r) {
        if (nums[left] < nums[right]) {
            tmp[index++] = nums[left++];
        } else {
            tmp[index++] = nums[right++];
        }
    }
    while (left <= m) tmp[index++] = nums[left++];
    while (right <= r) tmp[index++] = nums[right++];
    for (int t : tmp) {
        nums[l++] = t;
    }
}
  1. 插入排序

原理和扑克牌整理牌差不多，左边都是整理好的牌，新的牌要插到理好的牌的相应位置，不断的和相邻的牌比较，比它小则交换位置。

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int[] nums) {
    for (int i=0; i<nums.length; ++i) {
        for (int j=i; j>0; --j) {
            if (nums[j] < nums[j-1]) {
                int tmp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = tmp;
            }
        }
    }
}
  1. 冒泡排序

每一轮元素都和相邻元素比较，将较大的往右交换，即每一轮遍历都将一个最大的数冒泡至右端。

1
2
3
4
5
6
7
8
9
10
11
12
void bubbleSort(int[] nums) {
    int n = nums.length;
    for (int i=0; i<n-1; ++i) {
        for (int j=0; j<n-i-1; ++j) {
            if (nums[j] > nums[j+1]) {
                int tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
            }
        }
    }
}
  1. 选择排序

左边维护排好序的列表，每次遍历都找出右边最小的数，放在左边列表的右端。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectionSort(int[] nums) {
    int n = nums.length;
    for (int i=0; i<n; ++i){
        int min = i;
        for (int j=i+1; j<n; ++j) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        if (min != i) {
            int tmp = nums[min];
            nums[min] = nums[i];
            nums[i] = tmp;
        }
    }
}

搜索算法

深度优先(DFS)

记住深度优先搜索的算法模板，有两种实现方式，其一是使用递归实现，这种写法比较好理解，也推荐解题时使用这种写法；其二是使用栈来实现，不需要累计函数调用堆栈，但写法上比较难理解。

547. 省份数量

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。省份是指一组直接或间接相连的城市。

1
2
3
4
输入： isConnected = [[1, 1, 0],
                      1, 1, 0],
                      0, 0, 1]]
输出：2

深度优先遍历（递归写法）：

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
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        // 保存已经遍历过的节点
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i=0; i<n; ++i) {
            if (!visited[i]) {
                dfs(isConnected, visited, i);
                ++count;
            }
        }
        return count;
    }

    private void dfs(int[][] isConnected, boolean[] visited, int i) {
        visited[i] = true;
        // 遍历节点 i 的所有节点，若找到相邻节点，访问其相邻节点（深度优先）
        for (int j=0; j<isConnected[i].length; ++j) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(isConnected, visited, j);
            }
        }
    }
}

深度优先遍历（堆栈写法）：

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
class Solution {
    // 堆栈深度优先遍历写法
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        // 保存已经遍历过的节点
        boolean[] visited = new boolean[n];
        int count = 0;
        Stack<Integer> nodes = new Stack<>();
        for (int i=0; i<n; ++i) {
            if (!visited[i]) {
                nodes.push(i);
                while(!nodes.empty()) {
                    int node = nodes.pop();
                    for (int j=0; j<isConnected[node].length; ++j) {
                        // 将与节点 node 相邻且未访问过的节点入栈
                        if (isConnected[node][j] == 1 && !visited[j]) {
                            visited[j] = true;
                            nodes.push(j);
                        }
                    }
                }
                ++count;
            }
        }
        return count;
    }
}

695. 岛屿最大面积

给你一个大小为 m x n 的二进制矩阵 grid。

grid中元素由1和0组成，岛屿是由一些相邻的 1 构成的集合。求出 grid 中最大岛屿面积。

经典的深度优先算法，本质上和上面那题是一样的，只不过这题的节点更多了(变成了m x n个)，且每个节点的邻居变少了(变成了4个)。

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
class Solution {
    private int[][] directions = new int[][]{{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        for (int i=0; i<grid.length; ++i) {
            for (int j=0; j<grid[0].length; ++j) {
                if (grid[i][j] == 1) {
                    res = Math.max(res, dfs(grid, i, j));
                }
            }
        }
        return res;
    }

    // 在 grid 中包含 row，col的岛屿最大面积
    private int dfs(int[][] grid, int row, int col) {
        if (grid[row][col] == 0) {
            return 0;
        }
        int area = 1;
        // 路过的格子需要清零
        grid[row][col] = 0;
        for (int[] dir : directions) {
            int x = row + dir[0];
            int y = col + dir[1];
            if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
                area += dfs(grid, x, y);
            }
        }
        return area;
    }
}

回溯(Backtracking)

46. 全排列

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

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

涉及排列、组合等的题，可以使用回溯算法解决。和 DFS 过程有些类似，但是要记住在选择完当前遍历的节点之后需要还原回其先前的状态。

这里使用visited数组来保存元素的遍历状态，回溯的时候要还原其状态。

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        backtrack(nums, res, current, visited);
        return res;
    }

    private void backtrack(int[] nums, List<List<Integer>> res, List<Integer> current, boolean[] visited) {
        if (current.size() == nums.length) {
            res.add(new ArrayList<Integer>(current));
            return;
        }
        for (int i=0; i<nums.length; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                current.add(nums[i]);
                backtrack(nums, res, current, visited);
                current.remove(current.size()-1);
                visited[i] = false;
            }
        }
    }
}

实际上，可以不使用 visited数组记录遍历状态，而是通过将数组分为左右两半部分（通过first指针隔开），左边为已选择的元素，右边为待选择的元素。回溯结束的条件是只存在左边元素，即全部元素均被选择了。

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> output = new ArrayList<>();
        // 为了方便的交换元素，这里将num拷贝一份成为List<Integer>，使用C++不需要这样
        for (int num : nums) {
            output.add(num);
        }
        backtrack(res, output, 0);;
        return res;
    }

    private void backtrack(List<List<Integer>> res, List<Integer> output, int first) {
        if (first == output.size()-1) {
            res.add(new ArrayList<>(output));
            return;
        }
        // 将 first 元素右边的元素依次选择至 first 位置（回溯时将其放回原位）
        for (int i=first; i<output.size(); ++i) {
            Collections.swap(output, i, first);
            backtrack(res, output, first+1);
            Collections.swap(output, i, first);
        }
    }
}

51. N皇后

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

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。(字符'Q'和'.'分别代表皇后和空位。)

1
2
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

解这道题之前首先应该要明白以下事实：每个皇后所在的行、列、左斜、右斜均不能够存在其它皇后。

因此我们遍历行来放入皇后，并使用三个数组分别表示列、左斜、右斜当前是否已经存在皇后。(回溯时将当前位置的皇后撤销，并将这三个数组相应位置改为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
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] current = new char[n][n];
        for (int i=0; i<n; ++i) {
            Arrays.fill(current[i], '.');
        }
        // 每个皇后导致其所在行、列、左斜和右斜不能存在皇后，故记录每列、左斜、右斜是否存在皇后
        boolean[] column = new boolean[n];
        boolean[] leftDiag = new boolean[2*n-1];
        boolean[] rightDiag = new boolean[2*n-1];
        backtrack(res, current, column, leftDiag, rightDiag, 0, n);
        return res;
    }

    private void backtrack(List<List<String>> res, char[][] current, 
                    boolean[] column, boolean[] leftDiag, boolean[] rightDiag, int row, int n) {
        if (row == n) {
            List<String> tmp = new ArrayList<>();
            for (char[] chars : current) {
                tmp.add(new String(chars));
            }
            res.add(tmp);
            return;
        }
        // 向当前所在行的每个格子尝试插入皇后
        for (int i=0; i<n; ++i) {
            if (!column[i] && !leftDiag[n-1+i-row] && !rightDiag[i+row]) {
                current[row][i] = 'Q';
                column[i] = leftDiag[n-1+i-row] = rightDiag[i+row] = true;
                backtrack(res, current, column, leftDiag, rightDiag, row+1, n);
                // 回溯
                column[i] = leftDiag[n-1+i-row] = rightDiag[i+row] = false;
                current[row][i] = '.';
            }
        }
    }
}

广度优先搜索(BFS)

和深度优先的一直深入不同，广度优先搜索是一层一层进行遍历的，因此可以用来解决最短路径的问题。

广度优先搜索需要借助 队列(Queue) 来实现，基本流程为：访问队列中的节点，并将当前访问节点的所有子节点入队，作为下一层遍历的对象。

934. 最短的桥

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 ）

1
2
3
4
输入：A = [[0,1,0],
           [0,0,0],
           [0,0,1]]
输出：2

实际上就是求两座岛之间的最短距离。我们可以使用深度优先搜索首先将第一座岛屿搜索到，然后使用广度优先搜索沿着这座岛一层一层向外搜索，当搜索到另一座岛时搜索的层数就是最短的桥。(这道题算是代码量较大的题，但思路并不是很复杂，需要注意搜索算法的写法。)

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
class Solution {
    private int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int shortestBridge(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<Node> queue = new LinkedList<Node>();
        // 先深度优先搜索
        boolean flipped = false;
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, queue);
                    flipped = true;
                    break;
                }
            }
            // 用于跳出两层循环
            if (flipped) break;
        }
        // 对第一个岛屿中的点进行一圈圈扩大，也就是广度优先搜索
        int level = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            ++ level;
            while (--sz >= 0) {
                Node node = queue.poll();
                for (int[] dir : directions) {
                    int x = node.i + dir[0];
                    int y = node.j + dir[1];
                    if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
                        if (grid[x][y] == 0) {
                            grid[x][y] = 2;
                            queue.offer(new Node(x, y));
                        } else if (grid[x][y] == 1) {
                            return level;
                        }
                    }
                }
            }
        }
        return level;
    }

    // 深度优先搜索，遍历完第一个岛屿，并将其周围的0入队
    private void dfs(int[][] grid, int i, int j, Queue<Node> queue) {
        if (grid[i][j] == 0) {
            grid[i][j] = 2;
            queue.offer(new Node(i, j));
            return;
        }
        if (grid[i][j] == 2) {
            return ;
        }
        // 为了防止干扰，访问过的点改为 2
        grid[i][j] = 2;
        for (int[] dir : directions) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
                dfs(grid, x, y, queue);
            }
        }
    }

    static class Node{
        public int i;
        public int j;
        public Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}

参考文献

  1. https://leetcode-cn.com/problems
  2. 《算法导论3th》