leetcode 765+778 题解

发表于

这周因为两道题目都只想到了一种解法，所以写在一起。

1. Swim In Rising Water

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example 1:

1
2
3
4
5
6
7
8
Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Note:

  1. 2 <= N <= 50.
  2. grid[i][j] is a permutation of [0, …, N*N - 1].

解法

这道题的意思是，在t时刻，海拔为t，而n*n的二维矩阵的每个数值都代表了一处的海拔，从一点游到另一点的条件是两处的海拔（值）都大于等于t，要求求出从（0，0）到（n-1，n-1）的最小时间。也就是一个搜索节点的问题，可以用bfs即广度优先搜索的思路来做。

在寻找足够大的t时，我用二分法来实现，这样又可以节约不少时间：

1
2
3
4
5
6
7
8
9
10
11
int swimInWater(vector<vector<int>>& grid) {
    int n = grid.size(), st = grid[0][0], ed = n * n - 1, t = 0;
    while(st < ed){
        t = (st + ed) / 2;
        if(swim(grid, t)){	//判断t时能否到达终点
            ed = t;
        }
        else st = t + (st + ed) % 2;
    }
    return st;
}

真正的实现函数里，bfs用一个queue来实现，还要一个二维vector来记录已经到过的节点。然后就是每次把和节点相邻的未经过的节点（且是数值小于等于t的）加入bfs，并把现有节点pop出去，看能否在bfs为空之前找到终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool swim(vector<vector<int>>& grid, int t){
    int n = grid.size();
    queue<pair<int, int>> bfs;
    vector<vector<int>> visited(n, vector<int>(n));
    int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};	//右左下上
    bfs.emplace(0, 0);
    visited[0][0] = 1;
    while(bfs.size()){
        int x = bfs.front().first, y = bfs.front().second;
        bfs.pop();
        if(grid[x][y] <= t){
            if(x == n - 1 && y == n - 1) return true;
            for(auto d : dir){
                int xs = x + d[0], ys = y + d[1];
                if(xs >= 0 && xs < n && ys >= 0 && ys < n && !visited[xs][ys]){	//判断边界
                    visited[xs][ys] = 1;
                    bfs.emplace(xs, ys);
                }
            }
        }
    }
    return false;
}

这样就完成了这一道题。

2. Couples Holding Hands

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

1
2
3
Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

1
2
3
Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.

Note:

  1. len(row) is even and in the range of [4, 60].
  2. row is guaranteed to be a permutation of 0...len(row)-1.

解法（伪）

在这道题目中，有许多对couple，他们是(0, 1), (2, 3), …, (2n-2, 2n-1)。现在它们的顺序被打乱了，而你可以随即调换元素的位置，你需要找到调换次数最少的方案。

我的做法是简单的在判断两个元素不是一对couple后，往后查找它的couple并替换，同时调换次数增加一次。

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
int minSwapsCouples(vector<int>& row) {
    int swap = 0;
    for(int i = 0; i < row.size() - 1; i += 2){
        if(row[i] % 2){
            if(row[i + 1] != row[i] - 1){
                swap++;
                for(int j = i + 2; j < row.size(); j++){
                    if(row[j] == row[i] - 1){
                        int temp = row[j];
                        row[j] = row[i + 1];
                        row[i + 1] = temp;
                        break;
                    }
                }
            }
        }
        else{
            if(row[i + 1] != row[i] + 1){
                swap++;
                for(int j = i + 2; j < row.size(); j++){
                    if(row[j] == row[i] + 1){
                        int temp = row[j];
                        row[j] = row[i + 1];
                        row[i + 1] = temp;
                        break;
                    }
                }
            }
        }
    }
    return swap;
}

你以为这样就结束了吗？

cyclic swapping

上面的解法是在循环中嵌套一个循环，效果显然是不行的，通过leetcode的discuss，我学到了一种更为优秀的解法：cyclic swapping。

这个解法的精华在于：i == ptn[pos[ptn[row[i]]]]，乍一看确实毫无头绪，但要首先了解两个额外设置的数组ptn和pos：

  1. ptn[i]指的是标签i的couple的值（i可以是位置也可以是具体的值）—— 若i为偶数，ptn[i] = i + 1，若i为奇数，ptn[i] = i - 1。
  2. pos[i]指的是标签i在row数组（也就是给定的随机数组）中的index —— row[pos[i]] == i。

这样一来，i == ptn[pos[ptn[row[i]]]]的意思就是：

  1. 在位置i上的元素有值row[i]，我们想把它放在它couple的旁边。
  2. 首先找到它的couple的值，也就是ptn[row[i]]。
  3. 接着找到这个couple的位置，也就是pos[ptn[row[i]]]。
  4. 最后找到这个位置旁的位置，也就是ptn[pos[ptn[row[i]]]]。

接着就可以进行调换了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minSwapsCouples(vector<int>& row) {
    int res = 0, N = row.size();
    vector<int> ptn(N, 0);
    vector<int> pos(N, 0);
    for (int i = 0; i < N; i++) {
        ptn[i] = (i % 2 == 0 ? i + 1 : i - 1);
        pos[row[i]] = i;
    }//初始化
    
    for (int i = 0; i < N; i++) {
        for (int j = ptn[pos[ptn[row[i]]]]; i != j; j = ptn[pos[ptn[row[i]]]]) {
            swap(row[i], row[j]);
            swap(pos[row[i]], pos[row[j]]);
            res++;	//调换次数
        }	//这里的循环实际上只是完成一个位置的调换，如果这里的循环多于一次，后面的循环次数会减少
    }
        
    return res;
}