5.31号刷题

发表于 | 分类于 | 0 comments

第一题 70. Climbing Stairs

算法

利用动态规划来进行计算。分析这个问题，我们发现每遇到一个新的n，我们总是有三种方式从之前的状态到达这个新的状态，分别是A[n-2] + 2, A[n-2] + 1 + 1, A[n-1] + 1即两步之前的走一个2步，2步之前的走2个1步，1步之前的走一个1部可以到达我们目前所在的n处。但是需要注意的是，这三种方式中，A[n-2] + 1 + 1与A[n-1]一部分是重复的，所以最终对于一个新的状态n，所有的可能性为A[n-1] + A[n-2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class climbStairs70 {
    public int climbStairs(int n) {
        if (n == 0 || n == 1 || n == 2) return n;
        int[] store = new int[n];
        store[0] = 1; store[1] = 2;
        for (int i = 2; i < n; i++) {
            store[i] = store[i-1] + store[i-2];
        }
        return store[n-1];
    }
    public int climbStairs2(int n) {
        if (n == 0 || n == 1 || n == 2) return n;
        int firstStep = 1, secondStep = 2, total = 0;
        for (int i = 2; i < n; i++) {
            total = firstStep + secondStep;
            firstStep = secondStep;
            secondStep = total;
        }
        return total;
    }
}

第二题 413. Arithmetic Slices

描述

如果一组数包含至少3个元素，并且任意两个连续元素之差都相等，则称该序列为等差序列。

给定一个以0为起始下标的数组A，包含N个数字。数组的切片是指任意满足0 <= P < Q < N的整数对 (P, Q)。

数组A的切片 (P, Q) 是等差数列，如果满足下列条件：

A[P], A[p + 1], …, A[Q - 1], A[Q]是等差数列。特别的，P + 1 < Q。

函数应当返回数组A的等差数列切片的个数。

算法

具体过程参见图片，对于每一次到的n。如果现在长度为3，那么只有1种可能即3；如果长度是4，那么有两种可能，即长度为3或4，如果长度为5，那么有3中可能，即3，4，5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class numberOfArithmeticSlices413 {
    public int numberOfArithmeticSlices(int[] A) {
        if (A.length < 3) return 0;
        int sum = 0, temp = 0;
        for (int i = 2; i < A.length; i++) {
            if (A[i-1] - A[i-2] == A[i] - A[i-1]) {
                temp += 1;
                sum += temp;
            } else {
                temp = 0;
            }
        }
        return sum;
    }
}