【leetcode】递归练习总结

爱被打了一巴掌 2022-10-17 04:18 219阅读 0赞

一、总结

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center]

二、题目

1.  递归通用模板

（1）具有返回值型  
int型 代表题目：斐波那、跳台阶、阶乘  
集合型 代表题目：杨辉三角；Java注意记录时的加入引用与实例问题。  
bool型 代表题目：2的幂、4的幂。

/** * @param n 传入参数 * @param pos 当前递归位置 * @param val 计算参数,子集的异或问题参考 * @param flag 状态判断,N皇后问题 * @return */
        T recursion(int n,int pos,int val,int []flag){  // flag可以boolean型
            T t = new T();// 返回参数,根据需要声明设定
            if(pos==flag.length){  // 终止条件,根据题目来定
                // 处理
                return t;//终止
            }
            if(flag[pos]==1){ // 根据当前状态的情况进行处理
                // 处理
            }
            // 递归进行
            // 标志位处理
            flag[pos] = 1;
            recursion(n,pos+1,val*n,flag);
            flag[pos] = 0;//标志位回退，--> 回溯模板
            recursion(n,pos+1,val*n,flag);
            return t;
        }

（2）void型模板

List<String> record = new ArrayList<>();
        // 树的遍历结构
        void dfs(TreeNode treeNode,int n,int pos){ 
            if(treeNode==null){ 
                // 递归一次结束进行记录
               // record.add(treeNode.val+"");
                // record进行记录
                return;//终止
            }
            // 进行处理数据treeNode
            dfs(treeNode.left,n,pos+1);//向左
            dfs(treeNode.right,n,pos+1);//向右
        }

1.  题目

\----斐波那数-----

基本考察，采用简单的递归公式即可解决，解决代码如下。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 1]  
但是，可以看到直接递归时间复杂度只能击败28.00%，如果题目样例再大一点应该就会超时了，因此此时就需要记忆优化来处理记录重复计算的步骤（也就是空间换时间，建议采用hash表同等情况下空间复杂度更低（比较map来说））。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 3]  
另外，可能存在很大的数，此时一般会要求取余，直接取余即可。  
其他同类型题目：

爬楼梯分析：当爬取一个楼梯则为该问题的n-1的数量，当爬取两个时则为n-2的问题规模，然后再讨论终止态一个或两个楼梯时的情况。

**返回bool型**

4的幂分析：当能整除4时则进行递推，直到问题规模为1或0，为1则true，为0则false。

boolean isPowerOfFour(int n){ 
            if(n<=0){ 
                return false;
            }else{ 
                if(n%4==0){ 
                    return isPowerOfFour(n/4);// 若是4的倍数则,进行递归 否则判断
                }else if(n==1){ // 本来就是1或除4到等于1
                    return true;
                }else// 最终非1,说明非4的幂数
                { 
                    return false;
                }
    
            }
        }

**返回集合型**  
杨辉三角：获取numRows行数据，以列表返回。

List<List<Integer>> generate(int numRows) { 
               List<Integer> list = new ArrayList<>();
               List<List<Integer>> lists = new ArrayList<>();
    
               if(numRows<=1){ 
                   for(int i=0;i<numRows;i++)
                   { 
                        list.add(1);
                   }
                   lists.add(list);
                   return lists;
               }else{ 
                   lists = generate(numRows-1);
                   list = lists.get(lists.size()-1);
    
                   List<Integer> temp = new ArrayList<>();
                   temp.add(1);
                   for(int i=0;i<list.size()-1;i++){ 
                       temp.add(list.get(i)+list.get(i+1));
                   }
                   temp.add(1);
                   lists.add(temp);
                   return lists;
               }
        }
        public List<Integer> getRow(int rowIndex) { 
                return generate(rowIndex+1).get(rowIndex);
        }

--------------------

—异或所有的子集和–

int  res = 0;
        // nums集合，pos当前的递归位置，val即为所求的值，通过外部变量进行带值出来
        public void dfs(int[]nums,int pos,int val){ 
             if(pos == nums.length){ 
                 res+=val;//记录总值，该次递归（或理解为搜索）结束，终止条件，开始处理记录数据
                 return ;
             }
             dfs(nums,pos+1,val^nums[pos]);//进行选择，进行对val的异或处理,pos+1
             dfs(nums,pos+1,val);//不选择
        }
    
        public int subsetXORSum(int[] nums) { 
            dfs(nums,0,0);
            return res;
        }

关于子集的求法，还可以采用位运算。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 4]  
官方的代码采用位运算，较为难理解，因此本人采用以下办法，也就是进行2^n次结果，每次结果需要进行len次选择，选择只有0或1 选取该数或者不选。因此遍历0-2^n-1然后判断选择情况即可。

