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

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

image.png

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

共 10 个回复

第一题:

文字略

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int ret = 0;
        while (head != NULL) {
            ret = ret * 2 + head->val;
            head = head->next;
        }
        return ret;
    }
};

第二题:

这种题本来第一反应就是数位dp的,然而符合条件的数,总共才36个,想办法枚举出来就行了

条件:每一位上的数字都比前一位上的数字大 1 的整数

我们只需要分别枚举第一位是1,2,3...9,后面依此对前面的数字加一,直到有一位数字为9为止,中间产生的所有“顺次数”都记录下来

class Solution {
public:
    vector<int> all;
    void init() {
        if (all.size() != 0) {
            return;
        }
        for (int i = 1;i < 10;i++) {
            int x = 0;
            for (int j = i;j < 10;j++) {
                x = x * 10 + j;
                all.push_back(x);
            }
        }
        sort(all.begin(), all.end());
    }
    vector<int> sequentialDigits(int low, int high) {
        init();
        vector<int> ret;
        for (int i = 0;i < all.size();i++) {
            if (all[i] >= low && all[i] <= high) {
                ret.push_back(all[i]);
            }
        }
        return ret;
    }
};

第三题:

这种题第165场周赛也有,统计全为 1 的正方形子矩阵

原理:枚举所有的正方形(x,y,k),其中(x,y)为正方形左上角的坐标,k为正方形边长,判断每个正方形是否满足元素总和小于或等于阈值

做法:从大到小枚举边长k(这样如果某个边长为k的正方形满足条件,那么可以直接返回),利用滑动数组(或者前缀和),把grid[i]到grid[i+k-1]累加压缩成一维,再利用滑动数组(或者前缀和),寻找符合元素总和小于或等于阈值的长度为k的连续子数组

时间复杂度o(n3)o(n^3)

当然二分k也行。。时间复杂度降到o(n2logn)o(n^2 logn)

class Solution {
public:
    bool find(vector<int>& data, int k, int threshold) {
        int ret = 0;
        for (int i = 0;i < k - 1;i++) {
            ret += data[i];
        }
        for (int i = k - 1;i < data.size();i++) {
            ret += data[i];
            if (ret <= threshold) {
                return true;
            }
            ret -= data[i - k + 1];
        }
        return false;
    }
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int n = mat.size();
        int m = mat[0].size();
        int k = min(n, m);
        
        while (k > 0) {
            vector<int> data(m, 0);
            for (int i = 0;i < k - 1;i++) {
                for (int j = 0;j < m;j++) {
                    data[j] += mat[i][j];
                }
            }
            for (int i = k - 1;i < n;i++) {
                for (int j = 0;j < m;j++) {
                    data[j] += mat[i][j];
                }
                if (find(data, k, threshold)) {
                    return k;
                }
                for (int j = 0;j < m;j++) {
                    data[j] -= mat[i - k + 1][j];
                }
            }
            k--;
        }
        return k;
    }
};

第四题:

bfs题,跟一般迷宫题不一样,这个题需要增加一维k,状态点:dist[{x, y, k}],表示从(0,0)到(x,y),还剩k次消除机会的最短路径,原点就变成了(0,0,k),我们bfs的目标是min(dist({n,m-1,k})),状态转移时,根据grid[x][y]是否为障碍,判断转移状态的第二维(k)是否需要减1,注意如果k小于0,状态点无效

