vector
里面,然后反转一下从前往后计算即可。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;
}
};
[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;
}
};
(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;
}
};
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;
}
};
本文分享自 GiantPandaCV 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!