1290. 二进制链表转整数

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

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

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

Solution

先求这个链表有多长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int a[35];
        int cnt = 0;
        
        while (head != NULL) {
            a[cnt++] = head->val;
            head = head->next;
        }
        int res = 0;
        for (int i = 0; i < cnt; i++)
            res += (1<<(cnt-i-1))*a[i];
        return res;
    }
};

1291. 顺次数

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

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

1
2
输出：low = 100, high = 300
输出：[123,234]

Solution

找规律或者打表都可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        int l, h;
        int templ = low, temph = high;
        l = h = 0;
        while (templ) {
            l++;
            templ /= 10;
        }
        while (temph) {
            h++;
            temph /= 10;
        }
        vector<int> ans;
        for (int i = l; i <= h; i++) {
            long long s = 0, t = 1, cnt = 0;
            for (int j = i; j >= 1; j--) {
                s += j*t;
                cnt += t;
                t *= 10;
            }
            for (int j = 0; j <= 9-i; j++) {
                if (s >= low && s <= high)
                    ans.push_back((int)s);
                s += cnt;
            }
        }
        return ans;
    }
};

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

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

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

1
2
输入：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

Solution

二维前缀和预处理，然后枚举正方形边长，判断是否符合，时间复杂度 \(O(n^3)\)

优化：

枚举边长这一步可以使用二分法，因为正方形内的和随边长的增加而增大，满足二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        const int n = mat.size();
        const int m = mat[0].size();
        int psum[305][305];

        memset(psum, 0, sizeof psum);

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)    
                psum[i][j] = psum[i][j-1]+psum[i-1][j]-psum[i-1][j-1]+mat[i-1][j-1];
        
        int len = min(n, m);
        int ans = 0;

        for (int k = 1; k <= len; k++)
            for (int i = 1; i+k-1 <= n; i++)
                for (int j = 1; j+k-1 <= m; j++) {
                    int ex = i+k-1, ey = j+k-1;
                    if (psum[ex][ey]-psum[ex][j-1]-psum[i-1][ey]+psum[i-1][j-1] <= threshold)
                    ans = max(k, ans);
                }
        return ans;
    }
};

1293. 网格中的最短路径

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

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

1
2
3
4
5
6
7
8
9
10
11
12
输入： 
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).

Solution

在普通的 BFS 上多加一个状态记录当前最多还可以消除几个障碍物。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    struct node {
        int x, y, step, k;
        node() {x = y = step = k = 0;}
        node(int x, int y, int step, int k): x(x), y(y), step(step), k(k) {}
    };

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

    int shortestPath(vector<vector<int>>& grid, int k) {
        const int n = grid.size();
        const int m = grid[0].size();
        bool vis[n+1][m+1][k+1];
        memset(vis, false, sizeof vis);

        queue<node> q;
        node s;
        s.k = k;
        q.push(s);
        vis[0][0][k] = true;

        while (!q.empty()) {
            node top = q.front();
            q.pop();
            if (top.x == n-1 && top.y == m-1) return top.step;

            for (int i = 0; i < 4; i++) {
                int nx = top.x+dir[i][0];
                int ny = top.y+dir[i][1];
                if (nx < 0 || nx >= n || ny < 0
                || ny >= m) continue;
                if (grid[nx][ny]) {
                    if (top.k && !vis[nx][ny][top.k-1]) {
                        q.push(node(nx, ny, top.step+1, top.k-1));
                        vis[nx][ny][top.k-1] = true;
                    }
                } else {
                    if (!vis[nx][ny][top.k]) {
                        q.push(node(nx, ny, top.step+1, top.k));
                        vis[nx][ny][top.k] = true;
                    }
                }
                
            }
        }
        return -1;
    }
};