【leetcode】递归练习总结

一、总结

二、题目

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;//终止}// 进行处理数据treeNodedfs(treeNode.left,n,pos+1);//向左dfs(treeNode.right,n,pos+1);//向右}

2. 题目

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

基本考察，采用简单的递归公式即可解决，解决代码如下。

但是，可以看到直接递归时间复杂度只能击败28.00%，如果题目样例再大一点应该就会超时了，因此此时就需要记忆优化来处理记录重复计算的步骤（也就是空间换时间，建议采用hash表同等情况下空间复杂度更低（比较map来说））。


另外，可能存在很大的数，此时一般会要求取余，直接取余即可。
其他同类型题目：

爬楼梯分析：当爬取一个楼梯则为该问题的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到等于1return 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+1dfs(nums,pos+1,val);//不选择}public int subsetXORSum(int[] nums) {dfs(nums,0,0);return res;}

关于子集的求法，还可以采用位运算。

官方的代码采用位运算，较为难理解，因此本人采用以下办法，也就是进行2^n次结果，每次结果需要进行len次选择，选择只有0或1 选取该数或者不选。因此遍历0-2^n-1然后判断选择情况即可。

class Solution {List<List<Integer>> lists = new ArrayList<>();//List 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 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皇后问题）

该玩具可以放在4*4任意一个位置开始，然后进行DFS搜索直到所有位置填满则为一次结构，然后回退，继续搜索。

class Point{int x,y;public Point(int x, int y) {this.x = x;this.y = y;}@Overridepublic 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为对象引用，加入并没加入实例的数据。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！