0%

LeetCode算法经典题集(四)

标注

来源:力扣(LeetCode
链接:https://leetcode-cn.com/problemset/algorithms/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

39.组合总和(回溯)

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

题解

target = 7candidates = [2,3,6,7]为例讲解

回溯算法backtrace,设置三个参数

Stack<Integer> subComb:来存储组合数字列表
int pos:当前进行到的candidates的数字坐标
int left:当前组合数之和与target的差的余数

这里有一个细节,每次进行回溯的候选数字下标不减,要么是当前的,要么下一个

首先用一个泛型为Integer的栈存储当前组合,利于回溯操作

回溯过程,在循环里附加left - candidates[i]的剪枝操作

附上一张树形图演示过程

代码如下,易读

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
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private int[] candidates;
private int len;

/**
* 回溯算法
* @param subComb 组合
* @param pos 当前进行到的数组候选坐标
* @param left 当前组合数之和与 target 的差的余数
*/
private void backtrace(Stack<Integer> subComb, int pos, int left) {
if (left == 0) {
result.add(new ArrayList<>(subComb));
return;
}
// 利用 left - candidates[i] >= 0 进行剪枝
for (int i = pos; i < len && left - candidates[i] >= 0; i++) {
subComb.push(candidates[i]);
backtrace(subComb, i, left - candidates[i]);
subComb.pop();
}
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.candidates = candidates;
this.len = candidates.length;
if (len == 0) {
return result;
}
// 先进行排序,利于算法进行
Arrays.sort(candidates);
backtrace(new Stack<Integer>(), 0, target);
return result;
}
}

40.组合总和 II(回溯)

题目

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1, 2, 2],
[5]
]

题解

和上一题基本一样,加上一步去重步骤即可

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
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private int[] candidates;
private int len;

/**
* 回溯算法
* @param subComb 组合
* @param pos 当前进行到的数组候选坐标
* @param left 余数
*/
private void backtrace(Stack<Integer> subComb, int pos, int left) {
if (left == 0) {
result.add(new ArrayList<>(subComb));
return;
}
for (int i = pos; i < len && left - candidates[i] >= 0; i++) {
// 去重
if (i > pos && candidates[i] == candidates[i - 1]) {
continue;
}
subComb.push(candidates[i]);
backtrace(subComb, i + 1, left - candidates[i]);
subComb.pop();
}
}

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
this.candidates = candidates;
this.len = candidates.length;
if (len == 0) {
return result;
}
Arrays.sort(candidates);
backtrace(new Stack<Integer>(), 0, target);
return result;
}
}

41.缺失的第一个正数

题目

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [3,4,-1,1]
输出: 2

示例 3:

输入: [7,8,9,11,12]
输出: 1

题解

思路

这题看似简单,实则困难,要求在 O(1) 的空间复杂度下完成,限制了很多做法

官方题解

如果不考虑空间复杂度,简单的做法就是用一个哈希表HashMap<Integer, Boolean>来判断是否存在某个正整数

现在不使用这种方法,而借鉴这种 使用索引作为哈希键值 的想法

最终的想法是 使用索引作为哈希键 以及 元素的符号作为哈希值 来实现是否存在的检测

例如,nums[2] 元素的负号意味着数字 2 出现在 nums数组中
nums[3] 元素的正号表示 3 没有出现在 nums 数组中

为了完成此操作,我们遍历一遍数组(该操作在数据预处理使得数组中只有正数的操作后),检查每个元素值 elem 以及将nums[elem] 元素的符号变为符号来表示数字elem 出现在 nums 数组中。注意,当数字出现多次时需要保证符号只会变化 1 次

