leetcode思考记录
文章目录
33题:搜索旋转排序数组 难度中等
1.因为时间复杂度有要求,一开始想法是模拟二分法,非递归,左边不行就右边
但是非递归有个问题,某种情况无法区分在左边还是右边,所以想着用递归做
第二天想了想,因为是递增数组的旋转,可以区分在左还是右,非递归可以做,递归当然也可以
2328题:网格图中递增路径的数目 难度困难
首先,递增路径不难,二维数组每个节点为头的情况都来一遍,
感觉复杂的是对结果进行存储或是去重,用原生支持去重的数据结构进行存储,在求size的方法
感觉空间复杂度要求太高了,不考虑了
尝试将问题拆分成子规模,
A首先将起始点进行拆分,每个二维数组的节点都是一个起始点
届时,从某一个节点起始的问题就是子规模,放到循环里就行了
B假定起始点确定,需要有一个数据结构进行临时的存储,满足递增序列,
(牵扯到递归了,首先为了方便验证合法性,先将m,n的合法性确认)
代码 测试用例可以通过,但是超出了时间限制,需要想办法修改
class Solution {
public:
int countPaths(vector<vector<int>>& grid) {
int xmax = grid.size();
int ymax = grid[0].size();
int final = 0;
for(int i = 0;i<xmax;i++){
for(int j =0;j<ymax;j++){
vector<int> tmp;
findonepathnum(i,j,xmax,ymax,tmp,grid,final);
}
}
return final;
}
void findonepathnum(int m,int n,int &xmax,int &ymax,vector<int>tmp,vector<vector<int>>& grid,int &final){
if(m<0 || n <0 || m>=xmax || n >=ymax){ // 验证合法性
return;
}
int tmpsize = tmp.size();
if(tmpsize){ // 存在元素,那就要gird[m][n]和tmp中最后一个值进行比较
if(tmp[tmpsize-1] <= grid[m][n] ){
return ;
}
}
final+=1;
tmp.push_back(grid[m][n]);
//递归下去
//上情况
findonepathnum(m,n-1,xmax,ymax,tmp,grid,final);
//下情况
findonepathnum(m,n+1,xmax,ymax,tmp,grid,final);
//左情况
findonepathnum(m-1,n,xmax,ymax,tmp,grid,final);
//右情况
findonepathnum(m+1,n,xmax,ymax,tmp,grid,final);
}
};把判断从函数的一开头放到里递归之前了,测试案例多通过了几个,不知道是不是递归的原因
修改后的代码:
class Solution {
public:
int countPaths(vector<vector<int>>& grid) {
int xmax = grid.size();
int ymax = grid[0].size();
int final = 0;
for(int i = 0;i<xmax;i++){
for(int j =0;j<ymax;j++){
int now_max = -1;
findonepathnum(i,j,xmax,ymax,now_max,grid,final);
}
}
final %= 1000000007;
return final;
}
void findonepathnum(int m,int n,int &xmax,int &ymax,int now_max,vector<vector<int>>& grid,int &final){
final++;
now_max = grid[m][n];
//递归下去
//上情况
if(n-1 < ymax && n-1 >=0 && grid[m][n-1] > now_max) // 符合条件再递归
findonepathnum(m,n-1,xmax,ymax,now_max,grid,final);
//下情况
if(n+1 < ymax && n+1 >=0 && grid[m][n+1] > now_max) // 符合条件再递归
findonepathnum(m,n+1,xmax,ymax,now_max,grid,final);
//左情况
if(m-1 < xmax && m-1 >=0 && grid[m-1][n] > now_max) // 符合条件再递归
findonepathnum(m-1,n,xmax,ymax,now_max,grid,final);
//右情况
if(m+1 < xmax && m+1 >=0 && grid[m+1][n] > now_max) // 符合条件再递归
findonepathnum(m+1,n,xmax,ymax,now_max,grid,final);
return;
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论