On the shoulders of giants.

weekly-contest-167

二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值

示例 1:

输入:head = [1,0,1]
输出:5
解释:二进制数 (101) 转化为十进制数 (5)

示例 2:

输入:head = [0]
输出:0

示例 3:

输入:head = [1]
输出:1

示例 4:

输入:head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出:18880

示例 5:

输入:head = [0,0]
输出:0

提示:

  • 链表不为空。
  • 链表的结点总数不超过 30
  • 每个结点的值不是 0 就是 1
题解

递归计算即可。

时间复杂度:\(O(\log n)\)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int x = 1;
    int getNum(ListNode* head) {
        if(head == NULL) return 0;
        int num = getNum(head->next) + head->val * x;
        x *= 2;
        return num;
    }
    int getDecimalValue(ListNode* head) {
        return getNum(head);
    }
};

顺次数

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

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

示例 1:

输出:low = 100, high = 300
输出:[123,234]

示例 2:

输出:low = 1000, high = 13000
输出:[1234,2345,3456,4567,5678,6789,12345]

提示:

  • 10 <= low <= high <= 10^9
题解

枚举第一个数是多少,然后深搜出合法答案,最后排序即可。

时间复杂度:\(O(9^2)\)

class Solution {
public:
    vector<int> result;
    
    void dfs(int sum, int s, int x, int y) {
        if(y < sum) return;
        if(x <= sum && sum <= y) {
            result.push_back(sum);
        }
        if(s <= 9) dfs(sum * 10 + s, s + 1, x, y);
    }
    
    vector<int> sequentialDigits(int low, int high) {
        for(int i = 1; i <= 9; i++) {
            dfs(0, i, low, high);
        }
        
        sort(result.begin(), result.end());
        
        return result;
    }
};

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

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

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

示例 1:

输入:mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
输出:2
解释:总和小于 4 的正方形的最大边长为 2,如图所示。

示例 2:

输入:mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
输出:0

示例 3:

输入:mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
输出:3

示例 4:

输入:mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
输出:2

提示:

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

前缀和求解,合法总和更新答案。

时间复杂度:\(O(nm\min (n,m))\)

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int n = mat.size(), m = mat[0].size(), ans = 0;
        vector<vector<int>> sum(n + 1, vector<int> (m + 1));
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                sum[i + 1][j + 1] = mat[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j];
            }
        }

        for(int r = 1; r <= min(n, m); r++) {
            for(int i = 1; i + r - 1 <= n; i++) {
                for(int j = 1; j + r - 1 <= m; j++) {
                    int x = i + r - 1, y = j + r - 1;
                    int val = sum[x][y] - sum[i - 1][y] - sum[x][j - 1] + sum[i - 1][j - 1];
                    if(val <= threshold) ans = max(ans, r);
                }
            }
        }
        
        return ans;
    }
};

网格中的最短路径

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

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

示例 1:

输入: 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
输出:6
解释:
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后,最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

示例 2:

输入:
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 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
题解

DFS:以 \((x,y,k)\) 为状态,表示为:在节点 \((x,y)\) 中还有 \(k\) 次消除次数。

那么有两中转移:

  • 当 \(grid_{x,y}\) 为 1 时:如果 \(k\) 不为 0 ,那么可以转移到 [laetx](x,y,k-1)[/latex] ;
  • 当 \(grid_{x,y}\) 为 0 时:那么可以转移到 \((x,y,k)\) 。

因为求最短路,所以再加上剪枝。

时间复杂度:\(O(nmk)\)

class stata {
public:
    int x, y, k;
    stata(int x, int y, int k) : x(x), y(y), k(k) { }
    
    bool operator < (const stata& tmp) const { 
        if(x != tmp.x || y != tmp.y) {
            return x < tmp.x || (x == tmp.x && y < tmp.y);
        } else {
            return k < tmp.k;
        }
    }
};

class Solution {
private:
    const int dt[2][4] = {{0, 1, 0, -1}, {1, 0, -1, 0}}, INF = 1E9;
    
public:
    vector<vector<int>> grid;
    map<stata, bool> vis;
    map<stata, int> dis;
    int ret = INF, n, m;
    
    void dfs(int x, int y, int k) {
        stata s = stata(x, y, k);
        if(vis[s] || ret <= dis[s]) return;
        vis[s] = true;
        
        if(x == n - 1 && y == m - 1) {
            ret = min(ret, dis[s]);
            return;
        }
        
        for(int i = 0; i < 4; i++) {
            int dx = x + dt[0][i], dy = y + dt[1][i];
            if(dx < 0 || n <= dx || dy < 0 || m <= dy) continue;
            
            if(grid[dx][dy] == 1) {
                if(k == 0) continue;
                stata ds = stata(dx, dy, k - 1);
                if(vis.find(ds) == vis.end()) dis[ds] = INF;
                if(dis[ds] > dis[s] + 1) {
                    dis[ds] = dis[s] + 1;
                    dfs(dx, dy, k - 1);
                }
            } else {
                stata ds = stata(dx, dy, k);
                if(vis.find(ds) == vis.end()) dis[ds] = INF;
                if(dis[ds] > dis[s] + 1) {
                    dis[ds] = dis[s] + 1;
                    dfs(dx, dy, k);
                }
            }
        }
    }
    
    int shortestPath(vector<vector<int>>& grid, int k) {
        n = grid.size(), m = grid[0].size();
        
        vis.clear();
        dis.clear();

        this->grid = grid;
        
        dis[(stata){0, 0, k}] = 0;
        dfs(0, 0, k);
        
        if(ret == INF) ret = -1;
        
        return ret;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注