【LeetCode每日一题】[中等]763. 划分字母区间

763. 划分字母区间

题目来源 算法思想：字符串, 贪心 题目：

java代码

思路：遍历字符串，依次寻找最短不含其它字母的子字符串，将其长度存起来

首先，统计每个字母第一次出现的位置(存放start)以及最后出现的位置(存放end)；遍历字符串S,寻找最短不含其它字母的子字符串,该子字符串中每个字母的起始位置均包括在子字符串中;(贪心的找取最短的,符合条件的字符串)记录以上子字符串的长度; class Solution { public List<Integer> partitionLabels(String S) { char[] ch = S.toCharArray(); int[] start = new int[26];//第一次出现位置 int[] end = new int[26];//最后一次出现位置 for (int i = 0; i < end.length; i++) {//将其设置成-1.表示没有该字母 start[i] = -1; end[i] = -1; } List<Integer> res = new ArrayList<Integer>();//存放字符串长度 //统计每个字母第一次出现以及最后出现位置 for (int i = 0; i < ch.length; i++) { int index = ch[i] - 'a'; if (start[index] == -1) { start[index] = i;//统计字母第一次出现位置 } end[index] = i;//字母最后出现的位置 } //初始化子字符串起始位置a,b int a = start[ch[0] - 'a'];//记录一个字母的起始位置,开始位置 int b = end[ch[0] - 'a'];//终止位置 for (int i = 1; i < ch.length; i++) {//遍历字符串 int index = ch[i] - 'a'; //如果新字母的起始位置,大于b,表示<a,b>是符合条件的子字符串,将其长度存入; //将新字母的初始位置成a,b的值,进行下一轮迭代 if (start[index] > b) { res.add(b - a + 1); a = start[index]; b = end[index]; } if (end[index] > b) {//如果新字母的终止位置大于b,则更新子字符串的终止位置 b = end[index]; } } res.add(b - a + 1);//将最后的子字符串加入res return res; } }

简化: 按照字符串顺序进行遍历,可以不用存字母的初始下标,因为就是i 简化后 代码如下：

class Solution { public List<Integer> partitionLabels(String S) { char[] ch = S.toCharArray(); int[] end = new int[26];//字母最后出现的位置 List<Integer> res = new ArrayList<Integer>(); for (int i = 0; i < ch.length; i++) {//统计每一个字母最后出现的位置 int index = ch[i] - 'a'; end[index] = i; } //设定a,b初始是第一个字母的起始和终止位置; int a = 0; int b = end[ch[0] - 'a']; for (int i = 1; i < ch.length; i++) { int index = ch[i] - 'a'; if (i > b) {//如果当前的字母起始比子字符串终止b大,则说明开始了新的子字符串,更新 res.add(b - a + 1);//存储长度 a = i;//更新a b = end[index];//更新b; } if (end[index] > b) {//当前字母在子字符串范围(a,b)内,其终止长度比b大,则要将b更新为最大的b,使得同一个字母在一个子字符串之内 b = end[index]; } } res.add(b - a + 1);//加入最后一个子字符串 return res;//返回 } }