时间复杂度理论上为o(n2k)o(n^2*k)

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<vector<bool>>> flag(n, vector<vector<bool>>(m, vector<bool>(k + 1, false)));
        queue<vector<int>> Q;
        
        int vx[] = {0,0,1,-1};
        int vy[] = {1,-1,0,0};
        
        //第一维:横坐标
        //第二维:纵坐标
        //第三维:剩下的消除次数
        //第四维:该状态下的最短路径
        Q.push({0, 0, k, 0});
        flag[0][0][k] = true;
        while (!Q.empty()) {
            auto last = Q.front();
            Q.pop();
            
            if (last[0] == n - 1 && last[1] == m - 1) {
                return last[3];
            }
            
            for (int i = 0;i < 4;i++) {
                vector<int> next = {last[0] + vx[i], last[1] + vy[i], last[2], last[3] + 1};
                if (next[0] < 0 || next[0] >= n || next[1] < 0 || next[1] >= m) {
                    continue;
                }
                if (grid[next[0]][next[1]] == 1) {
                    next[2]--;
                }
                if (next[2] < 0 || flag[next[0]][next[1]][next[2]]) {
                    continue;
                }
                flag[next[0]][next[1]][next[2]] = true;
                Q.push(next);
            }
        }
        return -1;
    }
};
17
对第四题更大规模数据做法的讨论

首先,朴素做法的空间复杂度为 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

Rank

  • 13/1477

5283. 二进制链表转整数

  • 题意:给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值 。
  • 难度:easy
  • 数据范围:
    • 链表不为空。
    • 链表的结点总数不超过 30。
    • 每个结点的值不是 0 就是 1。
  • 思路:把所有元素放在一个vector里面,然后反转一下从前往后计算即可。
  • 复杂度:O(30)
  • 代码:
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        vector <int> v;
        while(head!=NULL){
            v.push_back(head->val);
            head = head->next;
        }
        reverse(v.begin(),v.end());
        int ans=0;
        for(int i=0; i<v.size(); i++){
            ans=ans+pow(2, i) * v[i];
        }
        return ans;
    }
};

顺次数

  • 题意:我们定义「顺次数」为:每一位上的数字都比前一位上的数字大 1 的整数。请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表(从小到大排序)。
  • 难度:Medium
  • 数据范围:10 <= low <= high <= 10^9
  • 思路:直接枚举数起点和终点,然后把数计算出来check一下是不是在[low,high]中,是的话丢进set,然后将set的元素放入vector输出。
  • 复杂度:O(93)O(9^3)
  • 代码:
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector <int> ans;
        set <int> s;
        int t = 0;
        for(int j=1; j<=9; j++){//起点
            t = 0;
            for(int k=j; k<=9; k++){
                t = t*10 + k;
                if(t >= low && t <= high) s.insert(t);
            }
        }
        for(auto it:s){
            ans.push_back(it);
        }
        return ans;
    }
};

5285. 元素和小于等于阈值的正方形的最大边长

  • 题意:给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。请你返回元素总和小于或等于阈值的正方形区域的最大边长;如果没有这样的正方形区域,则返回 0 。
  • 难度:Medium
  • 数据范围:
    • 1 <= m, n <= 300
    • m == mat.length
    • n == mat[i].length
    • 0 <= mat[i][j] <= 10000
    • 0 <= threshold <= 10^5
  • 思路:维护二维前缀和,然后枚举方形子矩阵的起点(x,y)和边长k,然后用二维前缀和计算子矩阵的和并和threshold作比较即可,如果满足就更新答案。
  • 复杂度:O(nmmin(n,m))O(n*m*min(n,m))
  • 代码:
class Solution {
public:
    int a[310][310], dp[310][310];
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        memset(dp, 0, sizeof(dp));
        int n = mat.size();
        int m = mat[0].size();
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                a[i][j] = mat[i-1][j-1];
            }
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+a[i][j];
            }
        }
        int ans = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                for(int k=1; k<=min(n, m); k++){
                    if((i+k-1)<=n&&(j+k-1)<=m){
                        int x2 = i+k-1, y2=j+k-1, x1=i, y1=j;
                        int sum = dp[x2][y2]+dp[x1-1][y1-1]-dp[x1-1][y2]-dp[x2][y1-1];
                        if(sum <= threshold){
                            ans = max(ans, k);
                        }
                    }
                }
            }
        }
        return ans;
    }
};

