?763.劃分字母區間?
字符串 S 由小寫字母組成。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現在一個片段中。返回一個表示每個字符串片段的長度的列表。
示例：
- 輸入：S = "ababcbacadefegdehijhklij"
- 輸出：[9,7,8] 解釋： 劃分結果為 "ababcbaca", "defegde", "hijhklij"。 每個字母最多出現在一個片段中。 像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數較少
之前在回溯部分，有用回溯算法分割過字符串，但是屬于暴力搜索，時間復雜度較高。
題目要求同一字母最多出現在一個片段中，并且劃分盡可能多的片段，那么如何把同一個字母的都圈在同一個區間里呢？就是找到出現過的字母的最大終止位置。
可以分為如下兩步：
- 統計每一個字符最后出現的位置
- 從頭遍歷字符，并更新字符的最遠出現下標，如果找到字符最遠出現位置下標和當前下標相等了，則找到了分割點
class Solution {public List<Integer> partitionLabels(String s) {LinkedList<Integer> list=new LinkedList<>();int[] edge=new int[26]; char[] chars=s.toCharArray(); //將一個字符串轉換成一個字符（char）數組。//比如abecadf 那么edge[0]存儲的就是a出現的次數for(int i=0;i<chars.length;i++){edge[chars[i]-'a']=i; //統計每個字符出現的最后位置 ,按照字母的順序存儲}int idx=0, last=-1;for(int i=0; i<chars.length;i++){idx=Math.max(idx, edge[chars[i]-'a']); //遍歷出現過的元素，更新最遠位置if(i==idx){ //如果已經走到了前面出現過的覆蓋的最遠位置list.add(i-last);// 記錄當前子串的長度 last=i; //更新起點}}return list;}
}56. 合并區間
給出一個區間的集合，請合并所有重疊的區間。
示例 1:
- 輸入: intervals = [[1,3],[2,6],[8,10],[15,18]]
- 輸出: [[1,6],[8,10],[15,18]]
- 解釋: 區間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例?2:
- 輸入: intervals = [[1,4],[4,5]]
- 輸出: [[1,5]]
- 解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間。
- 注意：輸入類型已于2019年4月15日更改。 請重置默認代碼定義以獲取新方法簽名。
依舊是重疊區間問題，先按照start排序，再進行重疊判斷，本題相鄰區域也算重疊，因此若intervals[i][0]<=intervals[i-1][1]，則有重疊。若有重疊，則將區間的左右邊界判斷更新end使之成為兩個區間的最遠end，加入result數組，若不重合，更新start和end，直接加入原區間。
class Solution {public int[][] merge(int[][] intervals) {List<int[]> res=new LinkedList<>();Arrays.sort(intervals, (a,b)->Integer.compare(a[0], b[0]));int start=intervals[0][0];int end =intervals[0][1];for(int i=1;i<intervals.length;i++){if(intervals[i][0]>end){//不重疊res.add(new int[]{start, end});//將當前節點加入resstart=intervals[i][0]; //更新startend=intervals[i][1];}else{end=Math.max(end, intervals[i][1]); //更新最大右邊界}}res.add(new int[]{start, end});return res.toArray(new int[res.size()][]);}
}這里要注意一個語法基礎??在鏈表list里面添加值，然后把list鏈表添加進res鏈表中，在做算法題的時候，如果使用res.add(list)，輸出打印為空，因此需要res.add(new LinkedList＜Integer＞(list))。同理，在這里如果想要給鏈表res添加新的數組，一定也要res.add(new int[]{start, end});
)
