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

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

image.png

3 分 - 二进制链表转整数
5 分 - 顺次数
5 分 - 元素和小于等于阈值的正方形的最大边长
6 分 - 网格中的最短路径

对第四题更大规模数据做法的讨论

首先,朴素做法的空间复杂度为 O(mnk)O\left(m \cdot n \cdot k \right)

因此,在数据范围 1n,m1001 \leq n , m \leq 100 时,虽然可能不会超时(题目特性所致),但空间请求达到了1GB规模,这显然是不能容忍的。

观察到当 km+n1k \geq m+n-1 时显然是可以无视一切障碍物勇往直前走到终点的,直接返回 m+n2m+n-2 即可。

因此,在数据规模更大时,可以将空间复杂度优化为 O(mnmin(k,m+n1))O\left(m \cdot n \cdot \min\left(k,m+n-1\right) \right)

比较优化前后空间请求,设一个int占 88 字节,m=n=100m=n=100 , k=10000k=10000

  • 优化前:100100100008Byte=762MB100 \cdot 100 \cdot 10000 \cdot 8Byte=762MB
  • 优化后:100100min(10000,100+1001)8Byte=15MB100 \cdot 100 \cdot \min\left(10000,100+100-1\right) \cdot 8Byte=15MB

代码:

const int d[4][2]={1,0,-1,0,0,1,0,-1};

class Solution {
    int n,m;
    bool maze[41][41];
    struct node{
        int x,y,remain,t;
        node(){};
        node(int x,int y,int remain,int t):x(x),y(y),remain(remain),t(t){}
    };
    queue<node> que;
    bool vis[41][41][90];

    inline bool can_vis(int x,int y){
        if (x<0||x>=n) return false;
        if (y<0||y>=m) return false;
        return true;
    }
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        n=grid.size();
        m=grid[0].size();
        if (n==1&&m==1) return 0;
        if (k>m+n+2) return m+n-2;
        for (int i=0;i<n;++i){
            for (int j=0;j<m;++j){
                maze[i][j]=grid[i][j];
            }
        }
        if (maze[0][0]==1){
            maze[0][0]=0;--k;
        }
        if (maze[n-1][m-1]==1){
            maze[n-1][m-1]=0;--k;
        }
        if (k<0) return -1;
        vis[0][0][k]=true;
        que.emplace(0,0,k,0);
        node cur;
        int nx,ny,nr;
        while (!que.empty()){
            cur=que.front();que.pop();
            if (cur.x==n-1&&cur.y==m-1){
                return cur.t;
            }
            for (int i=0;i<4;++i){
                nx=cur.x+d[i][0];
                ny=cur.y+d[i][1];
                if (!can_vis(nx,ny)) continue;
                nr=cur.remain-(maze[nx][ny]?1:0);
                if (nr<0) continue;
                if (vis[nx][ny][nr]) continue;
                vis[nx][ny][nr]=true;
                que.emplace(nx,ny,nr,cur.t+1);
            }
        }
        return -1;
    }
};

Comment:第二次打Leetcode周赛,第一题手慢了,第三题没看到是正方形花了一定时间想更好复杂度的做法,第四题+1。发挥非常失误Rank38。争取一个月里混个Leetcode全家桶

4
展开全部 10 讨论