LeetCode 解题思路 40（跳跃游戏 II、划分字母区间）

解题思路：

1. 初始化变量：

• jump：记录跳跃次数。
• maxReach：记录总的最远距离。
• currentReach：记录当前的最远距离。

2. 遍历数组：

• 更新总的最远距离。
• 如果当前的遍历位置 i == 当前的最远距离，进行一次跳跃，并更新当前的最远距离。
• 如果当前的最远距离超过数组长度，break。

3. 返回结果： 返回 jump。

Java代码：

public class Solution {
    public int jump(int[] nums) {
        int jumps = 0;
        int maxReach = 0;
        int currentReach = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if (i == currentReach) {
                jumps++;
                currentReach = maxReach;
                if (currentReach >= nums.length - 1) break;
            }
        }

        return jumps;
    }
}

复杂度分析：

• 时间复杂度： O(n)，其中 n 是数组的长度。我们只需遍历数组一次。
• 空间复杂度： O(1)，只使用了常数级别的额外空间。
  

解题思路：

1. 初始化变量：

• result：记录结果。
• last：记录当前字符最后一次出现的索引位置。
• start：当前段的开始位置。
• end：当前段的结束位置。

2. 遍历数组：

• 更新当前段的结束位置为当前字符最后一次出现的索引位置。
• 如果当前的遍历位置 i == 当前段的结束位置，向结果集添加字符串的片段长度 end - start + 1，并更新当前段的开始位置。

3. 返回结果： 返回 result。

Java代码：

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new List<>();
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++)
            last[s.charAt(i) - 'a'] = i;
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }

        return result;
    }
}

复杂度分析：

• 时间复杂度： O(n)，其中 n 是字符串的长度，需要两次线性遍历字符串。
• 空间复杂度： O(1)。使用了一个固定大小的数组。