2022年10月17日

934. 最短的桥

class Solution {
public:

    int indexMap[105][105] = {0}; //岛屿点，对应一个岛
    int n;
    int edgex[105*105] = {0};
    int edgey[105*105] = {0};
    int edgei[105*105] = {0};
    int edgej[105*105] = {0};
    int edgecount = 0;
    int edgeicount = 0;
    int shortestBridge(vector<vector<int>>& grid) {
        n = grid.size();
        int islandCount = 0;
        int p1x,p1y;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1 && indexMap[i][j] == 0) {
                    ++islandCount;
                    dfs(grid, i, j, islandCount);
                }
            }
        }
        int min=INT_MAX;
        for(int i = 0; i < edgecount; i++) {
            for(int j = 0; j < edgeicount; j++) {
                int path = abs(edgex[i]-edgei[j]) + abs(edgey[i] - edgej[j]) - 1;
                if(min >= path) {
                    min = path;
                }
            }
        }
        return min;
    }
    void dfs(vector<vector<int>>& grid, int x, int y, int index) {
        if(x < 0 || y < 0 || x >= n || y >= n) return;
        if(indexMap[x][y] != 0 || grid[x][y] != 1) return;
        indexMap[x][y] = index;
        bool flag = (y-1 >= 0 && grid[x][y-1] == 0) || (y+1 < n && grid[x][y+1] == 0) || (x+1 < n && grid[x+1][y] == 0) || (x-1 >= 0 && grid[x-1][y] == 0);
        dfs(grid, x, y-1, index);
        dfs(grid, x, y+1, index);
        dfs(grid, x+1, y, index);
        dfs(grid, x-1, y, index);
        if(flag) {
            if(indexMap[x][y]==1) {
                edgex[edgecount]=x;
                edgey[edgecount]=y;
                edgecount++;
            } else if(indexMap[x][y]==2) {
                edgei[edgeicount]=x;
                edgej[edgeicount]=y;
                edgeicount++;
            }
        }
    }
};

和之前写的一道题有点像，827. 最大人工岛
827. 最大人工岛我先dfs找到所有连通子图和包围岛的0点，然后找这些点中有无同时包围多个岛的，把他们的面积加起来取最大值

这道题也可以使用相同的方法，找到每个岛屿的边界点，然后计算边界点的距离(只有两个岛，两个岛之间肯定是可以连通的，且不管使用那条途径，最短距离一定是 $ abs(x_1 - x_2) + abs(y_1-y_2)-1 $)

看答案

class Solution {
public:
    void dfs(int x, int y, vector<vector<int>>& grid, queue<pair<int, int>> &qu) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] != 1) {
            return;
        }
        qu.emplace(x, y);
        grid[x][y] = -1;
        dfs(x - 1, y, grid, qu);
        dfs(x + 1, y, grid, qu);
        dfs(x, y - 1, grid, qu);
        dfs(x, y + 1, grid, qu);
    }

    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue<pair<int, int>> qu;
                    dfs(i, j, grid, qu);
                    int step = 0;
                    while (!qu.empty()) {
                        int sz = qu.size();
                        for (int i = 0; i < sz; i++) {
                            auto [x, y] = qu.front();
                            qu.pop();
                            for (int k = 0; k < 4; k++) {
                                int nx = x + dirs[k][0];
                                int ny = y + dirs[k][1];
                                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                                    if (grid[nx][ny] == 0) {
                                        qu.emplace(nx, ny);
                                        grid[nx][ny] = -1;
                                    } else if (grid[nx][ny] == 1) {
                                        return step;
                                    }
                                }
                            }
                        }
                        step++;
                    }
                }
            }
        }
        return 0;
    }
};

对于一个为1的点，先dfs吧所有在同一个岛屿内的1放入队列q中
对于队列中的每个节点，把包围他们的0入队，反复操作，直到遇到1
也就是在岛屿附近画圈，遇到1对应的圈数就是结果。

915. 分割数组

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        vector<int> max(n+1);
        max[0] = INT_MIN;
        vector<int> min(n);
        min[n-1] = nums[n-1];
        for(int i = 0; i < n; i++) {
            if(nums[i] > max[i]) {
                max[i+1] = nums[i];
            } else {
                max[i+1] = max[i];
            }
        }
        for(int i = n-2; i >= 0; i--) {
            if(nums[i] < min[i+1]) {
                min[i] = nums[i];
            } else {
                min[i] = min[i+1];
            }
        }
        for(int i = 1; i < n; i++) {
            if(max[i] <= min[i]) {
                return i;
            }
        }
        return -1;
    }
};

没想到会这么慢

优化1

• max数组没必要
• 不用vector

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        int min[100005] = {0};
        min[n-1] = nums[n-1];
        for(int i = n-2; i >= 0; i--) {
            if(nums[i] < min[i+1]) {
                min[i] = nums[i];
            } else {
                min[i] = min[i+1];
            }
        }
        int max = nums[0];
        for(int i = 1; i < n; i++) {
            if(max <= min[i]) {
                return i;
            }
            if(max < nums[i]) {
                max = nums[i];
            }
        }
        return -1;
    }
};

1768. 交替合并字符串

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string ret;
        int len1 = word1.size(), len2 = word2.size();
        int i = 0;
        for(; i < len1 && i < len2; i++) {
            ret.push_back(word1[i]);
            ret.push_back(word2[i]);
        }
        if(len1 < len2) {
            for(; i < len2; i++) {
                ret.push_back(word2[i]);
            }
        } else {
            for(; i < len1; i++) {
                ret.push_back(word1[i]);
            }
        }
        return ret;
    }
};

1235. 规划兼职工作

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<int> index(n);
        for(int i = 0; i < n; i++) {
            index[i] = i;
        }
        sort(index.begin(), index.end(), [&](int a, int b)->bool {return endTime[a] < endTime[b];});
        vector<int> dp(n+1);
        for(int i = 1; i <= n; i++) {
            int j = index[i-1];
            int k = i-2;
            for(; k >= 0; k--) {
                if(endTime[index[k]] <= startTime[j]) break;
            }
            dp[i] = max(dp[i-1], dp[k+1] + profit[j]);
        }
        return dp[n];
    }
};

开始想用贪心，给时薪排序，一次选择，但是发现这样得到的不是profit最大，而是工作时间更短的情况下的收益最大
看了答案后自己写的，发现是一个非常典型的dp问题

官方题解

class Solution {
public:
    int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit) {
        int n = startTime.size();
        vector<vector<int>> jobs(n);
        for (int i = 0; i < n; i++) {
            jobs[i] = {startTime[i], endTime[i], profit[i]};
        }
        sort(jobs.begin(), jobs.end(), [](const vector<int> &job1, const vector<int> &job2) -> bool {
            return job1[1] < job2[1];
        });
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            int k = upper_bound(jobs.begin(), jobs.begin() + i - 1, jobs[i - 1][0], [&](int st, const vector<int> &job) -> bool {
                return st < job[1];
            }) - jobs.begin();
            dp[i] = max(dp[i - 1], dp[k] + jobs[i - 1][2]);
        }
        return dp[n];
    }
};