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;
}
};