文章目錄
- 1. 演算法思想
- 1.1 思想
- 1.2 套路代碼
- 1.3例題精講
- 1.3.1 最小覆寫子串
- 1.3.2 找到字串中所有字母異位詞
- 2. 相關例題
- 2.1. 重復的DNA序列
- 2.2. 存在重復元素 II
1. 演算法思想
這里標注一下，本文參考于 《labuladong的演算法小抄》
1.1 思想
滑動視窗，顧名思義：
滑動的視窗，其實就是使用雙指標進行維護一個視窗，經過相關題目的練習，可以得出該視窗大小有固定大小的例題，也有不固定大小的例題，我們要根據相應的題目進行分析，而如果視窗是固定大小的，我們一般會根據視窗大小要超越固定大小而進行縮小視窗，而不是固定大小的視窗的就根據題目具體意思進行相應的視窗縮小，
1.2 套路代碼
int l = 0, r = 0;
while(r < s.length()){
擴大視窗
c是要添加進去的字符
char c = s.charAt(r);
r ++;
這里進行相關的操作
while(視窗需要縮小時){
縮小視窗
d是要從視窗中出去的字符
char d = s.charAt(l);
l ++;
這里進行相關的操作
}
}
相關模板講解：
- 在這里我們使用的是雙指標演算法技巧，初始化
l = 0 ,r = 0 - 我們這里維護的區間視窗為
[l,r)， r作為右指標進行擴大視窗，c是放入視窗內部的字符l作為左指標進行縮小視窗，d是從視窗中去除的字符- 那么
其他需要加進來的代碼就是題目要求我們維護的相應的資料結構，和維護該資料結構的相關操作了，看我博客的友友們要隨機應變哦，
1.3例題精講
1.3.1 最小覆寫子串
思路分析：
- 在擴大視窗的同時，我們需要維護什么？
因為題目要我們求的是包含相應模板串中的所有字符，那么相應的字符可能是分散于我們求出來的答案中的，所以我們需要去維護
一個名為need的map集合存下模板串的所有字符及個數，還要一個名為win的map集合存下相應主串中滑動視窗中是上一個map集合中所包含的字符，還需要一個變數valid存下滑動視窗中和模板串中對應字符的個數相同的字符個數，因為是要求子串，所以還需要一個start記錄相應的起始下標，len記錄相應的長度，
- 什么時候縮小視窗？
當
valid等于need的大小時，就是相應的主串的滑動視窗包含模板串的所有字符了，此時需要縮小視窗，
3.在什么地方、什么時候更新start和len?
在
內層while中進行更新，當len小于r - l時，
AC代碼：
public String minWindow(String s, String t) {
Map<Character,Integer> map = new HashMap<>();
Map<Character,Integer> map2 = new HashMap<>();
for(int i = 0; i < t.length(); i ++) map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0) + 1);
int l = 0, r = 0;
int valid = 0;
int start = 0, len = Integer.MAX_VALUE;
while(r < s.length()){
char c = s.charAt(r);
r ++;
if(map.containsKey(c)){
map2.put(c,map2.getOrDefault(c,0) + 1);
if(map.get(c).equals(map2.get(c))){
valid ++;
}
}
while(valid == map.size()){
if(r - l < len){
start = l;
len = r - l;
}
char d = s.charAt(l);
l ++;
if(map.containsKey(d)){
if(map.get(d).equals(map2.get(d))){
valid --;
}
map2.put(d,map2.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start,start + len);
}
特別提醒：
Byte,Short,Integer,Long 這 4 種包裝類默認創建了數值 [-128，127] 的相應型別的快取資料，Character 創建了數值在 [0,127] 范圍的快取資料，Boolean 直接回傳 True Or False， 兩種浮點數型別的包裝類 Float,Double 并沒有實作常量池技術，
所以如果是超出相應的范圍，就不能使用
==判斷數值大小，而必須使用equals方法
1.3.2 找到字串中所有字母異位詞
思路分析：
- 題目分析
這是
視窗大小固定的相關例題，上面那一道是視窗大小不是固定的，
- 所需要維護的資料結構？
因為模板串的字符順序和主串的不一定相同，所以
維護的資料結構和上面的一樣，這里不再過多講解，
- 什么時候縮小視窗？
因為是固定大小的視窗，所以一般是
視窗大小等于相應的視窗大小時，先進行 是否符合要求判斷，然后進行縮小視窗，
AC代碼：
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> findAnagrams(String s, String p) {
Map<Character,Integer> need = new HashMap<>();
Map<Character,Integer> win = new HashMap<>();
// 初始化need
for(int i = 0; i < p.length(); i ++) need.put(p.charAt(i),need.getOrDefault(p.charAt(i),0) + 1);
int l = 0, r = 0;
int valid = 0;
while(r < s.length()){
char c = s.charAt(r);
r ++;
if(need.containsKey(c)){
win.put(c,win.getOrDefault(c,0) + 1);
if(need.get(c).equals(win.get(c))){
valid ++;
}
}
while(r - l >= p.length()){
// 相應的操作
if(valid == need.size()) list.add(l);
char d = s.charAt(l);
l ++;
if(need.containsKey(d)){
if(need.get(d).equals(win.get(d))){
valid --;
}
win.put(d,win.get(d) - 1);
}
}
}
return list;
}
}
可以練手的相關題目：
567. 字串的排列
這里對前面的滑動視窗問題進行總結：
前面的三個問題是難度比較高的三個滑動視窗問題，因為
他們的對應的模板串的字符在主串中相應位置不是固定的，所以我們使用valid進行描述到達相應的標準，但是我們需要對我們所確定的區間進行字符記錄，且記錄的字符要是相應的模板串中含有的，
2. 相關例題
后面的問題就相對比較簡單：
2.1. 重復的DNA序列
思路分析：
- 題目分析
其實
定長是10，而又是相應的字串，并且不和前面相應的例題一樣，他這相應的字符順序截取的是什么就是什么，不需要改變，那么就可以直接根據相應的substirng，但是就是需要統計出現的次數，
- 維護的資料結構
map集合，截取后存入相應的map集合，邊放邊存，然后根據條件進行判斷，
AC代碼：
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
int L = 10;
List<String> list = new ArrayList<>();
Map<String,Integer> map = new HashMap<>();
for(int i = 0; i <= s.length() - L; i ++){
String a = s.substring(i,i + L);
map.put(a,map.getOrDefault(a,0) + 1);
if(map.get(a) == 2){
// 為什么是== 2的時候，如果是大于2的話就會導致冗余情況
list.add(a);
}
}
return list;
}
}
2.2. 存在重復元素 II
思路分析:
- 題目分析
這是
視窗大小固定的相關例題，上面那一道是視窗大小不是固定的，
- 維護的資料結構？
set集合，因為需要判斷在前面的區間中是否出現過，所以使用set集合
- 縮小視窗的時機
因為這里維護的是
[i - k + 1,i]區間，所以當set.size() > k的時候縮小視窗，
AC代碼：
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
for(int i = 0; i < nums.length; i ++){
// 相當于一個數字在前面的一段區間內只能出現一次
// 每次遍歷的時候加入set集合
// 該步驟簡化了判斷在區間距離小于k + 1的情況下是否存在相同元素
if(set.contains(nums[i])) return true;
// 在這里進行添加的原因是前面已經判斷過了，set集合中不存在相應的重復元素
set.add(nums[i]);
if(set.size() > k){
// 但是set集合中的元素個數不能超過k + 1個
set.remove(nums[i - k]);
}
}
return false;
}
}
220. 存在重復元素 III
思路分析：
- 題目分析
這里的思路和前面的相似，
- 注意點
但是就是我們這里需要說明的是
添加操作的相應的位置改變，因為前面的那一道題是判斷過集合不存在相應的元素，才進行添加，而我們這里沒有，
if(ts.size() + 1 > k){
ts.remove(nums[i - k] * 1L);
}
ts.add(nums[i] * 1L);
AC代碼：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(k == 0) return false;
TreeSet<Long> ts = new TreeSet<>();
for(int i = 0; i < nums.length; i ++){
Long u = nums[i] * 1L;
// TreeSet 是一個可以提供找到大于相應值的最小值 和 一個可以找到小于相應值的最大值的方法
Long f = ts.floor(u);
Long r = ts.ceiling(u);
if(f != null && u - f <= t) return true;
if(r != null && r - u <= t) return true;
if(ts.size() + 1 > k){
ts.remove(nums[i - k] * 1L);
}
ts.add(nums[i] * 1L);
}
return false;
}
}
學到的新知識：
TreeSet: 一個可以提供大于相應元素的最小值和一個可以提供小于相應元素最大值的集合，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/341878.html
標籤：其他
下一篇：演算法開啟小碼農雙鏈表血脈