10.1斐波那契数列

题目
牛客网
思路
方法：迭代相加
斐波那契数列初始化第1项与第2项都是1，则根据公式第0项为0，可以按照斐波那契公式累加到第n项。

复杂度分析：

  • 时间复杂度：O(n)，其中n为输入的数，n次迭代
  • 空间复杂度：O(1)，常数级变量，没有其他额外辅助空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int Fibonacci(int n) {

				// 从0开始，第0项是0，第一项是1
        if (n <= 1) {
            return n;
        }
        
        int res = 0;
        int a = 0;
        int b = 1;
        
        // 因n=2时也为1，初始化的时候把a=0，b=1
        for (int i = 2;i <= n;i++) {
        		// 第三项开始是前两项的和,然后保留最新的两项，更新数据相加
            res = (a + b);
            a = b;
            b = res;
        }
        
        return res;
    }
}

10.2矩形覆盖

题目
牛客网
思路
方法：动态规划

  • n = 1的时候
    • 只能竖着覆盖，1种
  • n = 2的时候
    • 可以竖着和横着覆盖，2种
  • n = 3的时候
    • 第三级竖着覆盖，用了一级，剩下 n = 2，有2种覆盖方法
    • 第三级横着覆盖，用了两级，剩下 n = 1，有1种覆盖方法
    • 总共有3种
  • n = 4的时候
    • 第四级竖着覆盖，用了一级，剩下 n = 3，有3种覆盖方法
    • 第四级横着覆盖，用了两级，剩下 n = 2，有2种覆盖方法
    • 总共有5种
  • n = n的时候
    • 第n级竖着覆盖，用了一级，剩下 n = n - 1，所以关注第 n - 1 种有几种覆盖方法
    • 第n级横着覆盖，用了两级，剩下 n = n - 2，所以关注第 n - 2 种有几种覆盖方法
    • 总和为两种情况的总和

复杂度分析：

  • 时间复杂度：O(n)，一次遍历
  • 空间复杂度：O(1)，常数级变量，没有其他额外辅助空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int rectCover(int target) {

        if (target <= 2) {
            return target;
        }
        
        int res = 0;
        int a = 1;
        int b = 2;
        
        for (int i = 3;i <= target;i++) {
            res = a + b;
            
            // 变量更新
            a = b;
            b = res;
        }
        
        return res;
    }
}

10.3跳台阶

题目
牛客网
思路
方法：动态规划
当 n = 1 时，只有一种跳法。
当 n = 2 时，有两种跳法。
跳 n 阶台阶，可以先跳 1 阶台阶，再跳 n-1 阶台阶；或者先跳 2 阶台阶，再跳 n-2 阶台阶。

复杂度分析：

  • 时间复杂度：O(n)，一次遍历
  • 空间复杂度：O(1)，常数级变量，没有其他额外辅助空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int rectCover(int target) {

        if (target <= 2) {
            return target;
        }
        
        int res = 0;
        int a = 1;
        int b = 2;
        
        for (int i = 3;i <= target;i++) {
            res = a + b;
            
            // 变量更新
            a = b;
            b = res;
        }
        
        return res;
    }
}

10.4变态跳台阶

题目
牛客网
思路
方法：动态规划
跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去…，那么

1
f(n-1) = f(n-2) + f(n-3) + ... + f(0)

同样，跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去… ，那么
1
f(n) = f(n-1) + f(n-2) + ... + f(0)

综上可得
1
f(n) - f(n-1) = f(n-1)

即
1
f(n) = 2*f(n-1)

复杂度分析：

  • 时间复杂度：O(n)，一次遍历
  • 空间复杂度：O(1)，常数级变量，没有其他额外辅助空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int jumpFloorII(int target) {

        if (target <= 1) {
            return target;
        }
        
        // 初始化上一种结果
        int pre = 1;
        
        // 初始化最终结果
        int res = 0;
        
        for (int i = 2;i <= target;i++) {
            res = 2 * pre;
            pre = res;
        }
        
        return res;
    }
}

42.连续子数组的最大和

