數組刷題<下>套路分析
- 2019 年 10 月 6 日
- 筆記
數組刷題<下>套路分析
一、雙索引技術-對撞指針1.167. 兩數之和 II – 輸入有序數組2. 345. 反轉字符串中的元音字母3.344. 反轉字符串4.125. 驗證迴文串5.11. 盛最多水的容器二、雙索引技術-滑動窗口1.209. 長度最小的子數組2.438. 找到字符串中所有字母異位詞3.76. 最小覆蓋子串
一、雙索引技術-對撞指針
類似題目：
- 167. 兩數之和 II – 輸入有序數組
- 345. 反轉字符串中的元音字母
- 344. 反轉字符串
- 125. 驗證迴文串
- 11. 盛最多水的容器
注意的問題：
- 定義前後指針
- 向中間靠攏
1.167. 兩數之和 II – 輸入有序數組
給定一個已按照升序排列 的有序數組，找到兩個數使得它們相加之和等於目標數。
函數應該返回這兩個下標值 index1 和 index2，其中 index1 必須小於 index2。
說明:
- 返回的下標值（index1 和 index2）不是從零開始的。
- 你可以假設每個輸入只對應唯一的答案，而且你不可以重複使用相同的元素。
示例:
輸入: numbers = [2, 7, 11, 15], target = 9 輸出: [1,2] 解釋: 2 與 7 之和等於目標數 9 。因此 index1 = 1, index2 = 2 。
實現思路：
使用雙索引技術-對撞指針：
- 一般會是大於或者小於。
- 如果大i++ 小 j–
- 兩個索引在往中間走。對撞指針。
實現：
class Solution { public int[] twoSum(int[] numbers, int target) { int[] res=new int[2]; int i=0,j=numbers.length-1; while(i<j){ if(numbers[i]+numbers[j]==target){ res[0]=i+1; res[1]=j+1; break; }else if(numbers[i]+numbers[j]>target){ j--; }else{ i++; } } return res; } }
2. 345. 反轉字符串中的元音字母
編寫一個函數，以字符串作為輸入，反轉該字符串中的元音字母。
示例 1:
輸入: "hello" 輸出: "holle"
示例 2:
輸入: "leetcode" 輸出: "leotcede"
說明: 元音字母不包含字母"y"。
實現思路：
使用雙索引技術-對撞指針：
- 兩個索引在往中間走。對撞指針。
實現：
這道題難點在於語言的熟悉度。比如在下面java中可以用匿名函數來創建HashMap並初始化。中間使用s.charAt(i)函數獲取每個字符，最後將char數組轉為String。
class Solution { public String reverseVowels(String s) { int i=0,j=s.length()-1; HashMap<Character,Integer> hashMap = new HashMap<Character, Integer>(){ { put('a',0);put('A',0);put('e',0);put('E',0);put('i',0); put('I',0);put('o',0);put('O',0);put('u',0);put('U',0); } }; char[] str = new char[s.length()]; while(i<=j){ if(hashMap.getOrDefault(s.charAt(i),-1)==-1){ str[i]=s.charAt(i); i+=1; continue; } if(hashMap.getOrDefault(s.charAt(j),-1)==-1){ str[j]=s.charAt(j); j-=1; continue; } str[i]=s.charAt(j); str[j]=s.charAt(i); i+=1; j-=1; } return String.valueOf(str); } }
3.344. 反轉字符串
編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。
不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。
你可以假設數組中的所有字符都是 ASCII 碼錶中的可打印字符。
示例 1：
輸入：["h","e","l","l","o"] 輸出：["o","l","l","e","h"]
示例 2：
輸入：["H","a","n","n","a","h"] 輸出：["h","a","n","n","a","H"]
實現思路：
使用雙索引技術-對撞指針：
- 兩個索引在往中間走。對撞指針。
實現：
兩邊交換即可。
class Solution { public void reverseString(char[] s) { int i=0,j=s.length-1; char temp; while(i<j){ temp=s[i]; s[i]=s[j]; s[j]=temp; i++; j--; } } }
4.125. 驗證迴文串
給定一個字符串，驗證它是否是迴文串，只考慮字母和數字字符，可以忽略字母的大小寫。
說明：本題中，我們將空字符串定義為有效的迴文串。
示例 1:
輸入: "A man, a plan, a canal: Panama" 輸出: true
示例 2:
輸入: "race a car" 輸出: false
實現思路：
使用雙索引技術-對撞指針：
- 兩個索引在往中間走。對撞指針。
實現：
兩邊往中間走即可。
class Solution { public boolean isPalindrome(String s) { int i=0,j=s.length()-1; s = s.toLowerCase(); while(i<j){ if(!((s.charAt(i) >= '0' && s.charAt(i) <= '9') || (s.charAt(i) >= 'a' && s.charAt(i) <= 'z'))){ i++; continue; } if(!((s.charAt(j) >= '0' && s.charAt(j) <= '9') || (s.charAt(j) >= 'a' && s.charAt(j) <= 'z'))){ j--; continue; } if(s.charAt(i)!=s.charAt(j)) return false; i++; j--; } return true; } }
上述是吧字符串全部轉小寫了，當然也可以在比較中轉：
class Solution { public static boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { if (!((s.charAt(i) >= '0' && s.charAt(i) <= '9') || (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'))) { i++; continue; } if (!((s.charAt(j) >= '0' && s.charAt(j) <= '9') || (s.charAt(j) >= 'a' && s.charAt(j) <= 'z') || (s.charAt(j) >= 'A' && s.charAt(j) <= 'Z'))) { j--; continue; } if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false; i++; j--; } return true; } }
5.11. 盛最多水的容器
給定 n 個非負整數 a1，a2，…，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。
說明：你不能傾斜容器，且 n 的值至少為 2。
img
圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
實現思路：
使用雙索引技術-對撞指針：
- 兩個索引在往中間走。對撞指針。
實現：
使用雙指針，選擇最小高度乘以間距即可。
class Solution { public int maxArea(int[] height) { int left=0,right=height.length-1; int area=0; while(left<right){ if(height[left]<height[right]){ area=Math.max((right-left)*height[left],area); left++; }else{ area=Math.max((right-left)*height[right],area); right--; } } return area; } }
上述簡化版：
class Solution { public int maxArea(int[] height) { int left=0,right=height.length-1; int area=0; while(left<right){ area=Math.max(area,(right-left)*Math.min(height[left],height[right])); if(height[left]<height[right]){ left++; }else{ right--; } } return area; } }
二、雙索引技術-滑動窗口
類似題目：
- 209. 長度最小的子數組
- 438. 找到字符串中所有字母異位詞
- 76. 最小覆蓋子串
注意的問題：
- 如何維護窗口？
1.209. 長度最小的子數組
給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和≥ s 的長度最小的連續子數組。如果不存在符合條件的連續子數組，返回 0。
示例:
輸入: s = 7, nums = [2,3,1,2,4,3] 輸出: 2 解釋: 子數組 [4,3] 是該條件下的長度最小的連續子數組。
進階:
如果你已經完成了O(n) 時間複雜度的解法, 請嘗試 O(n log n) 時間複雜度的解法。
實現思路：
當窗口內的值大於等於目標值，則壓縮窗口，左邊界向右壓縮，否則的話右邊界擴容。
注意邊界點：右邊界的index不能超過數組的最大值，另外右邊界與做左邊界都要指向計算和的當前元素，所以右窗口j從-1開始，先j++，這樣可以保證每次窗口的總和的右邊界是與j一致！
實現：
class Solution { public int minSubArrayLen(int s, int[] nums) { int i=0,j=-1; int n=nums.length; int number=n+1; int total=0; while(i<n){ if(j+1<n && total<s){ j++; total+=nums[j]; }else { total-=nums[i]; i++; } //獲取每次結果的窗口長度 if(total>=s){ if(number>j-i+1){ number=j-i+1; } } } //若不變，則沒有找到 if (number==n+1){ return 0; } return number; } }
滑動窗口升級版1：
class Solution { public int minSubArrayLen(int s, int[] nums) { int i=0,j=-1; int n=nums.length; int number=0; int total=0; while(i<n){ if(j+1<n && total<s){ j++; total+=nums[j]; }else { total-=nums[i]; i++; } //獲取每次結果的窗口長度 if(total>=s){ number=number==0?j-i+1:Math.min(j-i+1,number); } } return number; } }
滑動窗口升級版2：
class Solution { public int minSubArrayLen(int s, int[] nums) { int i=0; int sum=0; int number=0; for (int j=0;j<nums.length;j++){ sum+=nums[j]; while(sum>=s){ number=number==0?j-i+1:Math.min(j-i+1,number); sum-=nums[i++]; } } return number; } }
除了上述O(n)時間複雜度，題目中說了O(nlogn)呢？
實現思路：
二分法:
時間複雜度：O(nlogn)，空間複雜度O(n)。
思路：
將原先數組所有數字累加求和得到一個新數組，例如：
nums=[2,3,1,2,4,3] parNums=[0,2,5,6,8,12,15]
然後循環parNums，對每一個數組中的index對應的值，利用二分法找到最小的窗口。
舉個例子：
nums=[2,3,1,2,4,3] parNums=[0,2,5,6,8,12,15] -------------- i=0時 -------------- 第一輪 left=0,right=6 left<right,計算出mid=3，此時對應的值為6,mid距離i的和也就是6<7， 調整left=mid+1=4。 第二輪 left=4,right=6 left<right,計算出mid=5，此時對應的值為12，mid距離i的和也就是12>7， 調整right=mid-1。 是不是上述可以看作是查找7的二分法，那麼後面依次類推即可。 當然left調整也可以是left++，right調整也可以是right--，也可以AC,但是效率會低一些！ -------------- ......
實現：
循環+二分
public class Solution { public int minSubArrayLen(int s, int[] nums) { int[] parNums = new int[nums.length+1]; //構造nums元素依次累加數組 for(int i=1;i<parNums.length;i++){ parNums[i]=parNums[i-1]+nums[i-1]; } int min=0; for(int i=0;i<parNums.length;i++){ int left=i; int right=parNums.length-1; while(left<=right){ int mid=left+(right-left)/2; int subSum=parNums[mid]-parNums[i]; if(subSum>=s){ right=mid-1; //可以換成right--; min=min==0?mid-i:Math.min(min,mid-i); }else{ left=mid+1; //可以換成left++; } } } return min; } }
2.438. 找到字符串中所有字母異位詞
給定一個字符串 s 和一個非空字符串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。
字符串只包含小寫英文字母，並且字符串 s 和 p 的長度都不超過 20100。
說明：
- 字母異位詞指字母相同，但排列不同的字符串。
- 不考慮答案輸出的順序。
示例 1:
輸入: s: "cbaebabacd" p: "abc" 輸出: [0, 6] 解釋: 起始索引等於 0 的子串是 "cba", 它是 "abc" 的字母異位詞。 起始索引等於 6 的子串是 "bac", 它是 "abc" 的字母異位詞。
示例 2:
輸入: s: "abab" p: "ab" 輸出: [0, 1, 2] 解釋: 起始索引等於 0 的子串是 "ab", 它是 "ab" 的字母異位詞。 起始索引等於 1 的子串是 "ba", 它是 "ab" 的字母異位詞。 起始索引等於 2 的子串是 "ab", 它是 "ab" 的字母異位詞。
實現思路：
字母異位數指的是：字母異位詞指字母相同，但排列不同的字符串。所以只要滿足字母異位數，那麼p字符串的每個字符肯定會在字符串中出現！
實現：
題目中提到只考慮小寫字母，那麼創建一個數組長度包含所有小寫字母大小，這裡創建26個長度數組。使用ch-'a'來存儲每個字符與a字符的距離也就是一個int值。
循環s-p次，也就是讓p當作窗口掃描s字符串，然後在s中截取子串，並查看這個字串中的每個字符是否在p中存在(或者說p中的字符是否在子串)，這個判斷是通過對字串的每個字符累加，然後在p中去減，如果是>=0,那麼肯定是字母異位詞，<0肯定不是字母異位詞。最後把子串開始索引加入list中即可。
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>(); if(s==null || p==null||s.length()<p.length()) return res; for(int i=0;i<s.length()-p.length()+1;i++){ if(isAn(s.substring(i,i+p.length()),p)){ res.add(i); } } return res; } public boolean isAn(String s,String p){ int[] arr= new int[26]; for(char ch:s.toCharArray()){ arr[ch-'a']++; } for(char ch:p.toCharArray()){ arr[ch-'a']--; if(arr[ch-'a']<0) { return false; } } return true; } }
對上述優化，上述代碼在取子串後調用isAn函數的時候每次都會做循環，也就是連續幾個遞進會有重複的循環操作，所以效率非常低。
實現思路：
第一個循環讓arr數組統計字符串p的每個字符個數，第二個循環，讓滑動窗口達到p的長度，並計算第一個窗口是否滿足字母異位詞。第三個循環是根據s中的字符來調整窗口的左右邊界。
實現：
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> list = new ArrayList<>(); if(s==null || p==null || s.length()<p.length()) return list; int[] arr = new int[26]; for(int i=0;i<p.length();i++){ arr[p.charAt(i)-'a']++; } int p_len=p.length(); int left=0,right=p.length(); for(int i=0;i<p.length();i++){ arr[s.charAt(i)-'a']--; if (arr[s.charAt(i)-'a']>=0) p_len--; } if(p_len==0) list.add(0); while(right<s.length()){ if(arr[s.charAt(left)-'a']>=0) p_len++; arr[s.charAt(left)-'a']++; left++; arr[s.charAt(right)-'a']--; if (arr[s.charAt(right)-'a']>=0) p_len--; right++; if(p_len==0) list.add(left); } return list; } }
實現思路：
使用一個數組arr存儲p字符串的每個字符出現的個數。循環字符串s，right表示窗口的右邊界，left表示窗口的左邊界，根據s中每個窗口內的字符是否存在在arr中來調整左右邊界。
實現：
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> list = new ArrayList<>(); if(s==null || p==null || s.length()<p.length()) return list; int[] arr = new int[26]; for(int i=0;i<p.length();i++){ arr[p.charAt(i)-'a']++; } int p_len=p.length(); int left=0,right=0; while(right<s.length()){ arr[s.charAt(right)-'a']--; if (arr[s.charAt(right)-'a']>=0) p_len--; if(p_len==0) list.add(left); //維護窗口大小 if(right-left==p.length()-1){ if(arr[s.charAt(left)-'a']>=0) p_len++; //恢復 arr[s.charAt(left)-'a']++; left++; } right++; } return list; } }
3.76. 最小覆蓋子串
給定一個字符串 S 和一個字符串 T，請在 S 中找出包含 T 所有字母的最小子串。
示例：
輸入: S = "ADOBECODEBANC", T = "ABC" 輸出: "BANC"
說明：
- 如果 S 中不存這樣的子串，則返回空字符串
""。 - 如果 S 中存在這樣的子串，我們保證它是唯一的答案。
實現思路：
首先讓右指針不斷往前走,左指針不動,直到將窗口拉到最大,同時包含t中所有字符串。
定義一個HashMap,key為character,value為Integer。先循環t字符串長度，這個HashMap中保存了t中所有字符。key為t中字符，value為t中字符出現的次數。
然後定義左右指針，left與right，當s中的right對應的元素在HashMap中，就讓對應的value減1，每減1，也就是與t中匹配的字符串就得減去1，也就是t_len減去1。當t_len為0，表示right已經拉到最大，此時窗口包含所有t中元素，就要移動left，進而壓縮窗口大小，使得找出最小覆蓋子串。
實現：
class Solution { public static String minWindow(String s, String t) { HashMap<Character, Integer> hashMap = new HashMap<>(); if (s == null || t == null || s.length() < t.length()) return ""; for (int i = 0; i < t.length(); i++) { if(hashMap.get(t.charAt(i))!=null){ hashMap.put(t.charAt(i), hashMap.get(t.charAt(i)) + 1); }else{ hashMap.put(t.charAt(i), 1); } } int t_len = t.length(); int left = 0, right = 0; int minlen = s.length() + 1; int minleft=0; while (right < s.length()) { if (hashMap.containsKey(s.charAt(right))) { Integer in = hashMap.get(s.charAt(right)); in--; hashMap.remove(s.charAt(right)); hashMap.put(s.charAt(right),in); if (in >= 0) t_len--; //表示t中此時被訪問過的元素-1 } //窗口拉到了最大，尋找匹配，看是否是最小長度子串。 while(t_len == 0){ if(right - left + 1 < minlen){ minlen = right - left + 1; minleft = left; } //左邊的元素如果在hashMap中，那麼就要恢復原來的值，因為左邊的值必定被右邊right訪問過，而right訪問的時候只要在hashMap中，就會減去1，所以這裡要恢復，也就是+1，同是如果此時恢復過後的值>0就需要，讓t_len+1。表示t中此時沒被訪問過的元素+1。 if (hashMap.containsKey(s.charAt(left))) { Integer lt = hashMap.get(s.charAt(left)); lt++; if(lt>0){ t_len++; } hashMap.remove(s.charAt(left)); hashMap.put(s.charAt(left),lt); } left++; } right++; } if(minlen==s.length()+1){ return ""; } return s.substring(minleft, minleft + minlen); } }
上述精簡版:
class Solution { public static String minWindow(String s, String t) { HashMap<Character, Integer> hashMap = new HashMap<>(); if (s == null || t == null || s.length() < t.length()) return ""; for (int i = 0; i < t.length(); i++) { if(hashMap.get(t.charAt(i))!=null){ hashMap.put(t.charAt(i), hashMap.get(t.charAt(i)) + 1); }else{ hashMap.put(t.charAt(i), 1); } } int t_len = t.length(); int left = 0, right = 0; int minlen = s.length()+1,minleft=0; while (right < s.length()) { if (hashMap.containsKey(s.charAt(right))) { int rt = hashMap.getOrDefault(s.charAt(right), 0); rt--; hashMap.put(s.charAt(right), rt); if (rt >= 0) t_len--; } while(t_len == 0){ if(right - left + 1 < minlen){ minlen = right - left + 1; minleft = left; } if (hashMap.containsKey(s.charAt(left))) { int lt = hashMap.getOrDefault(s.charAt(left), 0); lt++; if(lt>0){ t_len++; } hashMap.put(s.charAt(left), lt); } left++; } right++; } return (minlen == s.length() + 1) ? "" : s.substring(minleft, minleft + minlen); } }
總結：第3題與第2題特別相似，都是先確定一個窗口，然後不斷調整左右窗口範圍，需要注意不同點：第2道題是讓t串的字符串出現在s中並且連續，所以滑動窗口的長度在第一次確定後就可以不變了。而第3道題則是先確定一個包含所有字符串t的窗口，不斷壓縮這個最大窗口，然後再繼續移動左右指針。
