首页 > 其他分享 >763. 划分字母区间

763. 划分字母区间

时间:2024-09-03 15:23:12浏览次数:13  
标签:子串 片段 last int 763 字母 位置 划分

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1:

输入:s = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。 

示例 2:

输入:s = "eccbbbbdec"
输出:[10]

题解

  1. 由于同一个字母只能出现在同一个片段,显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串,得到每个字母最后一次出现的下标位置。
  2. 代码中首先用子串的首字母,查出其最后一次出现位置,作为临时子串(还不是最终子串,因为当前子串内的其他字母的最后一次出现位置,可能还在该子串后面,需要堆子串内部的其他字符再来一遍循环,找出某字母最后一次出现位置最大的位置处),经过内部循环后,此时的子串为最终临时子串,求出其长度,并更新下一个最终子串的起始位置。
  3. 使用贪心的思想寻找每个片段可能的最小结束下标,因此可以保证每个片段的长度一定是符合要求的最短长度,如果取更短的片段,则一定会出现同一个字母出现在多个片段中的情况。由于每次取的片段都是符合要求的最短的片段,因此得到的片段数也是最多的。

代码

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int count;
        vector<int> result;
        string pre;
        int len=s.length();
        int i=0,j=0,tmp;
        i=s.find_last_of(s[j]);//临时子串最终位置
        tmp=1;
        while(i<len){

            while(tmp<i){
                if(s.find_last_of(s[tmp])>i)//如果大于临时子串的最后位置则更新子串最终位置
                    i=s.find_last_of(s[tmp]);
                tmp++;
            }
            pre=s.substr(j,i+1-j);
            i++;
            //j=s.find_first_not_of(pre,i);
            count=pre.length();
            result.push_back(count);
            if(i==len)
                return result;
            j=i;
            i=s.find_last_of(s[i]);
            tmp=j+1;
        }
        return result;
    }
};

官方题解代码

和上面的解题思路大致一样,巧妙的用了一个数组,存储每个字母最后一次出现的最大位置,在一次循环中,寻找子串(找到某位置等于子串内所有字母最后一次出现的最大值时)。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int length = s.size();
        for (int i = 0; i < length; i++) {
            last[s[i] - 'a'] = i;
        }
        vector<int> partition;
        int start = 0, end = 0;
        for (int i = 0; i < length; i++) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                partition.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return partition;
    }
};

标签:子串,片段,last,int,763,字母,位置,划分
From: https://blog.csdn.net/qq_33811080/article/details/141861972

相关文章

  • 代码随想录算法训练营,9月2日 | 242.有效的字母异位词,349. 两个数组的交集,202. 快乐数,1
    哈希表理论基础1.根据关键码的值而直接进行访问的数据结构(直白来讲其实数组就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素);2.哈希表都是用来快速判断一个元素是否出现集合里;3.哈希函数:把值对应到哈希表的函数;哈希碰撞:映射到哈希表同一个索引......
  • 2024.9.2 Python,用栈写每日温度,等差数列划分,子串所有可能性,等差数列划分,深度优先搜索
    1.每日温度给定一个整数数组temperatures,表示每天的温度,返回一个数组answer,其中answer[i]是指对于第i天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用0来代替。示例1:输入:temperatures=[73,74,75,71,69,72,76,73]输出:[1,1,4,2,......
  • 18046 字母分类统计
    ###思路1.读取输入的一行字符。2.初始化计数器:字母、数字、空格和其它字符的个数。3.遍历每个字符,根据其类型更新相应的计数器。4.输出计数结果,格式为:字母、数字、空格和其它字符的个数,中间以空格分隔。###伪代码1.读取输入的一行字符。2.初始化计数器:letters......
  • 哈萨克语学习心得(一)——哈萨克语西里尔字母记忆法
    最近开始学习基于西里尔文字的哈萨克语,慢慢梳理一下自己的学习心得。首先是字母的学习,虽然之前没有接触过西里尔文字,但是感觉自己在记忆字母这方面没什么太大的障碍,可能是因为西里尔字母来源于希腊字母吧,而之前数学和物理课上学到了很多希腊字母的发音,跟西里尔字母有很强的对照效......
  • 763. 划分字母区间(leetcode)
    https://leetcode.cn/problems/partition-labels/description/听说这题是字节广告一面的题有两种做法,但是思路大致相同,主要思路是先求出所有字符的出现的最远距离,然后不断往后遍历,更新当前片段的最远距离若是第一种做法,就是放在另一个循环中,不断更新最远距离,且维护这个en......
  • leecode_049_字母异位词分组解析
    题目给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=["eat","tea","tan","ate","nat","bat"]输出:[["bat"],["nat","tan"],[&......
  • 【Unity】经典四叉树的实现以及和无空间划分加速下的效率对比分析
    背景假如场景中存在大量的对象,需要快速找到某个范围内的所有对象,如果通过传统的方式,就需要对所有的物体遍历,依次判断是否在范围中,这样非常耗时。所以通过空间划分的方法将其加速,本文中采用四叉树的方式,从实现思想和代码层面对效率进行分析。思想在空间划分算法中首先需要对所有......
  • 【Hot100】LeetCode—17. 电话号码的字母组合
    目录1-思路String数组(哈希表)+回溯2-实现⭐17.电话号码的字母组合——题解思路3-ACM实现题目连接:17.电话号码的字母组合1-思路String数组(哈希表)+回溯思路通过String数组实现哈希表,存储0-9的哈希表映射回溯三部曲①参数及返回值numToStr:Stri......
  • 八行代码解决字母异位词分组(49)
    leetcode题目链接 这道题利用hash表特性可以很轻松的解决。首先我们只需要给所有的字母异位词排序,那样的所有的字母异位词就会变成同一个词,拿这个词当键,插入hash表,而所有的字母异位词当值,这样打印出hash表所有的词就是最后的结果。代码如下classSolution{ public: v......
  • 用Python给英语单词批量划分音节
    一、问题的缘起最近,有网友在我的视频下面留言,问我可否把英语单词进行音节的划分?我以前也有同样的想法,但是始终没有得到解决。但是,我想使用python,学习英语的人都很多,说不定有人已经编写了类似的模块供我们调用呢?问题截图于是,我就抱着试试看的心情,在网上搜了一下,果然,某搜索......