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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2019-12-15
最近编辑于 2019-12-15

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
展开全部 10 讨论