面試經典150題【41-50】

49.字母異位詞分組

用這種流式的處理
return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> { 處理邏輯 }））.values() );
不然處理起來太麻煩了。

class Solution {public List<List<String>> groupAnagrams(String[] strs) {return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> {// 返回 str 排序后的結果。// 按排序后的結果來grouping by，算子類似于 sql 里的 group by。char[] array = str.toCharArray();Arrays.sort(array);return new String(array);})).values());}
}

如果不排序的話，可以進行編碼： [b,a,a,a,b,c] 編碼成 a3b2c1， 然后再group by.

class Solution {public List<List<String>> groupAnagrams(String[] strs) {return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> {int[] counter = new int[26];for (int i = 0; i < str.length(); i++) {counter[str.charAt(i) - 'a']++;}StringBuilder sb = new StringBuilder();for (int i = 0; i < 26; i++) {// 這里的 if 是可省略的，但是加上 if 以后，生成的 sb 更短，后續 groupingBy 會更快。if (counter[i] != 0) {sb.append((char) ('a' + i));sb.append(counter[i]);}}return sb.toString();})).values());}
}

1. 兩數之和

每遍歷一個數，就把這個數字放到哈希表里。當遍歷到下一個數字的時候，看哈希表里是否存在Key為 target - nums[i] 的值。

202.快樂數

這個如果不是1，會進入一個循環。判斷循環就用雙指針就行。

判斷成環。一個是可以用快慢指針，他們倆相遇則有環。一個是可以用一個set,如果有重復元素則有環。

219. 存在重復元素II

區間大小為k，但是怎么保證K個里面能直接查出元素呢。
方法一：定義一個大小為k的hashSet, 如果包含元素則說明重復。因為hashSet會自動擴容，所以寫法是： if(hashSet.size() > k) hashSet.remove(nums[ i -k ] )
方法二：哈希表記錄[k,v]—> [ nums[i],i] ,如果包含則比較與i的距離，大于k則將[nums[i],j] 賦值給[nums[i],i] ，繼續遍歷。

128.最長連續序列

因為是O(n) ，所以不能排序。遍歷一遍，放到set里。
然后再遍歷一遍Set, 如果包含 nums[i]+1,依次遍歷有沒有nums[i] +2, nums[i] +3 等等
但是這樣也會導致很多重復的遍歷。 可以放到map里 [key,value] ->[ nums[i], 左右最長的長度]
當前的長度 = left + right +1

 public int longestConsecutive(int[] nums) {HashMap<Integer,Integer> hashMap=new HashMap<>();int ans=0;for(int i=0;i<nums.length;i++){//包含說明以前處理過，不包含的話可能是單獨，也可能是邊界，也可能是剛好插在倆個大條之間if(!hashMap.containsKey(nums[i])){int left=hashMap.getOrDefault(nums[i]-1,0);int right=hashMap.getOrDefault(nums[i]+1,0);int tempAns=left+right+1;if(tempAns>ans){ans=tempAns;}hashMap.put(nums[i],tempAns);//不能只更新自己，邊界也要更新hashMap.put(nums[i]+right,tempAns);hashMap.put(nums[i]-left,tempAns);}}return ans;}

228. 匯總區間

按照題意模擬即可。

56.合并區間（華為面試題）

先按左區間排序，然后依次遍歷，根據 nums[i+1][0] 和 nums[i][1] 判斷是否需要合并。

public class LC56 {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0]-o2[0];}});ArrayList<int[]> ans=new ArrayList<>();int left=intervals[0][0],right=intervals[0][1];for(int i=1;i<intervals.length;i++){if(intervals[i][0]>right){//不合并，裝載ans.add(new int[]{left,right});//開始記錄新的區間left=intervals[i][0];right=intervals[i][1];}else{//合并區間right=Math.max(right,intervals[i][1]);}}//無論是intervals里只有一個元素的特判，  還是 正常情況下最后一步， 都要有下面這一行。ans.add(new int[]{left,right});return ans.toArray(new int[][]{});}
}

57.插入區間

和56.合并區間一個意思

452.用最少的箭引爆氣球

所有的這種二維數組的，都要先排序。無非就是按照 左邊界 排序 或者按照 右邊界 排序。
而氣球這種場景，應該是按照右邊界排序，然后射擊第一個存在的氣球的最右邊。
判斷此次射擊會爆幾個氣球，要看別的氣球的左邊界是否小于射擊點。（因為是按右邊界排序的，右邊肯定是大的，左邊小就能被射到）

public int findMinArrowShots(int[][] points) {if(points.length==0) return 0;Arrays.sort(points, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {//return o1[1]-o2[1];if(o1[1]>o2[1]){return 1;}else if(o1[1]<o2[1]){return -1;}else{return 0;}}});//按右邊界  進行排序//擊斃第一個氣球的最右邊，能擊斃幾個算幾個。//pos為擊斃點int pos=points[0][1];int ans=1;for(int i=0;i<points.length;i++){//因為是按右邊界排序的，判斷第i個氣球爆沒爆，要看第i個氣球的左邊界。if(pos<points[i][0]){ans++;pos=points[i][1];}}return ans;}

20.有效的括號

一個個單詞放到棧里，放左括號，遇到右括號檢查棧頂是否為對應的左括號即可。