算法

  • 检查数字1是否出现在数组中,如果没有直接return 1
  • 如果只有一个元素且nums = [ 2 ]return 2
  • 过滤元素,将负数、0和大于n的数都转化为1
  • 遍历数组,当读到数字 a 时,替换第 a 个元素的符号(注意重复元素:只能改变一次符号。由于没有下标 n ,使用下标 0 的元素保存是否存在数字 n
  • 再次遍历数组,返回第一个正数元素的下标
  • 如果 nums[0] > 0,说明不存在元素n,那么return n
  • 如果之前的步骤中没有发现数组 nums 中有正数元素,说明数组是1 ~ n的全排列,那么return n + 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public int firstMissingPositive(int[] nums) {
int n = nums.length;

// 先考虑数组是否存在 1 的情况
boolean containsOne = false;
for (int i = 0; i < n; i++) {
if (nums[i] == 1) {
containsOne = true;
break;
}
}
if (n == 0 || !containsOne) {
return 1;
}

// 到这步说明一定有 1,如果条件成立,说明只有一个 1
if (n == 1) {
return 2;
}

// 用 1 替换负数、0 和大于 n 的数
for (int i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = 1;
}
}

// 首先,所有范围在 1 ~ n 之外的元素都不存在了,其他元素保持
// 那么接下来就可以使用索引和符号作为检查器
// 例如,如果 nums[1] 是负数表示在数组中出现了数字 1
// 如果 nums[2] 是正数 表示数字 2 没有出现
for (int i = 0; i < n; i++) {
int a = Math.abs(nums[i]);
if (a == n) {
nums[0] = -Math.abs(nums[0]);
} else {
nums[a] = -Math.abs(nums[a]);
}
}

// 现在,第一个整数的下标就是缺失的第一个数
for (int i = 1; i < n; i++) {
if (nums[i] > 0) {
return i;
}
}

// 到这,说明没有缺失 [1, n) 的数
if (nums[0] > 0) {
return n;
}

// 到这一步,说明数组是 1 ~ n 的连续自然数
return n + 1;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

42.接雨水(双指针/栈/动态编程)

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

题解

暴力法

对于每个下标,找出其能接到雨水的最大高度(左右边界的较小值 - 当前柱子高度)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int trap(int[] height) {
int n = height.length;
int ans = 0;
for (int i = 1; i < n - 1; i++) {
int leftBorder, rightBorder;
leftBorder = rightBorder = height[i];
for (int j = i - 1; j >= 0; j--) {
leftBorder = Math.max(leftBorder, height[j]);
}
for (int j = i + 1; j < n; j++) {
rightBorder = Math.max(rightBorder, height[j]);
}
ans += Math.min(leftBorder, rightBorder) - height[i];
}
return ans;
}

算法分析:

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)

动态编程

在暴力方法中,仅仅为了找到最大值每次都要向左和向右扫描一次,其实我们可以提前存储这个值,实现这个想法,就可以通过动态编程解决

  • 从左向右扫描数组,记录该下标左边界最大值

    leftBorder[i] = Math.max(height[i], leftBorder[i - 1])

  • 从右向左扫描数组,记录该下标右边界最大值

    rightBorder[i] = Math.max(height[i], rightBorder[i + 1])

  • 扫描数组height并更新答案

    ans += Math.min(leftBorder[i], rightBorder[i]) - height[i]

其实,可以把求leftBorder[i]的步骤和更新答案的步骤合并,减少一次循环

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int ans = 0;
int[] leftBorder = new int[n];
int[] rightBorder = new int[n];
leftBorder[0] = height[0];
rightBorder[n - 1] = height[n - 1];
for (int i = n - 2; i > 0; i--) {
rightBorder[i] = Math.max(height[i], rightBorder[i + 1]);
}
for (int i = 1; i < n - 1; i++) {
leftBorder[i] = Math.max(height[i], leftBorder[i - 1]);
ans += Math.min(leftBorder[i], rightBorder[i]) - height[i];
}
return ans;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

使用栈

我们可以不用像动态编程的算法那样存储最大高度,而是用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。

我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块,我们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶,我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定,因此我们可以弹出栈顶元素并且累加答案到 ans

步骤:

  • 使用栈来存储条形块的索引下标。
  • 遍历数组:
    • 当栈非空且height[index] > height[stack.peek()]
      • 意味着栈中元素可以被弹出。弹出栈顶元素 top
      • 计算当前元素和栈顶元素的距离,准备进行填充操作
        distance = index - stack.peek() - 1
      • 找出界定高度
        bounded_height = Math.min(height[index], height[stack.peek()]) - height[top]
      • 往答案中累加积水量ans += distance * bounded_height
    • 将当前索引下标入栈
    • index移动到下个位置

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int ans = 0;
int index = 0;
Stack<Integer> stack = new Stack<>();
while (index < n) {
while (!stack.empty() && height[index] > height[stack.peek()]) {
int top = stack.peek();
stack.pop();
if (stack.empty()) {
break;
}
int distance = index - stack.peek() - 1;
int bounded_height = Math.min(height[index], height[stack.peek()]) - height[top];
ans += distance * bounded_height;
}
stack.push(index++);
}
return ans;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

双指针

和动态编程算法相比,我们不从左和从右分开计算,我们想办法一次完成遍历

从动态编程方法的示意图中我们注意到,积水高度将由 leftBorderrightBorder 中的较小者决定

所以我们可以认为如果一端有更高的条形块(例如右端),积水的高度依赖于当前方向的高度(从左到右)。当我们发现另一侧(右侧)的条形块高度不是最高的,我们则开始从相反的方向遍历(从右到左)

