栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode.763 Partition Labels(标签分类)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode.763 Partition Labels(标签分类)

1.题目

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

2.样例

Example 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.
3.题解        

- 根据题目意思,我们需要对一个仅包含小写字母的字符串进行分割,分割的原则:尽量将相同的字符分到一组,并且保证分组数量尽可能多。最后输出最多分组数量的每段的长度。

- 思路:典型的贪心+数组记录下标解法,我们首先遍历数组各个字符最后出现的index,然后利用贪心每次对需要判断的字符判断其最远出现的下标是否大于当前分组里面最大的下标:

        - 1.如果当前字符下标index大于前面分组出现最大的下标,说明该字符不属于前面一组,可以进行切分。

        - 2.如果当前字符的下标小于前面分组出现的最大的下标,说明该字符属于前面同一组。

        - 3.如果当前字符的下标小于前面分组,但是其最后存在的下标大于前面分组的最大下表,则说明该组长度可以继续延长。

        - 4.ps:这里要尤其注意只出现一个字符,和处理到最后一个字符的处理。

- 代码:

class Solution {
    public List partitionLabels(String s) {
       // 思路:利用贪心进行字符串切割,每次判断当前下标元素可到达最远距离,如果当前可达到最远距离,则更新最大的,否则如果当前下标index大于之前可到达的最远的maxIndex,则认为是新的一段开始
        if (s == null || s.length() == 0) {
            return new ArrayList<>();
        }

        
        int[] lastIndex = new int[256];
        char[] chs = s.toCharArray();
        for (int i = 0; i < chs.length; i++) {
            lastIndex[chs[i]] = i;
        }

        List splitLengthList = new ArrayList<>();
        int curMaxIndex = lastIndex[chs[0]];
        int startIndex=0;
        for (int i = 0; i < chs.length; i++) {
            char curChar = chs[i];
            int curCharLastIndex = lastIndex[curChar];
            if (curCharLastIndex < curMaxIndex) {
                continue;
            }

            // 判断是否为新的开始
            if (i > curMaxIndex) {
                curMaxIndex = curCharLastIndex;
                splitLengthList.add(i-startIndex);
                startIndex=i;
            } else {
                curMaxIndex = Math.max(curMaxIndex, curCharLastIndex);
            }
            
            // 最后一个字符
            if (i == chs.length - 1) {
                splitLengthList.add(i-startIndex+1);
            }
        }
        return splitLengthList;
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/955991.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号