日拱两卒（三）

80#

划分字母区间。

把一个字符串分成尽可能多的区间，同一种字母必须出现在同一个区间。

预处理出来每个字母的最左和最右。

从前往后扫，维护必须延伸到的最右边。

1
class Solution:
2
    def partitionLabels(self, s: str) -> List[int]:
3
        n = len(s)
4
        seg = [[-1] * 2 for _ in range(26)]
5

6
        for i, ch in enumerate(s):
7
            idx = ord(ch) - ord('a')
8
            if seg[idx][0] == -1:
9
                seg[idx][0] = i
10
            seg[idx][1] = i
11

12
        ans = []
13
        l = 0
14
        r = seg[ord(s[0]) - ord('a')][1]
15
        i = l
16
        while True:
17
            if r >= n - 1:
18
                ans.append(n - 1 - l + 1)
19
                break
20
            if i > r:
21
                ans.append(r - l + 1)
22
                l = i
23
                r = seg[ord(s[i]) - ord('a')][1]
24

25
            r = max(r, seg[ord(s[i]) - ord('a')][1])
26
            i += 1
27

28
        return ans

79#

跳跃游戏II。

问在nums上从0跳到n - 1的最小次数。每一次可以跳0到nums[i]之间任意远。

记忆化做法在Leetcode上没被卡。

但本质上和80 划分字母区间是同一道题。

维护当前区间的最远延申位置，每当指针越过这个边界，就完成一次切割或者跳跃。

1
class Solution:
2
    def jump(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        if n == 1:
5
            return 0
6

7
        right = [i + nums[i] for i in range(n)]
8

9
        ans = 0
10
        r = right[0]
11
        max_r = r
12
        i = 0
13

14
        while True:
15
            if r >= n - 1:
16
                ans += 1
17
                break
18

19
            if i > r:
20
                ans += 1
21
                r = max_r
22
                continue
23

24
            max_r = max(max_r, right[i])
25
            i += 1
26

27
        return ans