WeetCode2滑動視窗系列
2022-11-27 18:06:39
一丶[無重複字元的最長子串](3. 無重複字元的最長子串 - 力扣（Leetcode）)
思路:
維護一個視窗，視窗中不存在重複的字元，視窗右邊界從第一個字元移動到最後，使用一個變數記錄視窗大小的最大值
那麼問題就變成了：怎麼確保視窗中不存在重複的字元，我們可以使用一個set，每次發現right位置的字元A重複後，就一直移動到之前A字元位置的下一個。比如 BACDHA，此時right位於第二個A，set中包含字元BACDH，為了維持不重複，我們要將左邊界移動到第一個C的位置，while迴圈讓left右移，並刪除left位置的字元，直到第一個A被刪除
繼續思考下，其實沒必要使用一個set，直接使用一個map即可，map需要記錄字元和這個字元最近出現的位置,當前字元重複A的時候，就讓left移動到A最近出現位置的前一個。比如BACDHA，此時right為A，map中記錄了B->0，A->1等資訊，我們只需要讓left移動到1+1（A最近出現於下標1，left需要移動到2位置）然後再map中重新記錄A->5即可
程式碼：
public int lengthOfLongestSubstring(String s) {
//空字串
if(s==null||s.length()==0){
return 0 ;
}
//視窗大小 最大值
int res = 0;
int left = 0;
int right = 0;
int len = s.length();
//key字元，value 這個字元最近在什麼位置出現
HashMap<Character,Integer> recentLocation = new HashMap<>();
while(right<len){
//當前子u發
char curChar = s.charAt(right);
//獲取這個字元出現的位置
Integer index = recentLocation.get(curChar);
//如果不為null 說明這個字元曾經出現過 那麼這時候需要 讓left 移動
if(index!=null){
left = Math.max(index+1,left);
}
//記錄下最近的位置
recentLocation.put(curChar,right);
right++;
//視窗最大長度更新
res = Math.max(res,right-left);
}
return res;
}
二丶[最小覆蓋子串](76. 最小覆蓋子串 - 力扣（Leetcode）)
思路：
使用一個Map表示當前滑動串列埠虧欠t中字元的數量， key 字元 value 當前視窗中虧欠的數目，虧欠的意思是當前視窗至少還需要多少個key的字元才滿足t
當left小於right的時候，我們儘可能讓left向右滑動，那麼什麼時候left可以向右滑暱？——當前left是一個t中根本不存在的字元，或者視窗中left位置的字元數量大於t中的數量（對應下面兩圖）（這其實是有貪心的思想在其中的，題目是找最短的，那麼left越接近right 那麼越短）並且虧欠map需要同時維護
然後我們需要移動right指標，同時維護虧欠map
那麼什麼時候視窗中滿足要求包含了t中所有字元暱——虧欠map中不存在value大於0的entry，這時候我們需要更新最佳結果
並且找到一個答案之後，我們需要left向右移動一個位置，並維護虧欠map，比如s=ADOBECODEBANC，t=ABC我們第一次找到符合的結果是ADOBEC，這時候需要left向右，因為後面存在更優秀的答案。
程式碼：
class Solution {
public String minWindow(String s, String t) {
//逆天用例
if (s == null || s.length() == 0) {
return null;
}
if(s.length() < t.length()){
return "";
}
char[] tCharArray = t.toCharArray();
// key 字元 value 當前視窗中虧欠的數目，虧欠的意思是當前視窗至少還需要多少個key的字元才滿足t
// value 為正數 表示視窗欠 t，0表示互不虧欠，負數表示視窗中此字元數目多於t
Map<Character, Integer> owesCharCountMap = new HashMap<Character, Integer>();
//初始化虧欠的數目
for (char loop : tCharArray) {
owesCharCountMap.put(loop, owesCharCountMap.getOrDefault(loop, 0) + 1);
}
String res = null;
int left = 0;
int right = 0;
while (right < s.length()) {
//如果left對應字元是無關緊要的字元（t中不包含的字元）
//或者left對應的字元那怕刪掉 視窗中的字元也不會虧錢t中的字元
//滿足上面任意一點 那麼 left++
while (left < right && !isNecessary(left, s, owesCharCountMap)) {
//當前left的字元
char leftChar = s.charAt(left);
left++;
//當前視窗虧欠視窗中多少個
Integer count = owesCharCountMap.get(leftChar);
//如果不為null 說明leftChar 是t中的字元
if (count != null) {
//虧欠數++
owesCharCountMap.put(leftChar, count + 1);
}
}
//right位置的字元
char rightChar = s.charAt(right);
//right位置字元 視窗虧欠的數目
Integer count = owesCharCountMap.get(rightChar);
//right處字元是一個t中的字元 那麼虧欠數-1
if (count != null) {
owesCharCountMap.put(rightChar, count - 1);
}
//如果視窗滿足要求——指最起碼不欠t中字元，及包含了所有t中的字元，那怕存在富足
if (meetRequirementsOrNot(owesCharCountMap)) {
//sub以下
String tempRes = s.substring(left, right + 1);
//記錄
if (res == null || tempRes.length() < res.length()) {
res = tempRes;
}
//從視窗中 強制刪除left位置處的字元
//比如s=ADOBECODEBANC t = ABC 此時視窗中字元為ADOBEC 我們找到了一種結果，但是後續可能存在更好的答案
//刪除left位置的A 我們繼續找更好的結果
char leftChar = s.charAt(left);
Integer leftCount = owesCharCountMap.get(leftChar);
if (leftCount!=null){
owesCharCountMap.put(leftChar,leftCount+1);
}
left++;
}
right++;
}
return res == null ? "" : res;
}
private boolean meetRequirementsOrNot(Map<Character, Integer> owesCharCountMap) {
for (Integer v : owesCharCountMap.values()) {
if (v == null) {
continue;
}
if (v > 0) {
return false;
}
}
return true;
}
private boolean isNecessary(int left, String s, Map<Character, Integer> owesCharCountMap) {
//left 位置的字元
char leftChar = s.charAt(left);
//當前虧欠map中的對應的虧欠數目
Integer count = owesCharCountMap.get(leftChar);
//為null 說明這個字元都不是t字串中的字元 那麼說明left位置的字元沒必要存在於視窗中
if (count == null) {
return false;
}
//如果大於等於0 說明當前虧欠這個字元， 或者剛剛好，
//如果移動那麼視窗中的字元數將不夠覆蓋t中所有字元
if (count >= 0) {
return true;
}
//說明left處的字元不是必要的
//說明 當前視窗中這個字元的數量已經大於t中這個字元的數量
return false;
}
}
三丶[串聯所有單詞的子串](30. 串聯所有單詞的子串 - 力扣（Leetcode）)
思路：
我的思路其實和第二題一樣，也是恢復一個虧欠map 然後進行滑動視窗，只是這個開始滑動的位置應該是1~單個單詞長度這個範圍都進行滑動視窗，這一點很關鍵。
然後我們需要處理兩種情況
- 滑動視窗中包含了 words中不存在的單詞 ，那麼前功盡棄，我們需要從這個不存在單詞的結尾繼續滑動
- 滑動視窗中包含單詞1的數量大於了words陣列中單詞1的數量，那麼其實我們應該從第一個出現單詞1位置的下一個位置開始滑動
這個題推薦看題解30. 串聯所有單詞的子串 - 力扣（Leetcode）我的解法並不是很優秀
程式碼：
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
int singleWordLen = words[0].length();
if (singleWordLen * words.length > s.length()) {
return res;
}
//虧欠map
Map<String, Integer> owensMap = new HashMap<>();
for (String loop : words) {
owensMap.put(loop, owensMap.getOrDefault(loop, 0) + 1);
}
int roundStartPos = 0;
//從第一個位置開始 ，第二個位置開始 。。到單個單詞長度個位置
while (roundStartPos < singleWordLen) {
Map<String, Integer> owensMapTemp = new HashMap<>(owensMap);
int left = roundStartPos;
int right = roundStartPos;
//滑動視窗
while (right <= s.length() - singleWordLen) {
//left 位置的單詞 不是必要的
while (left < right && !isNecessary(left, singleWordLen, s, owensMapTemp)) {
String temp = s.substring(left, left + singleWordLen);
Integer count = owensMapTemp.get(temp);
if (count != null) {
owensMapTemp.put(temp, count + 1);
}
left += singleWordLen;
}
//right位置的單詞
String rightString = s.substring(right, right + singleWordLen);
Integer count = owensMapTemp.get(rightString);
//right位置的單詞 是我們需要的 那麼維護虧欠map
if (count != null && count >= 1) {
owensMapTemp.put(rightString, count - 1);
right += singleWordLen;
} else {
//right 位置的單詞 不是words陣列中的單詞 那麼直接然後right 跨過這個單詞，直接從下一個單詞開始
if (count == null) {
right = right + singleWordLen;
left = right;
owensMapTemp = new HashMap<>(owensMap);
} else {
//right位置的單詞是words陣列中的單詞 但是當前視窗中這個單詞數量 已經 大於words陣列中這個單詞數量的單詞
//那麼刪除頭部的第一個單詞 然後繼續，
String temp = s.substring(left, left + singleWordLen);
Integer tempCount = owensMapTemp.get(temp);
if (tempCount != null) {
owensMapTemp.put(temp, tempCount + 1);
}
left += singleWordLen;
}
}
//符合要求 那麼left 移動到下一個單詞 並繼續 找出所有答案
if (meetRequire(owensMapTemp)) {
res.add(left);
String temp = s.substring(left, left + singleWordLen);
Integer tempCount = owensMapTemp.get(temp);
if (tempCount != null) {
owensMapTemp.put(temp, tempCount + 1);
}
left += singleWordLen;
}
}
roundStartPos++;
}
return res;
}
private boolean isNecessary(int left, int singleWordLen, String s, Map<String, Integer> owensMapTemp) {
String temp = s.substring(left, left + singleWordLen);
Integer count = owensMapTemp.get(temp);
if (count == null) {
return false;
}
if (count < 0) {
return false;
}
return true;
}
private boolean meetRequire(Map<String, Integer> owensMapTemp) {
for (Integer c : owensMapTemp.values()) {
if (c == null) {
continue;
}
if (c > 0) {
return false;
}
}
return true;
}
}
四丶[重複的DNA序列](187. 重複的DNA序列 - 力扣（Leetcode）)
思路：
這個題挺逆天的，很難想到怎麼用滑動視窗做，使用2進位製表示字母A，C，G，T，分別使用00，01，02，03，這樣視窗滑動的時候就是第一個字母出去，意味著二進位制表示左移位2，右邊字元進來，使用位元運算
程式碼：
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
if(s == null || s.length()<=10){
return new ArrayList<>();
}
List<String> res = new LinkedList<>();
Map<Integer,Integer> memory = new HashMap<Integer,Integer>();
int right = 0;
int firstBi = 0;
while(right<10){
firstBi = (firstBi<<2)| binaryOf(s.charAt(right));
right++;
}
memory.put(firstBi,1);
while(right < s.length()){
int bi = binaryOf(s.charAt(right));
//左邊字元出去 右邊字元進來
firstBi = ((firstBi<<2) |bi)&((1<<20)-1);;
int count =memory.getOrDefault(firstBi,0)+1;
memory.put(firstBi,count);
if(count == 2){
res.add(s.substring(right+1-10,right+1));
}
right++;
}
return res;
}
private int binaryOf(char a){
if(a == 'A'){
return 0;
}
if(a == 'C'){
return 1;
}
if(a == 'G'){
return 2;
}
if(a == 'T'){
return 3;
}
return -1;
}
}
五丶[長度最小的子陣列](209. 長度最小的子陣列 - 力扣（Leetcode）)
思路：太簡單了，視窗描述當前子資料，使用sum記錄當前和，如果大於target那麼更新長度，如果減去左邊界的值還能大於，那麼left++。直到right到 陣列邊界
class Solution {
public int minSubArrayLen(int target, int[] nums) {
if(nums == null||nums.length == 0){
return 0;
}
int left = 0;
int right = 1;
int sum =nums[0];
int minLen = sum>target?1:0;;
while(right<nums.length){
sum +=nums[right];
while(left<right && sum - nums[left]>=target){
sum -= nums[left];
left++;
}
if(sum>=target){
if(minLen == 0||minLen>right-left+1){
minLen = right - left+1;
}
}
right++;
}
return minLen;
}
}
六丶[存在重複元素 II](219. 存在重複元素 II - 力扣（Leetcode）)
思路：
維護一個長度為k的滑動視窗，使用set記錄視窗中的數位，每次left位置的資料從視窗中出去，right位置的數進來，首先刪除set中left代表的數位，然後如果right位置的數位存在於set中那麼說明重複
程式碼：
public boolean containsNearbyDuplicate(int[] nums, int k) {
if(nums == null || nums.length<=1){
return false;
}
if(k == 0){
return false;
}
int left = 0;
int right = 0;
Set<Integer>memory = new HashSet<Integer>();
while(right<k+1 && right<nums.length){
if(!memory.add(nums[right])){
return true;
}
right++;
}
while(right <nums.length){
int newNum = nums[right];
memory.remove(nums[left++]);
right++;
if(!memory.add(newNum)){
return true;
}
}
return false;
}
七丶[存在重複元素 III](220. 存在重複元素 III - 力扣（Leetcode）)
思路：
思路和六類似，但是問題在於，我們如何快速的判斷是否存在一個數，它和視窗中的數滿足abs(nums[i] - nums[j]) <= t，這時候我們應該想到TreeSet，基於紅黑樹進行如此的判斷的速度是logN
程式碼：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
if (nums == null || nums.length == 0) {
return false;
}
if (indexDiff == 0) {
return false;
}
TreeSet<Integer> ts = new TreeSet<>();
int left = 0;
int right = 0;
while (right < indexDiff + 1 && right < nums.length) {
if (exist(ts,nums[right],valueDiff)){
return true;
}
ts.add(nums[right]);
right++;
}
while (right < nums.length) {
ts.remove(nums[left++]);
if (exist(ts,nums[right],valueDiff)){
return true;
}
ts.add(nums[right++]);
}
return false;
}
private boolean exist(TreeSet<Integer> ts, int value, int diff) {
//Set中是否 存在一個數A 滿足 abs(A-value)<=diff
//A>=value 最小的數 min 是否滿足 min - value <= diff
//A<=value 最大的數max 是否滿足 value - max<= diff
Integer min = ts.ceiling(value);
if (min != null && min - value <= diff) {
return true;
}
Integer max = ts.floor(value);
if(max!=null&&value - max<=diff){
return true;
}
return false;
}
}
八丶[滑動視窗最大值](239. 滑動視窗最大值 - 力扣（Leetcode）)
思路：
視窗大小恆定為k大小，從頭移動到尾巴，我們需要一種資料結構記錄視窗此時的最大值，第一反應使用優先佇列，入隊時right位置的值，出隊是left位置的值，但是這存在一個問題，如1,3,-1,3,2,2,k=3.當前視窗運動到1,【3,-1,3】,2,2 優先佇列記錄了3，-1緊接著left位置元素刪除的時候會導致佇列中只有一個1，隨後right位置入隊，佇列維護了-1，2導致結構少了一個3。我們需要轉變思想，佇列每一個元素記錄兩個內容——值和對應的下標，當我們發生堆頂元素下標不在視窗中的時候進行刪除。
上面優先佇列的使用是整個複雜度來到NLogN，其實還有另外一個資料結構可以實現這個功能，單調棧——我們維護一個單調遞減的棧，當j<i,並且i位置值大於j位置值的時候，我們還有什麼必要維護j下標的值暱，
程式碼：
1.優先佇列
public int[] maxSlidingWindow(int[] nums, int k) {
//優先佇列 維護滑動視窗中的最大值
if(nums == null || nums.length < k ){
return nums;
}
int[]res = new int[nums.length - k +1];
//優先使用值進行比較，值越大越在堆頂
//其次使用下標進行比較，下表越大越在堆頂，下標越大 活得越久
PriorityQueue<int[]> q = new PriorityQueue<>((i,j)->i[0]!=j[0]?j[0]-i[0]:j[1]-i[1]);
int right = 0;
while(right<k){
q.add(new int[]{nums[right],right});
right++;
}
res[0] = q.peek()[0];
int count = 1;
while(right<nums.length){
q.offer(new int[]{nums[right],right});
while(q.peek()[1] <= right - k){
q.poll();
}
right++;
res[count++]=q.peek()[0];
}
return res;
}
2.單調棧
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null ){
return nums;
}
int[]res = new int[nums.length - k +1];
//佇列中的值是下標 但是必須保證這些下標值是單調遞減的
//當前 i<j nums[j]>=nums[i] 這時候num[i]對應下標 不需要維護了
//說是單調棧其實是雙向佇列，因為我們需要看棧底元素
LinkedList<Integer> ll = new LinkedList<Integer>();
int right = 0;
//初始化雙端佇列
while(right < k){
//nums[ll.getLast()] <= nums[right]
//對應 1，2，3，4 k =3 初始化的時候 【1，2，3】4 這時候我們只需要維護3即可
while(!ll.isEmpty() && nums[ll.getLast()] <= nums[right]){
ll.removeLast();
}
ll.addLast(right);
right++;
}
res[0] = nums[ll.getFirst()];
int count = 1;
while(right < nums.length){
//同上
while(!ll.isEmpty() && nums[ll.getLast()] <= nums[right]){
ll.removeLast();
}
ll.addLast(right);
//如果佇列頭 也就是最大的值 將不處於視窗外
while(ll.getFirst() <= right-k){
ll.removeFirst();
}
res[count++] = nums[ll.getFirst()];
right++;
}
return res;
}
九丶[找到字串中所有字母異位詞](438. 找到字串中所有字母異位詞 - 力扣（Leetcode）)
思路：
滑動視窗大小為p長度，使用一個map記錄視窗中字元和對應的數量，當每種字元數量和p相同是，記錄下left的位置，left++的時候更新map，right++的時候更新map
程式碼：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
if(s == null || s.length()<p.length()){
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
if(s.equals(p)){
res.add(0);
return res;
}
//記錄p中的字元和對應的數量，因為都是小寫字母，26長度的陣列足以
int[] pCharCount = new int[26];
for(int i= 0; i<p.length();i++){
char c = p.charAt(i);
pCharCount[c-'a']++;
}
//記錄視窗中字元和隊友的數量
int[] windowCharCount = new int[26];
int left = 0 ;
int right = 0;
while(right<s.length()){
//左邊界++
while(right - left + 1 > p.length()){
windowCharCount[s.charAt(left)-'a']--;
left++;
}
//右邊界++
windowCharCount[s.charAt(right)-'a']++;
//字元和數目 和p一樣
if(meetRequire(pCharCount,windowCharCount)){
res.add(left);
}
right++;
}
return res;
}
private boolean meetRequire(int[] pCharCount,int[] windowCharCount ){
for(int i =0;i<26;i++){
if(pCharCount[i]!=windowCharCount[i]){
return false;
}
}
return true;
}
}
十丶[替換後的最長重複字元](424. 替換後的最長重複字元 - 力扣（Leetcode）)
思路：
維護一個視窗，我們需要保證視窗中的字元替換k次之後，都是相同的字元——字元總數-最大字元出現次數<=k
如果不滿足這個條件 那麼左邊界++，直到滿足
程式碼：
class Solution {
public int characterReplacement(String s, int k) {
if(s == null ){
return 0;
}
if(s.length() <=k){
return s.length();
}
int res = 0;
int left = 0;
int right = 0;
int[]charCount = new int[26];
while(right<s.length()){
charCount[s.charAt(right)-'A']++;
while(!meetRequire(charCount,k)){
charCount[s.charAt(left)-'A']--;
left++;
}
res = Math.max(res,right - left+1);
right++;
}
return res;
}
private boolean meetRequire(int[]charCount,int k){
int max = -1;
int sum = 0;
for(int c : charCount){
sum+=c;
max = Math.max(max,c);
}
return sum-max<=k;
}
}