點擊右邊

分享幾道以及「滑老虎機線數動窗口」無關的算法口試題

媒介科普:甚么是滑動窗口算法

滑動成績包括一個滑動窗口,它是一個運轉在一個大數組上的子列表,該數組是一個底層元素聚攏。

假定稀有組 [a b c d e f g h ],一個巨細為 3 的 滑動窗口 在其上滑動,則有:

[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]

一般環境下便是使用這個窗口在數組的 正當區間 內進行滑動,同時 靜態地 記載一些有效的數據,許多環境下,可以或許極大地提高算法地效率。

1. 滑動窗口最大值

標題泉源于 LeetCode 上第 239 號成績:滑動窗口最大值。標題難度為 Hard,現在經由過程率為 40.5% 。

標題描寫

給定一個數組 nums,有一個巨細為 k 的滑動窗口從數組的最左邊挪移到數組的最右邊。你只可以望到在滑動窗口 k 內的數字。滑動窗口每次只向右挪移一名。

返歸滑動窗口最大值。

示例:

輸出: nums = [1,3,-1,-3,5,3,6,7], 以及 k = 3
輸入: [3,3,5,5,6,7]

詮釋:

滑動窗口的地位                最大值
—————               —–
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

標題剖析

行使一個 雙端行列步隊,在行列步隊中存儲元素在數組中的地位, 而且維持行列步隊的嚴厲遞加,,也就說維持隊首元素是 最大的 ,當遍歷到一個新元素時, 若是行列步隊里有比當前元素小的,就將其移除行列步隊,以保障行列步隊的遞加。當行列步隊元素地位之差大于 k,就將隊首元素移除。

增補:甚么是雙端行列步隊(Dqueue)

Deque 的寄義是 “double ended queue”,即雙端行列步隊,它具備行列步隊以及棧的性子的數據布局。望文生義,它是一種前端與后端都支撐拔出以及刪除操作的539開獎結果行列步隊。

Deque 承繼自 Queue(行列步隊),它的間接完成有 ArrayDeque、LinkedList 等。

動畫描寫

代碼完成

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//有點坑,標題里都說了數組不為空,且 k > 0。然則望了一下,測試用例內里仍是有nums = [], k = 0,以是只好加上這個判定
if (nums == null || nums.length < k || k == 0) return new int[0];
int[] res = new int[nums.length – k + 1];
//雙端行列步隊
Deque<Integer> deque = new LinkedList<地下539公式>();
for (int i = 0; i < nums.length; i++) {
//在尾部增添元素,并保障左側元素都比尾部大
while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) {
deque.removeLast();
}
deque.addLast(i);
//在頭部移除元素
if (deque.getFirst() == i – k) {
deque.removeFirst();
}
//輸入效果
if (i >= k – 1) {
res[i – k + 1] = nums[deque.getFirst()];
}
}
return res;
}
}

2. 無反復字符的最宗子串

標題泉源于 LeetCode 上第 3 號成績:無反復字符的最宗子串。標題難度為 Medium,現在經由過程率為 29.0% 。

標題描寫

給定一個字符串,請你找出個中不含有反復字符的 最宗子串 的長度。

示例 1:

輸出: “大眾abcabcbb”大眾
輸入: 3
詮釋: 由于無反復字符的最宗子串是 “大眾abc”大眾,以是其長度為 3。
標題剖析
確立一個256位巨細的整型數組 freg ,用來確立字符以及其浮現地位之間的映照。

維護一個滑動窗口,窗口內的都是沒有反復的字符,往盡量的擴展窗口的巨細,窗口不絕的向右滑動。

(1)若是當前遍歷到的字符從未浮現過,那末間接擴展右側界;
(2)若是當前遍歷到的字符浮現過,則放大窗口(左側索引向右挪移),台湾六合彩然后持續察看當前遍歷到的字符;
(3)反復(1)(2),直到左側索引沒法再挪移;
(4)維護一個效果res,每次用浮現過的窗口巨細來更新效果 res,最初返歸 res 獵取效果。

動畫描寫

代碼完成

// 滑動窗口
// 時間龐大度: O(len(s))
// 空間龐大度: O(len(charset))
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int freq[256] = {0};
int l = 0, r = -1; //滑動窗口為s[l…r]
int res = 0;
// 整個輪回從 l == 0; r == -1 這個空窗口最先
// 到l == s.size(); r == s.size()-1 這個空窗口截止
// 在每次輪回里逐漸改變窗口, 維護freq, 并記載當前窗口中是否找到了一個新的最優值
while(l < s.size()){
if(r + 1 < s.size() && freq[s[r+1]] == 0){
r++;
freq[s[r]]++;
}else { //r已經經到頭 || freq[s[r+1]] == 1
freq[s[地下六合彩玩法l]]–;
l++;
}
res = max(res, r-l+1);
}
return res;
}
};

3. 存在反復元素 II

標題泉源于 LeetCode 上第 219 號成績:六合彩規則存在反復元素 II。標題難度為 Easy,現在經由過程率為 33.9% 。

標題描寫

給定一個整數數組以及一個整數 k,判定數組中是否存在兩個不同的索引 i 以及 j,使得 nums [i] = nums [j],而且 i 以及 j 的差的盡對值最大為 k。

示例 1:

輸出: nums = [1,2,3,1], k = 3
輸入: true

示例 2:

輸出: nums = [1,0,1,1], k = 1
輸入: true

示例 3:

輸出: nums = [1,2,3,1,2,3], k = 2
輸入: false

標題剖析

使用用滑動窗口與查找表來辦理。

配置查找表record,用來保管每次遍歷時拔出的元素,record的最大長度為k

遍歷數組nums,每次遍歷的時辰在record查找是否存在雷同的元素,若是存在則返歸true,遍歷收場

若是這次遍歷在record未查找到,則將該元素拔出到record中,爾后查望record的長度是否為k + 1

若是此時record的長度是否為k + 1,則刪減record的元素,該元素的值為nums[i – k]

若是遍歷完備個數組nums未查找到則返歸false

代碼完成

【免責聲明】本站內容轉載自互聯網,其相關談吐僅代表作者小我私家概念盡非權勢巨子,不代表本站態度。如您發明內容存在版權成績,請提交相關鏈接至郵箱:,咱們將實時予以處置。