LeetCode递归

面试08.05 递归乘法(乘法变加法)

题目

分析

1. 不需要乘法的话我就进行多次加法进行操作

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class ChengFa {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int a=input.nextInt();
        int b=input.nextInt();
        System.out.println(multiply(a,b));
    }

    public static int multiply(int a, int b) {
        int sum=0;
        for(int i=0;i<b;i++){
            sum+=a;  //乘法就相当于多次加法
        }
        return sum;
    }

}

结果

面试08.06 汉诺塔(递归)

题目

分析

1. n=1 : 直接将a移除一个到c
2. n!=1: 先a通过c到b 然后b通过a到c(中间a移除一个到c)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class HanNuoTa {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        List<Integer> A=new ArrayList<>();
        A.add(2);
        A.add(1);
        A.add(0);
        List<Integer> B=new ArrayList<>();
        List<Integer> C=new ArrayList<>();
        hanota(A,B,C);
        System.out.println(C.toString());
    }

    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        hanota(A.size(),A,B,C);
    }
    //总体的思路：要把A的n个盘移到C上，首先要借助B把n-1个盘移开，然后把A最下面的最大的移到C
    //然后把B的n-1个盘移到C上，按照同样的逻辑
    //这个函数的意思就是将A的n个盘移到C上
    public static void hanota(int n,List<Integer> A, List<Integer> B, List<Integer> C){
        //如果A上只有一个盘，直接移到C上
        if(n==1)    {
            C.add(A.remove(A.size()-1));
            return;
        }
        //如果不是，借助c将N-1个盘移到B上
        hanota(n-1,A,C,B);
        //然后把剩下的一个移到C
        C.add(A.remove(A.size()-1));
        //把B的移到C上
        hanota(n-1,B,A,C);
    }

}

结果

面试16.11 跳水板(等差数列)

题目

分析

1. 假设是最短是1 最长是2 有k=3个模板求结果。
2. 取值就是 111 112 122 222(中间每次差了2-1的值)，取值的个数就是k+1个。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class TiaoShuiBan {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int shorter=input.nextInt();
        int longer=input.nextInt();
        int k=input.nextInt();
        System.out.println(Arrays.toString(divingBoard(shorter,longer,k)));
    }

    public static int[] divingBoard(int shorter, int longer, int k) {
        // 最小值
        int min = shorter * k;  //就是可能性中最小取值
        // 最大值
        int max = longer * k;  //就是可能性中最大取值
        // 差值
        int difference = longer - shorter;  //每一次可能中差的一次结果
        //数组长度
        int len=0;
        if (k != 0) {
            if (difference == 0) {   //最长和最短一样： 可能性就只有一种
                len = 1;
            } else {
                len = k+1;  // 最长和最短不一样： 长度是k+1
            }
        }
		
        int[] nums = new int[len];  //存放可能性的值
        for (int i = 0; i <len; i++) {
            if (i == 0) {
                nums[i] = min; //最小的可能就是k次都是最短的
            } else {
                nums[i] = nums[i-1] + difference; //后面的每一次可能就是前面的加上两者差
            }
        }
        return nums;
    }

}

结果

面试17.12 BiNode

题目

分析

代码

1
2


结果

面试10-I 斐波那契数列(递归/动态规划)

题目

分析

1. 递归：return fib(n-1)+fib(n-2)
2. 动态规划：就是abc三个数字不断后移
    sum = (a + b) % 1000000007;  //第三个数字
    a = b;    //原来的第二个是下一轮的第一个
    b = sum;  //原来的第三个是下一轮的第二个

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class FeiBo {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        System.out.println("递归:"+fib(n));
        System.out.println("动态规划:"+dongtai(n));
    }
    //递归
    public static int fib(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }
    //动态规划
    public static int dongtai(int n) {
        int a = 0, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }

}

结果

面试10-II 青蛙跳台阶(递归/动态规划)

题目

分析

