划分字母区间

[编程题]划分字母区间

热度指数：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 \le n \le 10^5 \$ ，字符串中仅出现小写字母。

示例1

输入

"anfjaklii"

输出

[5,1,1,2]

算法知识视频讲解

Java

牛客683289936号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> splitString (String s) {
        // write code here
        Map<Character,Integer> map = new HashMap<>();
        ArrayList<Integer> res = new ArrayList<>();
        int end = -1;
        int start = 0;
        
        //存储每个字母最后的位置
        for(int i = 0 ;i<s.length();i++){
            map.put(s.charAt(i),i);
        }
        
        
        for(int i = 0;i<s.length();i++){
            end = Math.max(end,map.get(s.charAt(i)));
            if(end == i ){
                res.add(end - start + 1);
                start = i+1;
            }
        }
                           
        return res;
                
       
        
    }
}

发表于 2022-03-26 11:30:57 回复(0)