我们必须在遍历时维护 leftBorderrightBorder,但是我们现在可以使用两个指针交替进行,实现 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
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int ans = 0;
int leftBorder = 0, rightBorder = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftBorder) {
leftBorder = height[left];
} else {
ans += (leftBorder - height[left]);
}
left++;
}
else {
if (height[right] >= rightBorder) {
rightBorder = height[right];
} else {
ans += (rightBorder - height[right]);
}
right--;
}
}
return ans;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

43.字符串相乘

题目

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

说明:

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9。
  3. num1 和 num2 均不以零开头,除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。

题解

利用APIjava.math.BigInteger

1
2
3
4
5
public String multiply(String num1, String num2) {
BigInteger n1 = new BigInteger(num1);
BigInteger n2 = new BigInteger(num2);
return n1.multiply(n2).toString();
}

规规矩矩操作字符串

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
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int len1 = num1.length();
int len2 = num2.length();
String result = "";
for (int i = len2 - 1; i >= 0; i--) {
StringBuilder tmpStr = new StringBuilder();
// 先补 0
for (int j = 0; j < len2 - 1 - i; j++) {
tmpStr.append(0);
}
int carry = 0;
int num = num2.charAt(i) - '0';
for (int j = len1 - 1; j >= 0; j--) {
int cur = num * (num1.charAt(j) - '0') + carry;
carry = 0;
if (cur > 9) {
carry = cur / 10;
cur %= 10;
}
tmpStr.append(cur);
}
if (carry != 0) {
tmpStr.append(carry);
}
result = combineTwoStr(result, tmpStr.reverse().toString());
}
return result;
}

private String combineTwoStr(String s1, String s2) {
StringBuilder tmpStr = new StringBuilder();
int len1 = s1.length();
int len2 = s2.length();
int carry = 0;
for (int i = len1 - 1, j = len2 - 1; i >= 0 || j >= 0; i--, j--) {
int n1 = i >= 0 ? s1.charAt(i) - '0' : 0;
int n2 = j >= 0 ? s2.charAt(j) - '0' : 0;
int num = n1 + n2 + carry;
carry = 0;
if (num > 9) {
carry = num / 10;
num %= 10;
}
tmpStr.append(num);
}
if (carry != 0) {
tmpStr.append(carry);
}
return tmpStr.reverse().toString();
}

算法分析:

  • 时间复杂度:O(n * m)
  • 空间复杂度:O(n + m)

优化版

这里感谢作者 breezean 提供了优化版本

链接:https://leetcode-cn.com/problems/multiply-strings/solution/you-hua-ban-shu-shi-da-bai-994-by-breezean/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int[] res = new int[num1.length() + num2.length()];
for (int i = num1.length() - 1; i >= 0; i--) {
int n1 = num1.charAt(i) - '0';
for (int j = num2.length() - 1; j >= 0; j--) {
int n2 = num2.charAt(j) - '0';
int sum = (res[i + j + 1] + n1 * n2);
res[i + j + 1] = sum % 10;
res[i + j] += sum / 10;
}
}

StringBuilder result = new StringBuilder();
for (int i = 0; i < res.length; i++) {
if (i == 0 && res[i] == 0) continue;
result.append(res[i]);
}
return result.toString();
}
}

44.通配符匹配(动态规划/双指针+贪心算法/回溯法)

题目

给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?''*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。

示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:

输入:
s = “aa”
p = “*”
输出: true
解释: ‘*’ 可以匹配任意字符串。

示例 3:

输入:
s = “cb”
p = “?a”
输出: false
解释: ‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

示例 4:

输入:
s = “adceb”
p = “ab”
输出: true
解释: 第一个 ‘‘ 可以匹配空字符串, 第二个 ‘‘ 可以匹配字符串 “dce”.

示例 5:

输入:
s = “acdcb”
p = “a*c?b”
输出: false

题解

动态规划

这题用动态规划比较容易,因为涉及到了之前的状态

构造一个(n+1) * (m+1)的类型为boolean的表dp[][]

n代表文本串s的长度,m代表模式串p的长度
dp[i][j]代表这一位置对应的s[i]p[j]是否匹配

首先初始化数组dp[][]

  • dp[0][0] = true
  • 第一行:dp[0][i] = dp[0][i - 1] && p.charAt(i - 1) == '*'
    • 这是代表文本串为空的情况,当然索引从1开始
  • 第一列:默认为false
    • 因为第一列代表模式串为空,索引从1开始