5286. 网格中的最短路径

  • 题意:给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步,您都可以在空白单元格中上、下、左、右移动。如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。
  • 难度:hard(认真的?)
  • 数据范围:
    • grid.length == m
    • grid[0].length == n
    • 1 <= m, n <= 40
    • 1 <= k <= m*n
    • grid[i][j] == 0 or 1
    • grid[0][0] == grid[m-1][n-1] == 0
  • 思路:爆搜。vis[i][j][t]代表当前在[i,j]位置已经清除了t个障碍物的状态是否被标记,总的状态数就是40x40x40x40=2560000,剩下的就是BFS的常规做法了。
  • 复杂度:O(n2m2)O(n^2*m^2)
  • 代码:
class Solution {
public:
    struct node{
        int x, y, step, k;
        node(){}
        node(int x_, int y_, int step_, int k_):x(x_),y(y_),step(step_),k(k_){}
    };
    bool vis[42][42][1602];
    int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    int shortestPath(vector<vector<int>>& grid, int k) {
        queue <node> q;
        node now=node(0, 0, 0, 0);
        vis[0][0][0] = true;
        q.push(now);
        int n = grid.size();
        int m = grid[0].size();
        memset(vis, false, sizeof(vis));
        int ans = 1e9;
        while(q.size()){
            now = q.front();
            q.pop();
            if(now.x==n-1&&now.y==m-1){
                ans = min(ans, now.step);
            }
            for(int i=0; i<4; i++){
                int tx = now.x+dir[i][0], ty=now.y+dir[i][1];
                if(tx>=0&&ty>=0&&tx<n&&ty<m){
                    if(grid[tx][ty]==0){
                        if(!vis[tx][ty][now.k]){
                            q.push(node(tx,ty,now.step+1,now.k));
                            vis[tx][ty][now.k]=1;
                        }
                    }
                    else{
                        if(now.k+1>k) continue;
                        if(!vis[tx][ty][now.k+1]){
                            q.push(node(tx, ty, now.step+1, now.k+1));
                            vis[tx][ty][now.k+1]=1;
                        }
                    }
                }
            }
        }
        if(ans==1e9) ans=-1;
        return ans;
    }
};

欢迎关注我的微信公众号GiantPandaCV,期待和你一起交流机器学习,深度学习,图像算法,优化技术,比赛及日常生活等。
图片.png

3

第一题

条件: 给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。

思路:直接遍历链表,转换为字符串

class Solution:

    def getDecimalValue(self, head: ListNode) -> int:
        """
        遍历链表,用str存储,转10进制
        :param head:
        :return:
        """
        p = head
        res = ''
        while p:
            res += str(p.val)
            p = p.next
        return int(res, 2)

第二题

条件:我们定义「顺次数」为:每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表(从小到大排序)。

范围: 10 <= low <= high <= 10^9

思路:直接枚举1~9,后面位数=当前位数+1,记录下就可以

class Solution:

    def __is_suitable_number(self, num):
        pre = num % 10
        num = num // 10
        while num:
            if num % 10 + 1 != pre:
                return False

            pre = num % 10
            num = num // 10
        return True

    def sequentialDigits(self, low: int, high: int) -> List[int]:
        high_counter = self.digit(high)
        res = []
        for j in range(1, 10):
            num = j
            flag = False
            pre = j
            for i in range(high_counter):
                pre += 1
                num = num * 10 + pre
                if low <= num <= high:
                    if self.__is_suitable_number(num):
                        res.append(num)
                    continue
                elif num > high:
                    flag = True
                    break
            if flag:
                continue

        res.sort()
        return res

    def digit(self, num):
        counter = 1
        while num // 10:
            counter += 1
            num = num // 10
        return counter

第三题

条件:给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长;如果没有这样的正方形区域,则返回 0 。

范围:

  • 1 <= m, n <= 300
  • m == mat.length
  • n == mat[i].length
  • 0 <= mat[i][j] <= 10000
  • 0 <= threshold <= 10^5

