递归&DFS

1. 递归

   • 递归问题的关键问题是找到“相似性”——>下一次递归的调用形式；和“出口”——>终止递归的语句。
   • 在构造相似性时，如果没有明显相似性需要主动构造；不能相似的原因很可能是缺少参数。

   • 递归调用仅仅是被调函数恰为主调函数

     注意每次调用的层次不同
     注意每次分配形参并非同一个变量
     注意返回次序

   • 三个简单的递归例子：

     • //打印0-n
       public static  void f(int n){
                if(n==-1) return;　  //出口
                f(n-1);　　　　　　　　//相似性
                System.out.println(n);
           }

     • //累加数组中元素  
       //begin-a.length
       public static  int  f1(int[]a,int begin){
               if(begin==a.length)  return 0;
               int x=f1(a,begin+1);
               return x+a[begin];
           }

     • //比较字符串是否相等
       public static boolean f3(String a,String b){
               if(a.length()!=b.length())return false;
               if(a.length()==0) return true;
               if(a.charAt(0)!=b.charAt(0)) return false;
               else return f3(a.substring(1),b.substring(1));
           }

   • 进阶一点点的递归问题*3

     • 在n个球中任意取出m个（不放回），求有多少种不同取法？//特殊球法
       

       • //平地起风雷
                 public static  int f2(int n,int m){
                     if(nreturn 0;
                     if(n==m) return 1;
                     if(m==0) return 1;
                     return f2(n-1,m-1)+f2(n-1,m);//使用一个特殊球x将取法做人为划分
                             //取球包含x       //取球不包含x
             }

     • 求n个元素的全排列

       • public static  void  f(char[]a,int k){//传入参数用K做区别
                     if(k==a.length){
                         for(int i=0;i){
                             System.out.print(a[i]+" ");
                         }
                         System.out.println();
                     }
                     for(int i=k;i//循环本身就是递归出口
                         char temp=a[i];a[i]=a[k];a[k]=temp;//试探
                         f(a,k+1);
                         temp=a[i];a[i]=a[k];a[k]=temp;//回溯
                     }
             }

     • 求最长公共子序列

       • //字串----连着的
         //子序列----删除任意的
         public static int f3(String s1,String s2){
                 if(s1.length()==0||s2.length()==0){
                     return 0;
                 }
                 if(s1.charAt(0)==s2.charAt(0)) return f3(s1.substring(1),s2.substring(1))+1;
                 else return Math.max(f3(s1.substring(1),s2),f3(s1,s2.substring(1)));
             }

   • 蓝桥杯的一些题目（2014年以前

     • 求反串（填空）

       • public static String reverseString(String x)
         {
             if(x==null || x.length()<2) return x;
             return reverseString(x.substring(1)) + x.charAt(0);
         }

     • 杨辉三角形 （填空）（形如

       1
       1 1
       1 2 1
       1 3 3 1
       1 4 6 4 1
       1 5 10 10 5 1

       • 计算第m层的第n个系数

       • public static int f(int m,int n){
                 if(n==0 || n==m) return 1;
                 return f(m-1,n)+f(m-1,n-1);
             }

     • 计算m个A，n个B可以组合成多少个不同的排列（填空）

       • public static int f(int m,int n){
                 if(n==0 || m==0) return 1;
                 return f(m-1,n)+f(m,n-1);
             }

     • 整数的划分问题（编程题）
       如，对于正整数n=6，可以划分为：
       6
       5+1
       4+2，4+1+1
       3+3，3+2+1，3+1+1+1
       2+2+2，2+2+1+1，2+1+1+1+1
       1+1+1+1+1+1
       现在的问题是，对于给定的正整数n，编写算法打印所有划分

       
       

       • public static void f(int n,int[]a,int k){  //a为缓冲 k为当前位置
                 if(n==0){
                     for(int i=0;i){
                         System.out.print(a[i]+" ");
                     }
                     System.out.println();
                     return;
                 }
                 for(int i=n;i>0;i--){  //i从n开始，方便写n==0的出口
                     if(k>0 &&i>a[k-1]) continue;//视频里说return太过分了
                     a[k]=i;
                     f(n-i,a,k+1);
                 }
             }

     • 某财务部门结账时发现总金额不对头。很可能是从明细上漏掉了某1笔或几笔。如果已知明细账目清单，能通过编程找到漏掉的是哪1笔或几笔吗?
       如果有多种可能，则输出所有可能的情况。
       我们规定:用户输入的第一行是:有错的总金额。
       接下来是一个整数n，表示下面将要输入的明细账目的条数。再接下来是n行整数，分别表示每笔账目的金额。
       要求程序输出:所有可能漏掉的金额组合。每个情况1行。金额按照从小到大排列，中间用空格分开。
       比如:
       用户输入:
       6
       5
       3
       2
       4
       3
       1
       表明:有错的总金额是6;明细共有5笔。
       此时、程序应该输出：
       1 3 3
       1 2 4
       3 4
       为了方便，不妨假设所有的金额都是整数，每笔金额不超过1000，金额的明细条数不超过100。

       • /*
             参数说明：
                    err_sum: 题目输入的第一行，即错误的结果
                    a: 题目输入的第3-n行，即数据集
                    k: 当前遍历到哪个位置
                    cur_sum: k位置之前的所有取到元素的累加和
                    b: 记录元素取还是不取 Boolean[] b = new Boolean[a.length];new出来即可
              */
             //其实核心思想就是数据集中的数据取还是不取的问题。
             public static void f(int err_sum,int[]a,int k,int cur_sum,Boolean[]b){
                 if(cur_sum>err_sum) return;
                 if(cur_sum==err_sum){
                     for(int i =0;i){
                         if(b[i]==false) System.out.print(a[i]+" ");
                     }
                     System.out.println();
                     return;
                 }
                 if(k>=a.length) return;//注意出口顺序，此出口如果写在前面是有逻辑错误的
         
                 b[k] = false;
                 f(err_sum,a,k+1,cur_sum,b);//不取当前位置 递归
         
                 b[k]=true;
                 f(err_sum,a,k+1,cur_sum+a[k],b);//取当前位置 递归
         
                 b[k]=false;//回溯
         
             }

     • 今天（2020.1.7）刚写到的一道力扣

       • 98.验证二叉搜索树
         给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

         有效 二叉搜索树定义如下：

         1.节点的左子树只包含 小于 当前节点的数。
         2.节点的右子树只包含 大于 当前节点的数。
         3.所有左子树和右子树自身必须也是二叉搜索树。

       •  1 /**
          2  * Definition for a binary tree node.
          3  * public class TreeNode {
          4  *     int val;
          5  *     TreeNode left;
          6  *     TreeNode right;
          7  *     TreeNode() {}
          8  *     TreeNode(int val) { this.val = val; }
          9  *     TreeNode(int val, TreeNode left, TreeNode right) {
         10  *         this.val = val;
         11  *         this.left = left;
         12  *         this.right = right;
         13  *     }
         14  * }
         15  */
         16 class Solution {
         17     public boolean isValidBST(TreeNode root,long cur_max,long cur_min){
         18         if(root==null) return true;//一开始写成了判断是否为子节点，然后就出现了是子节点不管三七二十一都true的错误
         19                                     //但其实就这样一直遍历下去就可以啦
         20         if(root.val>=cur_max||root.val<=cur_min) return false;//最开始没有想到实际上是有闭区间的 想成了开闭或者闭开区间了
         21         return isValidBST(root.left,root.val,cur_min)&&isValidBST(root.right,cur_max,root.val);//我发现我逻辑上真的很差啊 一开始刚好写反 哭哭QAQ
         22     }
         23     public boolean isValidBST(TreeNode root) {
         24         return isValidBST(root,Long.MAX_VALUE,Long.MIN_VALUE);
         25     }
         26 }

   • 小总结

     • 递归和循环是可以互通的，递归往往用于循环层数不确定时使用。也就是说如果对于一道题如果感觉能用循环那基本写递归就可以了
     • 递归无外乎是寻找相似性和出口的问题，相似性即改变传入参数使得递归向下进行；寻找出口须想好条件以及次序
     • 回溯很重要！

2. DFS

   • 写在前面

     • 深度搜索本质上就是基于递归的思想 所以我放在一起写了
       这部分没有听网课 是我照着书写的
       下面会写一些书上的例子和我做力扣遇到的例子

   • 引例

     • emm因为是照着算法书写的再加上java和c++都想练到所以可能会C++和java代码串着出现2333

     • #include
       using namespace std;
       //hdu1312 "Red and Black"
       /*
           题目： 只能走黑色
           解法： DFS 
           输入： 第一行W H表示x方向和y方向上的瓷砖数量
                  下面H行 每行W个字符
                  “·”表示黑色 “# ”表示红色 “@ ” 表示起始位置
           输出： 一个数字 表示从初始瓷砖能到达的瓷砖总数 
                   
       */ 
       char room[23][23];
       int dir[4][2]={
           {-1,0},        //left 左上角为{0，0} 
           {0,-1},        //up
           {1,0},        //right
           {0,1}        //down
       };
       int Wx, Hy, num;
       #define isInRoom(x,y) (x=0 && y>=0 && ystruct node{
           int x,y;
       };
       void DFS(int dx,int dy){
           node start,next;
           start.x=dx;
           start.y=dy;
           for(int i=0;i<4;i++){
               next.x=start.x+dir[i][0];
               next.y=start.y+dir[i][1];
               if(isInRoom(next.x,next.y)&&room[next.x][next.y]=='.'){
                   room[next.x][next.y]='#';
                   num++;
                   DFS(next.x,next.y);
               }
           }
       }
       int main(){
           int x,y,dx,dy;
           while(cin>>Wx>>Hy){
               if(Wx==0&&Hy==0) break;
               for(y=0;y){
                   for(x=0;x){
                       cin>>room[x][y];
                       if(room[x][y]=='@'){
                           dx=x;
                           dy=y;
                       }
                   }
               }
               num=1;
               DFS(dx,dy);
               cout<endl;
           }
           return 0;
       }

     • 测试用例：

       • Sample Input
         6 9
         ....#.
         .....#
         ......
         ......
         ......
         ......
         ......
         #@...#
         .#..#.
         11 9
         .#.........
         .#.#######.
         .#.#.....#.
         .#.#.###.#.
         .#.#..@#.#.
         .#.#####.#.
         .#.......#.
         .#########.
         ...........
         11 6
         ..#..#..#..
         ..#..#..#..
         ..#..#..###
         ..#..#..#@.
         ..#..#..#..
         ..#..#..#..
         7 7
         ..#.#..
         ..#.#..
         ###.###
         ...@...
         ###.###
         ..#.#..
         ..#.#..
         0 0
         Sample Output
         45
         59
         6
         13

         Red and Black测试用例
     • 回溯和剪枝之后再补充吧

   • 力扣上的一些例子

     • 113.路径总和Ⅱ
       题目描述：
       给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
       叶子节点 是指没有子节点的节点。

       
       
       • 题解： 

         /**
          * Definition for a binary tree node.
          * public class TreeNode {
          *     int val;
          *     TreeNode left;
          *     TreeNode right;
          *     TreeNode() {}
          *     TreeNode(int val) { this.val = val; }
          *     TreeNode(int val, TreeNode left, TreeNode right) {
          *         this.val = val;
          *         this.left = left;
          *         this.right = right;
          *     }
          * }
          */
         class Solution {
             List> ans = new ArrayList>() ;
             List now = new ArrayList();
             public void dfs(TreeNode root,int targetSum,int num){
                 if(root==null) return;
                 num+=root.val;
                 now.add(root.val);
                 if(root.right==null&&root.left==null){
                     if(num==targetSum){
                         ans.add(new ArrayList(now));
                     }
                     //temp-=root.val;
                     now.remove(now.size()-1);
                     return;
                     
                 }
                 if(root.left!=null) dfs(root.left,targetSum,num);
                 if(root.right!=null) dfs(root.right,targetSum,num);
                 now.remove(now.size()-1);
             }
             public List> pathSum(TreeNode root, int targetSum) {
                 dfs(root,targetSum,0);
                 return ans;
             }
         }

         113.路径总和Ⅱ
       • 代码中的一些tips：
         • ans.add(new ArrayList(now)); 如果不用new的话会把之前的结果直接覆盖掉
         • 递归问题比较难的在于参数设计 这题比较简单啦

     • 93.复原IP地址
       题目描述：
       有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
       例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
       给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

       • （对不起这是图片）

       • 题解：

         class Solution {
             static final int count = 4;
             List ans = new ArrayList();
             int[] segment = new int[count];
             
             public List restoreIpAddresses(String s) {
                 segment = new int[count];
                 dfs(s,0,0);
                 return ans;
             }
             //segID:第几个点（0-3）
             //segStart:从数组的第几个位置开始出发    
             public void dfs(String s,int segID,int segStart){
                 //都划分好
                 if(segID==count){
                     if(segStart==s.length()){
                         StringBuffer temps = new StringBuffer();
                         for(int i=0;ii){
                             temps.append(segment[i]);
                             if(i!=count-1) temps.append('.');
                         }
                         ans.add(temps.toString());
                     }
                     return;
                 }
                 if(segStart==s.length()){
                     return;
                 }
                 
                 if(s.charAt(segStart)=='0'){
                     segment[segID]=0;
                     dfs(s,segID+1,segStart+1);
                 }
         
                 int temp=0;
                 for(int segEnd = segStart;segEndsegEnd){
                     temp=temp*10+(s.charAt(segEnd)-'0');
                     if(temp>0&&temp<=0xFF){
                         segment[segID] = temp;
                         dfs(s,segID+1,segEnd+1);
                     }
                     else break;
                 }
             }
         }

         93.复原IP地址
       • 代码中的一些tips：
         • 最后一个循环里的dfs(s,segID+1,segEnd+1); 一开始传成了segStart+1答案莫名其妙的2333 
         • 要注意对于0的特殊判断 题干有说不能含有前导0

   • 未完也许会续也许会新写一片记一下回溯