1. 和斐波那契数列一样！！！！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class QingWa {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        System.out.println(numWays(n));
        System.out.println(numWayser(n));
    }

    //递归
    public static int numWays(int n) {
        if(n==1){
            return 1;  //1
        }
        if(n==2){
            return 2; // 11/2
        }
        return numWays(n-1)+numWays(n-2);
    }

    //动态规划
    public static int numWayser(int n) {
        int a=1;
        int b=2;
        int c=0;
        for(int i=1;i<n;i++){
            c=(a+b)%1000000007;
            a=b;
            b=c;
        }
        return a;
    }

}

结果

面试16. 数值的整数次方(分析特殊情况)

题目

分析

1. 底为0结果就是0
2. 指为0结果就是1
3. 底不为0指数是正数(>1)  正常for循环计算
4. 底不为0指数是负数  先负数转正数后for循环计算

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class ShuZhengCiFang {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        Double x=input.nextDouble();
        int n=input.nextInt();
        System.out.printf("%.5f",cifang(x,n));
    }

    public static double cifang(double base,int exponent){
        double c=1;
        //底为0
        if(base==0){
            return 0;
        }
        if(exponent==0){  //任何数的0次方都是1
            return 1;
        }
        //底不为0  指数是负数
        if(exponent<0){
            exponent=-exponent;
            while (exponent--!=0) {  //有多少m就乘多少次n
                c*=base;  //c=c*n 在前面的基础上乘n
            }
            c=1.0/c;  //取倒数
        }
        //底不为o  指数大于等于1
        if(exponent>=1) {
            while (exponent--!=0) {  //有多少m就乘多少次n
                c*=base;  //c=c*n 在前面的基础上乘n
            }
        }
        return c;
    }

}

结果

生成最小高度树(递归)

题目

分析

1. 使用递归法解决
2. 因为要高度最小所以尽量左右子树要多,所以选数组中间元素为根节点
3. 然后生成根节点n，n的值为数组中间节点
4. n的左节点为递归调用(0--nums.length/2)
5. n的右节点为递归调用(nums.length/2+1--nums.length)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0) {
            return null;  //数组为空
        }
        TreeNode n = new TreeNode(nums[nums.length/2]);  //取最中间的值作为根节点
     //使用Arrays.copyOfRange()方法进行递归
        n.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,nums.length/2));
        n.right = sortedArrayToBST(Arrays.copyOfRange(nums,nums.length/2+1,nums.length));
        return n;  //返回n节点
    } 
}

结果

二叉搜索树范围和(深度优先遍历)

题目

分析

https://leetcode-cn.com/problems/range-sum-of-bst/solution/hua-jie-suan-fa-938-er-cha-sou-suo-shu-de-fan-wei-/

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static int rangeSumBST(TreeNode root, int L, int R) {
        if(root==null){  //为空
            return 0;
        }
        if(root.val<L){
            return rangeSumBST(root.right,L,R);  //当前节点<L  返回右子树之和
        }
        if(root.val>R){
            return rangeSumBST(root.left,L,R);  //当前节点>R  返回左子树之和
        }
        //当前节点值+左子树之和+右子树之和
        return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
    }

结果

单值二叉树

题目

分析

1. 左子树和根节点不同 返回fasle
2. 右子树和根节点不同 返回false
3. 递归return返回 左子树&&右子树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

public boolean isUnivalTree(TreeNode root) {
       if (root == null) {
           return true;  //空树就是true
       }
       if (root.left != null && root.val != root.left.val) {  //左树不为空 && 根节点值!=左子树节点
           return false;
       }
       if(root.right != null && root.val != root.right.val) { //右树不为空 && 根节点值!=右子树节点
           return false;
       }
       return isUnivalTree(root.left) && isUnivalTree(root.right);  //递归分析左右节点
   }

结果

各位相加(递归)

题目

分析

1. 使用进制取每一位增加给temp，然后递归找到temp<10就弹出

代码

