leetcode-爬楼梯

假设你正在爬楼梯。需要 n 步你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

1
2
3
4
5
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 步 + 1 步
2.  2 步

示例 2：

1
2
3
4
5
6
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 步 + 1 步 + 1 步
2.  1 步 + 2 步
3.  2 步 + 1 步

1:思路

1
2
3
4
假设一直a[n-1]之前的所有情况，此时增加一个台阶，那么最后增加的这个台阶有两种case：
1:最后这个是一步，那么爬上来的方式数量=a[n-1]
2:最后这个是两步种的一步，那么爬上来的方式数量=a[n-2]
所以：a[n]=a[n-1]+a[n-2];

2:代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int climbStairs(int n) {
        //a[n]= a[n-1]+a[n-2]
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int i=1;
        int j=2;
        for(int k=3;k<=n;k++){
            int temp = i+j;
            i=j;
            j=temp;
        }
        return j;
    }
}

leetcode-最大子序列和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

1：动态规划 O(n)

思路：

1
2
3
动态式：sum[i]:以i为结尾的最大子序列=Max{sum[i-1]+a[i],a[i]};

可以计算出以a[i]为结尾的最大子序列和，从中选出最大的。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSubArray(int[] nums) {
        //sum[i]:以a[i]为结尾的最大子序列和=max{sum[i-1]+a[i],a[i]}
        if(nums.length==0){
            return nums[0];
        }
        int max=nums[0];
        int maxPre=nums[0];
        for (int i = 1;i<nums.length;i++){
            int temp= nums[i]>(maxPre+nums[i])?nums[i]:(maxPre+nums[i]);
            maxPre=temp;
            max=max>temp?max:temp;
        }
        return max;
    }
}

2:分治法O(nLogn)

思路：

1
2
将数组分成两份，左边跟右边，那么最大的子序列 = Max {left,right,center}
递归结束条件：只有一个元素，return 该元素的值；

代码示例：

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
39
public int binarySubArray(int[] nums,int left,int right){
   
    if(left == right){
        return nums[left];
    }
    int center = (right +left )>>1;
    int leftMaxValue = binarySubArray(nums,left,center);//左边的最大子序列和
    int rightMaxValue = binarySubArray(nums,center+1,right);//右边的最大子序列和
    
    int centerLeftMaxValue=0;//从中心往左遍历找到的最大值（必须包含中心点）
    int centerRightMaxValue=0;//从中心往右遍历找到的最大值（必须包含中心点）
    
    int sumLeft=0;//用于记录遍历左侧的sum值
    int sumRight=0;//用于记录遍历右侧的sum值

    for(int i=center ;i>=left;i--){
        if(i==center){
            centerLeftMaxValue=nums[i];
            sumLeft=nums[i];
            continue;
        }
        sumLeft+=nums[i];
        centerLeftMaxValue=centerLeftMaxValue>sumLeft?centerLeftMaxValue:sumLeft;
    }
    
    for(int j =center+1;j<=right;j++){
        if(j==center+1){
            centerRightMaxValue=nums[j];
            sumRight=nums[j];
            continue;
        }
        sumRight+=nums[j];
        centerRightMaxValue=
            centerRightMaxValue>sumRight?centerRightMaxValue:sumRight;
    }        
    //返回Max{left,right,center}
    int sum = leftMaxValue>rightMaxValue?leftMaxValue:rightMaxValue;
    return sum>(centerLeftMaxValue+centerRightMaxValue)?sum:(centerLeftMaxValue+centerRightMaxValue);
}