思路: 这道题,求的是最大边长,由此可以跳过很多比当前最大边长小的区域,直接遍历就过了,代码还能用前缀和优化下区域求和,比较懒就不写了,有兴趣的可以自己写下.

class Solution:
   
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        """
        暴力遍历,以当前位置找正方形最大区域
        :param mat:
        :param threshold:
        :return:
        """
        import numpy as np
        mat = np.array(mat)
        row = len(mat)
        col = len(mat[0])

        min_val = float('-inf')
        max_length = -1
        for i in range(row):
            for j in range(col):
                # 最大区域
                length = min(row - i, col - j)
                if length <= max_length:
                    break
                # 对正方形区域内的值进行求和
                # 区域范围2 ~ 最大区域
                for k in range(2, length + 1):
                    if k <= max_length:
                        continue
                    nums = mat[i:i + k, j:j + k]
                    sums = nums.sum()
                    if sums <= threshold and nums.shape == (k, k):
                        min_val = max(min_val, k)
                        max_length = max(max_length, k)
                    elif sums > threshold:
                        break

        return min_val if min_val != float('-inf') else 0

第四题

条件:给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步,您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。

范围:

  • grid.length == m
  • grid[0].length == n
  • 1 <= m, n <= 40
  • 1 <= k <= m*n
  • grid[i][j] == 0 or 1
  • grid[0][0] == grid[m-1][n-1] == 0

思路:这道题用bfs和dfs都能做,不过bfs相对简单些,第一个到达终点的就是最短路径,转移状态时,只需要判断当前是否为障碍,如果消除当前障碍,并且计数 > k,则跳过当前状态点.

class Solution:
    
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        """
        bfs,消除障碍
        :param grid:
        :param k:
        :return:
        """
        from collections import deque
        row = len(grid)
        col = len(grid[0])

        queue = deque()
        queue.appendleft((0, 0, 0, 0))

        seen = set()
        seen.add((0, 0, 0))

        while queue:
            i, j, counter, step = queue.pop()

            if i == row - 1 and j == col - 1:
                return step

            if grid[i][j] == 1:
                counter += 1
            if counter > k:
                continue

            for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                tmp_i, tmp_j = x + i, y + j
                if 0 <= tmp_i < row and 0 <= tmp_j < col and (tmp_i, tmp_j, counter) not in seen:
                    queue.appendleft((tmp_i, tmp_j, counter, step + 1))
                    seen.add((tmp_i, tmp_j, counter))

        return -1
2

第四题在dfs超时后才发现应该是dp,然而时间已经莫得了

2

第二题

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> list = new ArrayList<>();
        while(low<high){
            int weight=maxw(low);
            int low1=low/(int)Math.pow(10,weight);
            int high1=high/(int)Math.pow(10,weight);
            if (high1*(int)Math.pow(10,weight)!=high)high1++;
            while((low1+weight)<=9&&low1<high1&&(low1!=high1)){
                int x=0;
                int l=low1;
                for(int i=weight;i>=0;i--){
                    x+=(l++)*(int)Math.pow(10,i);
                }
                if (x<=high&&x>=low) list.add(x);
                low1++;
            }
            low=(int)Math.pow(10,weight+1);
        }
        return list;
    }
    int maxw(int x){
        int sum=0;
        while(x/10!=0){
            x=x/10;
            sum++;
        }
        return sum;
    }
}
1

最后一题用 dfs做 怎么会得到 10 改成bfs就可以了 奇怪

1
public int getDecimalValue(ListNode head) {
          StringBuilder stringBuilder = new StringBuilder();
          while (head!=null){
              stringBuilder.append(head.val);
              head = head.next;
          }
          return Integer.parseInt(stringBuilder.toString(),2);
    }

第一题直接取出二进制数,然后一个Integer方法转换。

想请教一下,不同语言的 accept 上限时间是一样的吗?

扔个python3题解,看看python如何写,第三题第四题不超时。
https://www.bilibili.com/read/cv4167903

1