贪心算法习题其三【力扣】【算法学习day.20】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.划分字母区间

题目链接:763. 划分字母区间 - 力扣（LeetCode）

题面:

代码:

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> list = new ArrayList<>();char[] srr = s.toCharArray();int n = s.length();int[] addr = new int[30];for(int i = 0;i<n;i++){addr[srr[i]-'a'] = i;}int count = 0;int l = 0;int flag = 0;int flagl = 0;while(l<n){if(flag == 0){count++;flagl = addr[srr[l]-'a'];if(flagl==l){list.add(1);count=0;}flag=1;}else{flagl = Math.max(addr[srr[l]-'a'],flagl);count++;if(l==flagl){list.add(count);count = 0;flag = 0;}}l++;}return list;}
}

2.合并区间

题目链接:56. 合并区间 - 力扣（LeetCode）

题面:

代码:

class Solution {public int[][] merge(int[][] intervals) {int n = intervals.length;int[][] ans = new int[n][2];Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] - o2[0];}});int xl = 0;int xr = 0;int flag = 0;int l = 0;int count = 0;while (l < n) {if (flag == 0) {if (l == n - 1) {ans[count][0] =intervals[l][0];ans[count++][1] =intervals[l][1];l++;break;}xl = intervals[l][0];xr = intervals[l][1];flag=1;}else{if((intervals[l][0]<=xr&&xr<=intervals[l][1])||(xr>=intervals[l][1]&&xl<=intervals[l][0])){xr =Math.max(intervals[l][1],xr);xl =Math.min(intervals[l][0],xl);if(l==n-1){ans[count][0] =xl;ans[count++][1] = xr;break;}}else{ans[count][0] =xl;ans[count++][1] = xr;l--;flag = 0;}}l++;}int[][] ans2 = new int[count][2];for(int i = 0;i<count;i++){ans2[i]=ans[i];}return ans2;}
}