Leetcode 第 167 场周赛题解
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输出。 - 复杂度：
- 代码：
class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector <int> ans;
set <int> s;
for(int i=1; i<=9; i++){//数有多少位
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作比较即可，如果满足就更新答案。 - 复杂度：
- 代码：
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的常规做法了。 - 复杂度：
- 代码：
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;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-12-15，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 GiantPandaCV 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
