首页 > 试题广场 >

划分字母区间

[编程题]划分字母区间
  • 热度指数:524 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个由小写字母组成的字符串 s ,请你把这个字符串尽可能多地划分,相同的字母只出现在一个的区间。
例如 "anfjaklii" ,可以把 "anfja" 和 "k","l","ii" 划成四个区间, 'a' 'n' 'f' 'j' 只出现在第一个区间 ,'k' 'l' 'i' 分别出现在第二、三、四个区间。
即输出 5 1 1 2。

数据范围:字符串长度满足 ,字符串中仅出现小写字母。
示例1

输入

"anfjaklii"

输出

[5,1,1,2]
package main

import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return int整型一维数组
*/
func splitString( s string ) []int {
    ends:=map[byte]int{}
    for i,ch:=range []byte(s){
        ends[ch]=i
    }
    ans:=[]int{}
    var l,r int
    for i:=0;i<len(s);i++{
        r=max(r,ends[s[i]])
        if i==r{
            ans=append(ans,r-l+1)
            l=i+1
        }
    }
    return ans
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

发表于 2023-03-19 21:41:34 回复(0)