10.递归

一.判断能否形成等差数列
1.题目描述：
给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为等差数列。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

2.示例：
输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。

3.解:
（1）我的答案：
import java.util.Arrays;
class Solution {
public boolean canMakeArithmeticProgression(int[] arr) {
Arrays.sort(arr);
boolean a = false;
if(arr.length>=3){
if(canMakeArithmeticProgression(Arrays.copyOfRange(arr,0,arr.length-2))){
if(arr[arr.length-1]-arr[arr.length-2] == arr[arr.length-2]-arr[arr.length-3]) a=true;
else a=false;
}
}
else{
a=true;
}
return a;
}
}

（2）网友答案：
import java.util.Arrays;
class Solution {
public boolean canMakeArithmeticProgression(int[] arr) {
Arrays.sort(arr);
int d = arr[0] - arr[1];
for (int i = 1; i < arr.length - 1; i++)
if (d != arr[i] - arr[i + 1])
return false;
return true;
}
}
4.总结：
这里用递归并不好，因为排序这个操作和创建那个boolean变量的操作只需要一次，而我这样写就重复执行了。网友的答案是比较正常的思路，先排序然后逐个判断。

二.斐波那契数列
1.题目描述：
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

2.示例：
输入：n = 2
输出：1

3.解:
（1）我的答案：
class Solution {
public int fib(int n) {
if(n<2) return n;
else return (fib(n-1)+fib(n-2))%1000000007;
}
}

（2）网友答案：
class Solution {
public int fib(int n) {
if (n < 2) return n;
int dp1 = 0, dp2 = 1;
for (int i = 1; i < n; i++) {
int q = dp2;
dp2 = (dp2 + dp1) % (int)(1e9 + 7);
dp1 = q;
}
return dp2;
}
}

4.总结
本质上是考察递归，但是这道题目用递归，有的用例会超出时间限制。总之，知道如何递归就行了。如果不想使它超出时间限制，那么就使用网友的答案，即动态规划。

三.青蛙跳台阶问题
1.题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

2.示例：
输入：n = 2
输出：2

3.解:
（1）我的答案：
class Solution {
int method = 0;
int sum;
public int numWays(int n) {
sum = n;
jump(0);
return method;
}

public void jump (int n){
    if((sum-n)==1){
        jump(n+1);
    }
    else if((sum-n)>=2){
        jump(n+1);
        jump(n+2);
    }
    else method++;     
}

}
（2）网友答案：
class Solution {
public int numWays(int n) {
if(n<=1) return 1;
if(n==2) return 2;
int pre=1;
int next=2;
for(int i=2;i<n;i++){
int temp=next;
next=(pre+next)%1000000007;
pre=temp;
}
return next;
}
}

4.总结
和上一道题本质一模一样。。就是斐波那契数列。

四.二进制手表
1.题目描述：
二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。
每个 LED 代表一个 0 或 1，最低位在右侧。
图片说明
例如，上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。

2.示例：
输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

3.解:
（1）我的答案：
class Solution {
private int[] minutes = new int[]{0,0,0,0,32,16,8,4,2,1};
private int[] hours = new int[]{8,4,2,1,0,0,0,0,0,0};
List<string> result = new ArrayList<>();
public List<string> readBinaryWatch(int turnedOn) {
recall(turnedOn,0,0,0);
return result;
}
public void recall(int num,int index,int minute,int hour){
//剪枝操作
if (minute>59||hour>11) return;</string></string>

    //需求操作
    if(num==0){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(hour).append(":");
        if(minute<10) stringBuilder.append("0");
        stringBuilder.append(minute);
        result.add(stringBuilder.toString());
        return;
    }

    //递归操作，10条岔路
    while(index<10){
        recall(num-1,index+1,minute+minutes[index],hour+hours[index]);
        index++;
    }
}

}

4.总结：
回溯完全可以按照递归的方法去做，只不过加上剪枝操作就行。以后遇到可以递归的题目，首先假设有一个函数可以完成某个功能，然后在这个函数中写下面三部分代码：1.剪枝 2.需求代码 3.递归代码（有几条岔路就写几个递归语句，岔路多时可以用循环）。

五.比赛中的配对次数
1.题目描述：
给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：

如果当前队伍数是偶数，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
如果当前队伍数为奇数，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
返回在比赛中进行的配对次数，直到决出获胜队伍为止。

2.示例：
输入：n = 7
输出：6
解释：比赛详情：

第 1 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。
第 2 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
第 3 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 3 + 2 + 1 = 6

3.解:
class Solution {
private int result;
public int numberOfMatches(int n) {
result=0;
recall(n);
return result;
}
public void recall(int n){
if(n==1) return;
if(n%2==0&&n!=0){
result += n/2;
recall(n/2);
return;
}
if((n-1)%2==0){
result += (n-1)/2;
recall((n-1)/2+1);
return;
}
}
}

4.总结
无

六.合并两个排序的链表
1.题目描述：
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

2.示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

3.解:
（1）我的答案：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode root;
if (l1 == null && l2 != null) return l2;
if (l1 != null && l2 == null) return l1;
if (l1 == null && l2 == null) return null;
if (l1.val <= l2.val) {
root = l1;
insert(l1, l2);
} else {
root = l2;
insert(l2, l1);
}
return root;
}

public void insert(ListNode l1, ListNode l2) {
    if (l1 == null) {
        l1.next = l2;
        return;
    } else if (l2 == null) {
        return;
    } else if (l1.next == null) {
        l1.next = l2;
        return;
    } else if (l2.val <= l1.next.val) {
        ListNode temp = l1.next;
        ListNode newL2 = l2.next;
        l1.next = l2;
        l2.next = temp;
        insert(l2, newL2);
    } else insert(l1.next, l2);
}

}

（2）网友答案：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}