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

评论

暂无评论