TikTok真题第7天 | 2422.使用合并操作将数组转换为回文序列、200.岛屿的个数、694.不同岛屿的个数

2422.使用合并操作将数组转换为回文序列

题目链接：merge-operations-to-turn-array-into-a-palindrome

解法：

用双指针来解决。整体思路是：从数组的左右两边开始看，

• 如果 nums[left] == nums[right]，两边数字一样，left++, right--，继续比较中间的元素
• 如果?nums[left] != nums[right]，两边数字不一样，此时需要合并，谁较小就让谁与其邻居元素合并，并移动指针。同时要记录，merge了一次。
• 当 left 指针与 right 指针相遇的时候，返回一共合并了几次。

这个题还有一个很重要的细节，那就是在不断合并的过程中，合并的元素可能会超出int类型的范围。int类型是4字节32位，10进制最多表示10位。题目给出的array中元素范围是10进制的6位，但不断合并的过程中可能超出。所以得单独定义用于合并的leftSum和rightSum，类型为long。

参考题解：双指针

边界条件：

时间复杂度：O(n)

空间复杂度：O(1)

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = n - 1;
        // 注意这里是long类型，int类型是不行的，因为后面merge的时候，test case会超出32位8字节的限制
        // 也因为如此，所以这俩值需要显式地提取出来，通过 nums[left+1] += nums[left] 这种方式来更新是不行的
        long leftSum = nums[0], rightSum = nums[j];
        int res = 0;
        while (i < j) {
            if (leftSum > rightSum) {
                j--;
                rightSum += nums[j];
                res++;
            } else if (leftSum < rightSum) {
                i++;
                leftSum += nums[i];
                res++;
            } else {
                i++, j--;
                leftSum = nums[i], rightSum = nums[j];
            }
        }
        return res;
    }
};

200.岛屿的个数

题目链接：number-of-islands

解法：

每块岛屿可以看成相连的一个个节点，只需把所有相连节点遍历殆尽并标上特殊值以记录该节点已访问过，则遍历殆尽时证明一块岛屿已找到。

总体思想是，从1个小岛开始，通过遍历所有垂直和水平方向的节点，把相邻的小岛连接起来变成一整块岛屿，同时标上特殊值用来记录该节点已经访问过了。遍历完毕时，一整块岛屿就找到了。再从另一个小岛开始，继续遍历。

DFS：找到为1的点，然后访问下、上、左、右4个方位（垂直和水平）。如果遇到1，就置为0，表示访问过了，再继续访问下上左右；如果遇到0，那么就是遇到水了，该递归方向返回。如果点的所有递归都返回了，那岛屿数量加1。然后再找下一个为1的点进行DFS。

BFS：找到为1的点，加入队列。弹出后，访问下、上、左、右4个方位（垂直和水平）。如果遇到1，就加入队列。先进先出。

参考题解：LeetCode 200：岛屿数量 Number of Islands - 知乎

边界条件：无

时间复杂度：O(M×N)，其中 M 和 N 分别为行数和列数。

空间复杂度：DFS的O(M×N)；BFD的O(min(M,N) )，在最坏的情况下（全部为陆地），队列的大小可以达到 min(M，N)。

// DFS
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int ROW = grid.size();
        int COL = grid[0].size();
        int res = 0;
        for (int i=0; i<ROW; i++) {
            for (int j=0; j<COL; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j, ROW, COL);
                    res++;
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& grid, int i, int j, int ROW, int COL) {
        // 递归终止条件
        if (i <0 || j < 0 || i >= ROW || j >= COL) return;
        if (grid[i][j] == '0') return;
        grid[i][j] = '0'; // 置为0，避免再次被搜索
        // 依次为下，上，左，右，这4个方向
        dfs(grid, i-1, j, ROW, COL);
        dfs(grid, i+1, j, ROW, COL);
        dfs(grid, i, j-1, ROW, COL);
        dfs(grid, i, j+1, ROW, COL);
    }
};

// BFS
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int ROW = grid.size();
        int COL = grid[0].size();
        int res = 0;
        for (int i=0; i<ROW; i++) {
            for (int j=0; j<COL; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j, ROW, COL);
                    res++;
                }
            }
        }
        return res;
    }

    void bfs(vector<vector<char>>& grid, int i, int j, int ROW, int COL) {
        queue<int> deque;
        // 把二维表格展开为一维时的索引
        deque.push(i*COL + j);
        while (!deque.empty()) {
            int idx = deque.front();
            deque.pop();
            int i = idx / COL, j = idx % COL;
            // 别忘了不能越界，要加 (i-1) >= 0 这个条件
            if ((i-1) >= 0 && grid[i-1][j] == '1') {
                grid[i-1][j] = '0';
                deque.push((i-1)*COL + j);
            }
            if ((i+1) < ROW && grid[i+1][j] == '1') {
                grid[i+1][j] = '0';
                deque.push((i+1)*COL + j);
            }
            if ((j-1) >= 0 && grid[i][j-1] == '1') {
                grid[i][j-1] = '0';
                deque.push(i*COL + j-1);
            }
           if ((j+1) < COL && grid[i][j+1] == '1') {
                grid[i][j+1] = '0';
                deque.push(i*COL + j+1);
            }
        }
    }
};

