讨论/题目交流/🏆 第 178 场力扣周赛/
🏆 第 178 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 有多少小于当前数字的数字
4 分 - 通过投票对团队排名
5 分 - 二叉树中的列表
7 分 - 使网格图至少有一条有效路径的最小代价

展开讨论
力扣 (LeetCode)发起于 2020-03-01

来写一下 T4. 使网格图至少有一条有效路径的最小代价 的题解

很容易转化成一个最短路的模型,我们从 (0, 0) 点开始做最短路,到达每一个格子如果顺着箭头走代价为 0,反之代价为 1,计算到达 (n - 1, m - 1) 的最短路。每个格子只能修改一次的条件在最小代价的情况下一定天然符合,因为到达某个格子绕一圈回来再改它完全没有必要。

这道题目有一点特殊,因为他的边权为 0 / 1,可以使用 01BFS,在 O(nm+4nm)O(n * m + 4 * n * m) 的复杂度内求解,即 O(点数+边数)O(点数 + 边数)
通常的 BFS 边权均为 1,每次我们从队首取出一个节点的时候,一定能保证他是当前未向外扩展且 dist 值最小的节点,我们用它继续扩展新的节点并加入队尾,依旧能保证这个性质,这才成了宽度优先遍历。

但是如果出现了边权为 0 的情况,按照 BFS 处理就不行了,因为从边权为 0 的边扩展出去的新节点加入队列位尾部后,不能保证未来从队首取用节点一定是当前未向外扩展且 dist 值最小的节点
考虑当前队首节点 dist 值位 x,那么队列中的节点的元素 dist 值可能是这样的:

x,x,,x,x+1,,x+1x, x, \cdots, x, x+1, \cdots, x+1

考虑取队首节点开始扩展新的节点,那么新的节点的 dist 值位 xxx+1x+1,直接加入队尾将导致问题:

x,x,,x,x+1,,x+1x,x+1x, x, \cdots, x, x+1, \cdots, x+1 \leftarrow x, x+1

解决方法就是维护一个双端队列,如果从边权为 0 的边扩展的新的点从队首加入,从边权为 1 的点扩展的新点从队尾加入,这样就会变成这个样子:

xx,x,,x,x+1,,x+1x+1x \rightarrow x, x, \cdots, x, x+1, \cdots, x+1 \leftarrow x+1

那么,我们就可以继续放心取用队首元素做 BFS 了。

代码大致长这个样子:

const int MAXN = 150;
int dist[MAXN][MAXN];
bool inQue[MAXN][MAXN];
deque<pair<int, int> > que;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        
        memset(dist, -1, sizeof(dist));
        memset(inQue, false, sizeof(inQue));
        while(!que.empty()) que.pop_back();
        dist[0][0] = 0; que.push_back(make_pair(0, 0));
        
        while(!que.empty()){
            pair<int, int> cur = que.front(); que.pop_front();
            int x = cur.first, y = cur.second;
            
            if (inQue[x][y]) continue;
            inQue[x][y] = true;
            
            for (int k = 0; k < 4; k++){
                int tx = x + dx[k], ty = y + dy[k], cost = dist[x][y] + (grid[x][y] - 1 == k ? 0 : 1);
                if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
                if (dist[tx][ty] == -1 || dist[tx][ty] > cost){
                    dist[tx][ty] = cost;
                    if (dist[x][y] == dist[tx][ty]){
                        que.push_front(make_pair(tx, ty));
                    }else que.push_back(make_pair(tx, ty));
                }
            }
        }
        
        return dist[n - 1][m - 1];
    }
};

最后说一下吧,假设本题的点数为 nn,边数为 mm,那么时间复杂度为 O(n+m)O(n + m),也就是说数据范围可以再大一些,比如让点数等于 1e6。
这道题目本质是个最短路,用最短路算法也是没有问题的,用堆优化的 Dijkstra 复杂度为 O(nlogn)O(n log n) ,通过是合理的。但是 SPFA 嘛……如果想让 T4 更加完善一点,可以修改一下数据范围的限制方式,从限制网格图长宽,变为限制图中总格子数,然后卡一下 SPFA 和没有优化的 Dijkstra。

10
展开全部 21 讨论