接着分别从索引1开始遍历,is的索引,jy的索引

  1. 如果p[j - 1] == '?' 或者 s[i - 1] == p[j - 1]
    • 那么dp[i][j] = dp[i - 1][j - 1]
  2. 如果p[j - 1] == '*'
    • 那么dp[i][j] = dp[i][j - 1] || dp[i - 1][j]

解释一下第2种情况

dp[i][j] = dp[i][j - 1],代表'*'匹配的是空字符
dp[i][j] = dp[i - 1][j],代表'*'匹配的是非空字符

注:java 中boolean数组没有赋值的默认为false,所以其他地方不用管

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];

dp[0][0] = true;
for (int i = 1; i <= m; i++) {
dp[0][i] = dp[0][i - 1] && p.charAt(i - 1) == '*';
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
}
return dp[n][m];
}

算法分析:

  • 时间复杂度:O(n * m)
  • 空间复杂度:O(n * m)

双指针+贪心算法

为字符串s设置两个指针:iiStar
为字符串p设置两个指针:jjStar

iStarjStar分别表示在相应字符串中星号'*'当前匹配的位置
所以初始值要赋为-1,表示还没匹配

首先,遍历文本串s

  1. p[j - 1] == '?' 或者 s[i - 1] == p[j - 1]
    • 同时递增指针ij
  2. p[j - 1] == '*'
    • 指针iStarjStar就指向当前ij的位置
    • 并递增j指针去模式串p匹配下一个位置
  3. iStar >= 0说明已经开始进行'*'的匹配
    • 那么递增iStar尝试匹配文本串s的下一个位置
    • 并另i = iStar
    • 同时把j移动到jStar + 1的位置
  4. 若上述三种情况都不满足,说明匹配中断
    • return false
  5. 循环结束,若j没有指向p的末尾
    • 如果剩下的子串不全是'*',则return false

代码如下

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
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
int i = 0, j = 0;
int iStar = -1, jStar = -1;
while (i < n) {
if (j < m && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
i++;
j++;
} else if (j < m && p.charAt(j) == '*') {
iStar = i;
jStar = j++;
} else if (iStar >= 0) {
i = ++iStar;
j = jStar + 1;
} else {
return false;
}
}
//去除多余星号
while (j < m && p.charAt(j) == '*') {
j++;
}
return j == m;
}

算法分析:

  • 时间复杂度:O(n + m)
  • 空间复杂度:O(1)

回溯法

回溯法容易超时,不过代码易读,不多解释了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isMatch(String s, String p) {
if (p.equals("*")) {
return true;
}
// 如果 p 为空
if (p.isEmpty()) {
return s.isEmpty();
} else if (s.isEmpty()) { // 如果 s 为空
return p.charAt(0) == '*' && isMatch(s, p.substring(1));
} else { // 如果 p 和 s 都不为空
if (p.charAt(0) == '?' || s.charAt(0) == p.charAt(0)) {
return isMatch(s.substring(1), p.substring(1));
} else if (p.charAt(0) == '*') {
return isMatch(s, p.substring(1)) // '*' 匹配的是空字符
|| isMatch(s.substring(1), p); // '*' 匹配的是非空字符
}
}
return false;
}

45.跳跃游戏 II(贪心算法)

题目

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

题解

贪心算法

首先需要定义几个变量

  • lastBoundary:上一部达到的边界,初始值为起点 0
  • boundary:目前能达到的最远边界,初始值为起点 0

遍历步数数组nums[]

  • 每次都尝试更新能达到的最远边界
    • boundary = Math.max(boundary, nums[i] + i)
  • 如果遍历到上一步能达到的边界处
    • 更新lastBoundarylastBoundary = boundary
    • step++

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int jump(int[] nums) {
// 上一步达到的边界
int lastBoundary = 0;
// 目前能达到的最远边界
int boundary = 0;
// 跳的步数
int step = 0;
for(int i = 0; i < nums.length - 1; i++){
// 尝试更新能达到的最远边界
boundary = Math.max(boundary, nums[i] + i);
// 遇到之前达到的边界就更新达到的边界和步数
if(i == lastBoundary){
lastBoundary = boundary;
step++;
}
}
return step;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

附一下官方非贪心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int jump(int[] nums) {
int position = nums.length - 1; //要找的位置
int steps = 0;
while (position != 0) { //是否到了第 0 个位置
for (int i = 0; i < position; i++) {
if (nums[i] >= position - i) {
position = i; //更新要找的位置
steps++;
break;
}
}
}
return steps;
}

算法分析:

  • 时间复杂度:最坏情况下:O(n2)
  • 空间复杂度:O(1)