1
2
3
4
5
6
7
8
9
10
11
12

public int addDigits(int num) {
       if (num < 10) {
           return num;  //如果是小于10的值就返回
       }
       int temp = 0;
       while (num != 0) {
           temp=temp+num%10;  //每一位增加
           num/=10;  //数组缩小
       }
       return addDigits(temp);  //递归找temp
   }

结果

数字翻译成字符串(递归)

题目

分析

1. 这道题其实就是一个递归：递归出口是num是只有一位数，
2. 以xyzcba为例，先取最后两位（个位和十位）即ba，
    2.1 如果ba>=26，必然不能分解成f(xyzcb)+f(xyzc)，此时只能分解成f(xyzcb);
    2.2 但还有一种情况，就是ba<=9,也就是该数十位上为0，此时只能分解成f(xyzcb);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

public int translateNum(int num) {  //递归
      if (num<=9) {
         return 1;   //最后num是个位数小于等于9
      }
     //xyzcba为例
     int ba = num%100;  //取最后两位
     if (ba<=9||ba>=26) {
         return translateNum(num/10);  //如果ba>=26，必然不能分解成f(xyzcb)+f(xyzc)，此时只能分解成f(xyzcb)
                                     //但还有一种情况，就是ba<=9,也就是该数十位上为0 也只能分解成f(xyzcb)
     }
     return translateNum(num/10)+translateNum(num/100);  //其他情况下就是最后一位和倒数第二位
 }

结果

#

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:LeetCode递归

文章作者:Larkkkkkkk

发布时间:2020年06月11日 - 15时34分

最后更新:2020年11月25日 - 10时43分

原始链接:https://larkkkkkkk.github.io/2020/06/11/LeetCode%E9%80%92%E5%BD%92/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 面试08.05 递归乘法(乘法变加法)
    1. 1.1. 题目
    2. 1.2. 分析
    3. 1.3. 代码
    4. 1.4. 结果
  2. 2. 面试08.06 汉诺塔(递归)
    1. 2.1. 题目
    2. 2.2. 分析
    3. 2.3. 代码
    4. 2.4. 结果
  3. 3. 面试16.11 跳水板(等差数列)
    1. 3.1. 题目
    2. 3.2. 分析
    3. 3.3. 代码
    4. 3.4. 结果
  4. 4. 面试17.12 BiNode
    1. 4.1. 题目
    2. 4.2. 分析
    3. 4.3. 代码
    4. 4.4. 结果
  5. 5. 面试10-I 斐波那契数列(递归/动态规划)
    1. 5.1. 题目
    2. 5.2. 分析
    3. 5.3. 代码
    4. 5.4. 结果
  6. 6. 面试10-II 青蛙跳台阶(递归/动态规划)
    1. 6.1. 题目
    2. 6.2. 分析
    3. 6.3. 代码
    4. 6.4. 结果
  7. 7. 面试16. 数值的整数次方(分析特殊情况)
    1. 7.1. 题目
    2. 7.2. 分析
    3. 7.3. 代码
    4. 7.4. 结果
  8. 8. 生成最小高度树(递归)
    1. 8.1. 题目
    2. 8.2. 分析
    3. 8.3. 代码
    4. 8.4. 结果
  9. 9. 二叉搜索树范围和(深度优先遍历)
    1. 9.1. 题目
    2. 9.2. 分析
    3. 9.3. 代码
    4. 9.4. 结果
  10. 10. 单值二叉树
    1. 10.1. 题目
    2. 10.2. 分析
    3. 10.3. 代码
    4. 10.4. 结果
  11. 11. 各位相加(递归)
    1. 11.1. 题目
    2. 11.2. 分析
    3. 11.3. 代码
    4. 11.4. 结果
  12. 12. 数字翻译成字符串(递归)
    1. 12.1. 题目
    2. 12.2. 分析
    3. 12.3. 代码
    4. 12.4. 结果
  13. 13. #
,