题目
牛客网
思路
方法：动态规划
设动态规划列表 dp，dp[i] 代表以元素 array[i] 为结尾的连续子数组最大和。
状态转移方程： dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
dp[i]与dp[ i - 1]是否大于0相关：

  • dp[i] = dp[i - 1] + array[i]，dp[i - 1] > 0
  • dp[i] = array[i] ，dp[i - 1] <= 0

假设：在看到这种思路时提出了一个问题，那就是假设：dp[i - 1] = dp[i - 2] + 正整数，那么当dp[i - 1] < 0 的时候，为什么要抛弃array[i]之前的所有数呢？毕竟array[i] + 正整数也是比array[i]要更大的。
证明：当dp[i - 1] = dp[i - 2] + 正整数，那么必定有dp[i - 2] > 0，那么dp[i - 1]一定也 > 0，所以以上假设中dp[i - 1] < 0不成立，所以以上问题不存在。

复杂度分析：

  • 时间复杂度：O(n)，一次遍历
  • 空间复杂度：O(1)，常数级变量，没有其他额外辅助空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
       
        int sum = 0;
        int maxSum = array[0];
        
        for (int i = 0;i < array.length;i++) {
        
        		// 状态转移：连续子数组和最大值
            sum = Math.max(sum + array[i], array[i]);
            
            // 维护最大值
            maxSum = Math.max(maxSum, sum);
        }
        
        return maxSum;
    }
}

47.礼物的最大价值

题目
牛客网
思路
方法：动态规划
如果我们现在已经身处最右下角的一个格子，获取了这个礼物，那我们肯定是加上来自左边累计的最大礼物价值与来自上边累计的最大礼物价值的较大值，这样我们能获取的礼物价值才会更大，因此我们用dp[i][j]表示从左上角到第i行第j列的格子总共能获取的最大价值，因此转移方程为：

1
dp[i][j] = grid[i][j] + max(dp[i−1][j], dp[i][j−1]))

