2021-12-24:划分字母区间。 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。 力扣763。某大厂面试题。

答案2021-12-24:

时间紧,具体见代码。

代码用golang编写。代码如下:

package main

import "fmt"

func main() {
    S := "ababcbacadefegdehijhklij"
    ret := partitionLabels(S)
    fmt.Println(ret)
}

func partitionLabels(S string) []int {
    str := []byte(S)
    far := make([]int, 26)
    for i := 0; i < len(str); i++ {
        far[str[i]-'a'] = i
    }
    ans := make([]int, 0)
    left := 0
    right := far[str[0]-'a']
    for i := 1; i < len(str); i++ {
        if i > right {
            ans = append(ans, right-left+1)
            left = i
        }
        if right < far[str[i]-'a'] {
            right = far[str[i]-'a']
        }
    }
    ans = append(ans, right-left+1)
    return ans
}

执行结果如下: 图片


左神java代码