694.不同岛屿的个数

题目链接：number-of-distinct-islands

解法：

这个题的整体思路和【200.岛屿的个数】差不多，只是加了一个记录整块岛屿的形状。

整块岛屿的形状就是每个小岛的形状的列表。而形状定义为相对于左上角第1个小岛的位置的偏移量，这样左上角第一个小岛的位置是(0, 0)，下方的小岛则是(-1, 0)。这样，通过DFS或者BFS，可以得到这块岛屿上所有小岛的形状，从而得到整块岛屿的形状列表。

如果两块岛屿相对各自左上角的小岛的位置偏移量的列表相同，那么这两块岛屿形状相同。

要求不同的岛屿，那么就要把形状列表加入set中进行去重。

最后求set的长度即可。

BFS实现的步骤繁琐一些。

参考题解：https://blog.csdn.net/danspace1/article/details/86610850

边界条件：无

时间复杂度：O(mn)

空间复杂度：O(mn)

// DFS
class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int ROW = grid.size();
        int COL = grid[0].size();
        int res = 0;
        // 左上角第1个小岛的位置为(0,0)，先记录左上角，再记录其他小岛的位置
        set<vector<pair<int,int>>> shapes;
        for (int i=0; i<ROW; i++) {
            for (int j=0; j<COL; j++) {
                if (grid[i][j] == 1) {
                    vector<pair<int,int>> posVec;
                    // 左上角第1个小岛的位置为(0,0)
                    pair<int,int> pos(0, 0);
                    dfs(grid, i, j, posVec, pos);
                    shapes.insert(posVec);
                    res++;
                }
            }
        }
        return shapes.size();
    }

    void dfs(vector<vector<int>>& grid, int i, int j, vector<pair<int,int>>& posVec, pair<int,int>& pos) {
        // 递归终止条件
        int ROW = grid.size(), COL = grid[0].size();
        if (i <0 || j < 0 || i >= ROW || j >= COL) return;
        if (grid[i][j] == 0) return;
        
        grid[i][j] = 0; // 置为0，避免再次被搜索
        posVec.push_back(pos);

        // 依次为下，上，左，右，这4个方向
        vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
        for (const auto& d: directions) {
            // 计算相对左上角小岛的位置
            pair<int,int> newPos = {pos.first+d.first, pos.second+d.second};
            dfs(grid, i+d.first, j+d.second, posVec, newPos);
        }
    }
};

// BFS
class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int ROW = grid.size(),COL = grid[0].size(), res = 0;
        set<vector<pair<int, int>>> shapes;

        for (int i=0; i<ROW; i++) {
            for (int j=0; j<COL; j++) {
                if (grid[i][j] == 1) {
                    vector<pair<int,int>> posVec;
                    pair<int,int> idx(i, j), pos(0, 0);
                    bfs(grid, idx, posVec, pos);
                    shapes.insert(posVec);
                    res++;
                }
            }
        }
        return shapes.size();
    }

    void bfs(vector<vector<int>>& grid, pair<int,int> idx, vector<pair<int,int>>& posVec, pair<int,int>& pos) {
        int ROW = grid.size(), COL = grid[0].size();
        // 需要两个队列，一个装位置索引，一个装形状
        queue<pair<int, int>> deque, posQue;
        // 同时记录位置和形状
        deque.push(idx), posQue.push(pos);
        // 同时加入到整个岛屿的形状列表中
        posVec.push_back(pos);

        while (!deque.empty()) {
            pair<int,int> curIdx = deque.front();
            deque.pop();
            pair<int,int> curPos = posQue.front();
            posQue.pop();

            vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
            for (const auto& d: directions) {
                 int row = curIdx.first + d.first;
                 int col = curIdx.second + d.second;
                 if (row<0 || col<0 || row>=ROW || col>=COL) continue;
                 if (grid[row][col] == 0) continue;

                 grid[row][col] = 0;

                 pair<int,int> newIdx, newPos;
                 newIdx = {row, col};
                 newPos = {curPos.first+d.first, curPos.second+d.second};
                 deque.push(newIdx), posQue.push(newPos);

                 posVec.push_back(newPos);
            }
        }
    }
};