学校校园网站建设实践选题背景,宁波电子商务公司,电子政务与网站建设意义,wordpress异步上传图片题目链接#xff1a;763. 划分字母区间 - 力扣#xff08;LeetCode#xff09;
前情提要#xff1a;
因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。
贪心方法#xff1a;局部最优推出全局最优。
如果一个题你觉得可以用局部最优推出全局最优#xf…题目链接763. 划分字母区间 - 力扣LeetCode
前情提要
因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。
贪心方法局部最优推出全局最优。
如果一个题你觉得可以用局部最优推出全局最优并且没有反例来反驳的话就可以用贪心来试试。
题目思路
其实这个题入手很快本题要求将字符划尽可能多的分为片段。其实贪心就贪在我们要找到尽可能长度小的片段。
局部最优根据范围来获得最小的片段。
全局最优获得尽可能多的片段。
那么我们怎么找呢题目要求不同片段内同一字母只能出现一次。
其实这题跟力扣55-跳跃游戏有点像。 题目链接55. 跳跃游戏 - 力扣LeetCode 题解链接 力扣55-跳跃游戏java详细题解-CSDN博客 如有需要请自取。 我们可以将每一个字母所出现的最大下标位置给求出然后遍历该字符串并在原来的最大范围内并扩大该范围只有该范围不能再扩大了即遍历到该片段的最大范围那么这时求的就是最小的字符片段。
举个例子。 那么肯定就有人想我们不是要求最小的片段吗那这个片段的范围不是越小越好吗怎么要求最大范围。
如果不这样虽然你的片段范围是小了但是你的这个片段并不符合题意题目要求不同片段内同一字母只能出现一次。
你只有将该片段内的最大的字母下标位置确定下来你才能确定该片段内所有的字母不会出现在其他的片段内。
核心思路就是要维护一个最大的边界范围确定他的终止位置。
最终代码
class Solution {public ListInteger partitionLabels(String s) {//该题我们要寻找字符串尽可能多的片段怎么求呢//只要知道我们当前字母的最大范围然后在我们的这个范围内再不断的扩大我们这个范围只到我们不能再扩大了,那么我们就得到了这样一个最小的字符片段。//局部最优根据范围来获得最小的片段//全局最优获得尽可能多的片段int [] hashArr new int [27];ListInteger result new ArrayList();//利用哈希思想让每一个数组下标跟字母做映射给每一个字母得出最大的位置下标for(int i 0;i s.length();i ){hashArr[s.charAt(i) - a] i;}//在这里我们用双指针来获取每一个片段的长度//left记录起始位置 right记录终止位置int left 0,right 0;for(int i 0;i s.length();i ){//首先 我们移动终止位置知道终止位置移动到我们这个片段的最大下标位置就停止收集结果//并让下一段起始位置移动到上一段终止位置的下一个right Math.max(hashArr[s.charAt(i) - a],right);if(right i){result.add(right - left 1);left i 1;}}return result;}
}这一篇博客就到这了如果你有什么疑问和想法可以打在评论区或者私信我。
我很乐意为你解答。那么我们下篇再见
