欢迎大家来到IT世界,在知识的湖畔探索吧!
贪心算法练习记录：
leetcode 763 https://leetcode-cn.com/problems/partition-labels
小写字母组成的字符串，将其分为尽可能多的片段，满足的要求是：每个字母最多出现在一个片段中，最多能分成几个片段呢？输出形式是片段长度的整数数组。
如：string = 'abcbadefghdijk',分成的片段为：‘abcba'、‘defghd'、'ijk' ;输出为：result = [5,6,3]欢迎大家来到IT世界,在知识的湖畔探索吧!
思路：
因为给的字符串长度有限，所以可以用暴力解法，循环遍历字符数组，用当前的字母去逐个比对得出每个片段，时间复杂度O(n^2)。贪心的思路：循环遍历字符串数组，由于同一字母最多出现在一个片段中，其第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段，所以一下子可以获得该字母在字符串中最后的位置（前提条件是已经遍历获得每个字母以及对应的最后位置），用一个变量current_last表示当前字母的最后位置，当前字母的最后位置大于current_last则更新否则不变，然后判断当前字母在字符串数组中的下标号等于其最后位置则说明已经可以形成一个片段，接着继续遍历下一个字母，直到遍历结束。
代码实现：
划分字母区间C语言代码实现
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://itzsg.com/34968.html