class Solution { 
        List<List<Integer>> lists = new ArrayList<>();
        //List<Integer> temp = new ArrayList<>();
        void dfs(List<Integer> temp,int []nums,int idx){ 
        
            if(idx==nums.length){ 
                lists.add(new ArrayList<>(temp));// list加入构造？？
                return;
            }
            temp.add(nums[idx]);//选择当前
            dfs(temp,nums,idx+1);
            temp.remove((Object)nums[idx]);// 不选择
            dfs(temp,nums,idx+1);
    
        }
        public List<List<Integer>> subsets(int[] nums) { 
            // List<Integer> temp = new ArrayList<>();
            // dfs(temp,nums,0);
            // return lists;
            List<List<Integer>> allSet = new ArrayList<>();
            List<Integer> tempSet = new ArrayList<>();
            
             int len = nums.length;
             for(int i = 0; i< Math.pow(2,len); i++){ 
                 tempSet.clear();//选择之前清理
                 int n = i;
                  for(int j=0;j<len;j++){ 
                      // 进行len次选择,考虑使用移位运算
                      if(n%2==1){ 
                          tempSet.add(nums[j]);// 进行判断是否选择j
                      }
                      n = n>>1;//移位处理
                  }
                  allSet.add(new ArrayList<>(tempSet));
             }
             return allSet;
        }
    }

玩具蛇问题（对应DFS、回溯，可借鉴N皇后问题）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 5]  
该玩具可以放在4\*4任意一个位置开始，然后进行DFS搜索直到所有位置填满则为一次结构，然后回退，继续搜索。

class Point{ 
            int x,y;
            public Point(int x, int y) { 
                this.x = x;
                this.y = y;
            }
            @Override
            public String toString() { 
                return "Point{" +
                        "x=" + x +
                        ", y=" + y +
                        '}';
            }
        }
        List<List<Point>> list = new ArrayList<>();
        List<Point> record = new ArrayList<>();//记录一次轨迹
        /** * * @param matrix * @param count * @param x * @param y * @return * * 玩具蛇（国赛第五题） * * 计算数量即可,使用一个棋盘记录是否选择该位子（->排列组合？是否选择该字符 * * -> 回溯法,当选择不合理时进行回退 * * 1. * */
        int dfs(boolean [][]matrix,int count,int x,int y){ 
    
            if(x>=4||y>=4||x<0||y<0)
                return 0;// 选择不合理,计数为0,思考记录路径
            if(count==0)
                record.clear();
            if(matrix[x][y])
            { 
                record.add(new Point(x,y));
                return 0;//已走
            }
    
            if(count==15)
            { 
                list.add(record);
                return 1;// 成功选择完,具有一种可能性
            }
    
            int sum=0;
            // 表示已经走过该位子
            matrix[x][y] = true;
            sum+=dfs(matrix,count+1,x-1,y);//往左走
            sum+=dfs(matrix,count+1,x+1,y);//往右走
            sum+=dfs(matrix,count+1,x,y-1);
            sum+=dfs(matrix,count+1,x,y+1);
            matrix[x][y]=false;//若四个方向都走完则进行回退
            return sum;
        }
        void test(){ 
            boolean [][]matrix=new boolean[4][4];
            int sum=0;
            for(int i=0;i<16;i++){ // 从16个位子进行分别开始深搜
                sum+=dfs(matrix,0,i/4,i%4);
            }
            System.out.println("RS:"+sum);
            list.stream().forEach(e->{ 
                e.stream().forEach(System.out::print);
                System.out.println();
            });
        }
    
    
        /** * 排列组合字符串 */
        String str = "abc";
        String temp = "";
        List<String> recordStr = new ArrayList<>();
        int permutation(boolean[] select,int hasSelect,String str,int pos){ 
            if(pos<0||pos>=3){ 
                return 0;
            }
             if(select[pos]){ 
                System.out.println(pos);
                temp=temp+str.substring(pos,pos+1);
                return 0;//该位子已选
            }
             if(hasSelect==3){ // 已选三个
                recordStr.add(temp);
                return 1;
            }
    
            int sum = 0;
            select[pos]=true;
            sum+=permutation(select,hasSelect+1,str,pos+1);
            sum+=permutation(select,hasSelect+1,str,pos-1);
            select[pos]=false;
            return sum;
        }

最后，关于Java朋友使用List<>进行记录时，直接插入会出现空白的情况。

if(idx==nums.length){ 
                lists.add(new ArrayList<>(temp));// 不能直接lists.add(temp)
                return;
            }

原因：temp为对象引用，加入并没加入实例的数据。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/99f74b898db7488c8a17f14b3dc95880.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221014/48655ffc817942f9b5b4f650c994c316.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221014/87005ecca5d048f8aa5df3bd034eb2c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221014/adb3fb253ad9462bba3f18998dcfc43d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221014/bba6c01e0c2b4f609f03564258d4145f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221014/4002824d44ec4d8f990e1b2382637083.png