复杂度分析：

  • 时间复杂度：O(mn)，其中m、n分别为矩阵的边长，遍历整个矩阵
  • 空间复杂度：O(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
public class Solution {
    public int maxValue (int[][] grid) {
        
        int m = grid.length;
        int n = grid[0].length;
        
        // 第一列只能来自上方
        for (int i = 1;i < m;i++) {
            grid[i][0] += grid[i - 1][0];
        }
        
        // 第一行只能来自左边
        for (int i = 1;i < n;i++) {
            grid[0][i] += grid[0][i - 1];
        }
        
        // 遍历后续每一个位置
        for (int i = 1;i < m;i++) {
            for (int j = 1;j < n;j++) {
            		// 增加来自左边的与上边的之间的较大值
                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        
        return grid[m - 1][n - 1];
    }
}

48.最长不含重复字符的子字符串

题目
牛客网
思路
方法：动态规划+哈希表
如果对于某个前面的子串，如果我们新加入一个字符，与前面的都不重复，那么最长无重复子串肯定就是在前面的基础上加1，如果与前面重复了，那就是当前位置减去它重复之前字符出现的位置的长度。因此我们使用动态规划递推。

复杂度分析：

  • 时间复杂度：O(n)，其中n为字符串长度，遍历一次字符串
  • 空间复杂度：O(n)，辅助数组dp的大小为字符串长度，哈希表的最大空间为字符串长度
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
import java.util.*;


public class Solution {
    public int lengthOfLongestSubstring (String s) {
    
        // 哈希表记录窗口内非重复的字符及其下标
        HashMap<Character, Integer> mp = new HashMap<>();
        
        int res = 0;
        
        // dp[i]表示以下标i结尾的字符串最长不含重复子串的长度
        int[] dp = new int[s.length() + 1];
        
        for (int i = 1;i <= s.length();i++) {
            
            // 哈希表中没有，说明不重复
            if (!mp.containsKey(s.charAt(i - 1))) {
            		// 前一个加1
                dp[i] = dp[i - 1] + 1;
            }
            // 遇到重复字符
            else {
                dp[i] = Math.min(dp[i - 1] + 1, i - mp.get(s.charAt(i - 1)));
            }
            
            // 加入哈希表
            mp.put(s.charAt(i - 1), i);
            
            // 维护最大值
            res = Math.max(res, dp[i]);
        }
        
        return res;
    }
}

49.丑数

题目
牛客网
思路
方法：动态规划
我们知道丑数是由1开始的每个丑数依次乘上2、3、5得到，而我们每次只需要在其中找到最小的一个，一共找n次即可。我们可以用i、j、k三个下标表示在已经找到的丑数中那个数分别被乘2、乘3、乘5有无被记录过，然后依次找n个数字就可以了。

复杂度分析：

  • 时间复杂度：O(n)，只需要遍历一次
  • 空间复杂度：O(n)，记录丑数的数组最大长度为n
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.*;
public class Solution {
    
    // 寻找三个数中的最小值
    public int findMin(int x, int y, int z) {
            int res = Math.min(x, y);
            res = Math.min(res, z);
            return res;
        }
    
    public int GetUglyNumber_Solution(int index) {
        
        // 排除0
        if (index == 0) {
            return 0;
        }
        
        // 按顺序记录丑数
        ArrayList<Integer> list = new ArrayList<>();
        
        list.add(1);
        
        // 记录这是第几个丑数
        int count = 1;
        
        // 分别代表要乘上2 3 5的下标
        int i = 0, j = 0, k = 0;
        
        while (count < index) {
            
            // 找到三个数中最小的丑数
            list.add(findMin(list.get(i) * 2, list.get(j) * 3, list.get(k) * 5));
            
            count++;
            
            // 由2与已知丑数相乘得到的丑数，那该下标及之前的在2这里都用不上了
            if (list.get(count - 1) == list.get(i) * 2) {
                i++;
            }
            
            // 由3与已知丑数相乘得到的丑数，那该下标及之前的在3这里都用不上了
            if (list.get(count - 1) == list.get(j) * 3) {
                j++;
            }
            
            // 由5与已知丑数相乘得到的丑数，那该下标及之前的在5这里都用不上了
            if (list.get(count - 1) == list.get(k) * 5) {
                k++;
            }
        }
        
        return list.get(count - 1);
    }
}

66.构建乘积数组

题目
题目主要信息：

  • 给定一个数组A，要求返回数组B，数组B每个元素等于数组A所有元素除了对应下标以外的全部元素的乘积
  • 即B[i]=A[0]∗A[1]∗…∗A[i−1]∗A[i+1]∗…∗A[n−1]
  • 程序不能使用除法
1
2
输入：[1,2,3,4,5]
返回值：[120,60,40,30,24]

思路
方法：双向遍历
矩阵中由对角线1将其分成了上三角和下三角。我们先看下三角，如果我们累乘的时候，B[1]是在B[0]的基础上乘了新增的一个A[0]，B[2]是在B[1]的基础上乘了新增的一个A[1]，那我们可以遍历数组的过程中不断将数组B的前一个数与数组A的前一个数相乘就得到了下三角中数组B的当前数。同理啊，我们在上三角中，用一个变量存储从右到左的累乘，每次只会多乘上一个数字。这样，两次遍历就可以解决。

复杂度分析：

  • 时间复杂度：O(n)，其中n为数组A的长度，遍历两次数组
  • 空间复杂度：O(n)，数组B为返回必要空间，不属于额外空间
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
public class Solution {
    public int[] multiply(int[] A) {

				// 初始化数组B
        int[] B = new int[A.length];
        
        B[0] = 1;
        
        // 先乘左边，从左到右
        for (int i = 1;i < A.length;i++) {
            
            // 每多一位由数组B左边的元素多乘一个前面A的元素
            B[i] = B[i - 1] * A[i - 1];
        }
        
        int temp = 1;
        
        // 再乘右边，从右到左
        for (int i = A.length - 1;i >= 0;i--) {
        		// temp为右边的累乘
            B[i] *= temp;
            temp *= A[i];
        }
        
        return B;
    }
}