贪心算法 | 763.划分字母区间
·题目描述
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec" 输出：[10]
·解题思路
很质朴的想法是，遍历一圈字符串s， 把每个字母出现的起始位置用数组记录下来。再套用之前leetcode 452 用最少数量的箭引爆气球 和 leetcode 435 无重复区间的 思路， 将数组进行规划；
规划分为三步：1.最开始的位置进行排序；2.当后一个数组的开始位置小于前一个数组的结束位置的时候，说明两个数组有重叠，更新数组区间；3.当后一个数组的开始位置大于前一个数组的结束位置的时候，说明两个数组没有重叠区间，需要计算前一个数组的字符串长度
·解题细节：
1.每一个字母都可能出现，因此创建26*2的二维数组，计算每一个出现的字母的开始和结束位置。同时，如何判断该数字是开始坐标还是结束坐标------创建flag数组来标记，若是flag = 0 ，表示之前没有出现过，该坐标为起始坐标，反之则为结束坐标。结束坐标需要不断更新；
int[][] num = new int[26][2];
int[] flag = new int[26];
for(int i = 0; i < s.length(); i++){
int temp = s.charAt(i) - 'a';
if(flag[temp] == 0){num[temp][0] = i;flag[temp] = 1;}
else{ num[temp][1] = Math.max(num[temp][1], i);}
}2.对记录的字母坐标按照第一个元素进行排序
Arrays.sort(num, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
#打印结果
for(int i = 0; i < num.length; i++){
System.out.println(num[i][0] + " " + num[i][1]);
}3.对坐标数组进行处理，遍历num数组，利用栈来辅助更新区间。当当前数组的开始位置小于栈顶数组的结束位置的时候，说明两个数组有重叠，更新数组区间；反之说明两个数组没有重叠区间，需要计算前一个数组的字符串长度
Stack<int[]> stack = new Stack<int[]>();
for(int i = 0;i < num.length;i++){
#当栈为空的时候，先压入
if(stack.isEmpty()) stack.push(num[i]);
else{
int[] point = stack.peek();
if(num[i][0] < point[1]){
int newend = Math.max(point[1], num[i][1]);
int[] newpoint = new int[] {point[0],newend};
stack.pop();
stack.push(newpoint);
}
else{
int len = stack.peek()[1] - stack.peek()[0] + 1;
res.add(len);
stack.pop();
stack.push(num[i]);
}
}
}4.有可能最后一个子字符串不能满足for循环的收割条件，也就是说栈不为空，这是还需要处理
while(!stack.isEmpty()){
int[] point = stack.pop();
if(point[1] == 0) {res.add(1);count += 1;}
else{
int len = point[1] - point[0] + 1;
res.add(len);
}
}5.处理空数组：
由于给出的字符不一定包含26个字母，也就是说num中有很多空数组参与了排序，这时候只需要在遍历的时候，当数组两个元素都是0的时候，continue即可
if(num[i][0] == 0 && num[i][1] == 0){continue;}6.处理单个元素
字符串中可能存在单个元素，分为两种情况：头单个【0，0】和其他【x(x!= 0) , 0】
处理头单个的时候，只需要增加一个count技术，当所有子串的长度小于给定字符串的长度时，说明有头单个元素漏加，只需要在列表结构头部增加 1 ，即可
处理其他单个元素的时候，只需要在遍历num时，当数组第一个元素不为0，而第二元素为0 的时候，将第二个元素变为第一个元素相同值即可
if(num[i][0] == 0 && num[i][1] == 0){continue;}
if(num[i][0] != 0 && num[i][1] == 0){num[i][1] = num[i][0];}·java代码
import java.util.*;
class Solution {
public List<Integer> partitionLabels(String s) {
int[][] num = new int[26][2];
int[] flag = new int[26];
int count = 0;
for(int i = 0; i < s.length(); i++){
int temp = s.charAt(i) - 'a';
if(flag[temp] == 0){num[temp][0] = i;flag[temp] = 1;}
else{ num[temp][1] = Math.max(num[temp][1], i);}
}
Arrays.sort(num, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
for(int i = 0; i < num.length; i++){
System.out.println(num[i][0] + " " + num[i][1]);
}
List<Integer> res = new ArrayList<Integer>();
Stack<int[]> stack = new Stack<int[]>();
for(int i = 0;i < num.length;i++){
if(num[i][0] == 0 && num[i][1] == 0){continue;}
if(num[i][0] != 0 && num[i][1] == 0){num[i][1] = num[i][0];}
if(stack.isEmpty()) stack.push(num[i]);
else{
int[] point = stack.peek();
if(num[i][0] < point[1]){
int newend = Math.max(point[1], num[i][1]);
int[] newpoint = new int[] {point[0],newend};
stack.pop();
stack.push(newpoint);
}
else{
int len = stack.peek()[1] - stack.peek()[0] + 1;
res.add(len);
count += len;
stack.pop();
stack.push(num[i]);
}
}
}
while(!stack.isEmpty()){
int[] point = stack.pop();
if(point[1] == 0) {res.add(1);count += 1;}
else{
int len = point[1] - point[0] + 1;
res.add(len);
count += len;
}
}
if(count < s.length()) res.add(0,1);
return res;
}
}
public class Main {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.partitionLabels("vhaagbqkaq"));
}
}原文地址：https://blog.csdn.net/weixin_57865902/article/details/140674164
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！