933.最近的請求次數
- 有新請求就入隊，3000ms前發出的請求出隊
- 隊列的長度就是最近請求次數
/** 時間複雜度：O(n) while循環體 n為踢出對的請求個數
* 空間複雜度：O(n) 定義了一個數組，n為隊列的長度
*/
var RecentCounter = function() {
this.q = []
};
RecentCounter.prototype.ping = function(t) {
// 新請求入隊
this.q.push(t)
// 把不在時間範圍内的老請求出隊
while(this.q[0]<t-3000){
this.q.shift()
}
return this.q.length
};
資料流中的第K大元素
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
思路：
方法1：儲存前K個最大的值；全部排序
方法2：優先隊列，每次把最大的放在最上面，或把最小的放在最上面
小頂堆：把最小的放根結點，是以要保證元素個數等于K（意思是這個堆的個數為K個，最頂的是最小的，周遊數組的元素，如果有比它小的就不用進來排隊了，如果比它大，就把最小的踢掉，剩下的元素重新調整log2^k）
239.滑動視窗最大值
輸入: 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
所有的滑動視窗題用隊列去處理
- 方法1：暴力求解，枚舉視窗的起點位置，起點開始到len-k的最大值，寫兩個嵌套循環O(n*K)
const maxSlidingWindow = function (nums, k) {
const len = nums.length
const res = []
let left = 0, right = k-1
// 當數組沒有被周遊完時，執行循環體内的邏輯
while(right < len){
const max = calMax(nums, left, right)
res.push(max)
// 左右指針前進一步
left++
right++
}
return res
}
function calMax(arr, left, right){
if (!arr || !arr.length) return
// 初始化為第一個元素
let maxNum = arr[left]
for(let i = left; i<=right; i++){
// 誰比我大，我就變成誰
if(arr[i] > maxNum) maxNum = arr[i]
}
return maxNum
}
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
上述通過周遊來更新最大值産生了K
-
方法2：線性隊列，O(n+k)即O(n)一次解決
1）設定一個雙端隊列，存儲nums的下标
2）周遊每個元素，拿元素跟雙端隊列裡的隊尾做比較（雙端隊列：比我小的都踢出去）
目前元素小于隊尾，就直接入隊，否則，将隊尾元素逐個出隊，直到隊尾元素大于等于目前元素為止（比如，視窗移到2 3 4位置，5進來的時候，要跟視窗其他數對比，隻要比5小，都可以從這個棧彈出）
3）檢查隊頭元素，看隊頭元素是否已經被排除在滑動視窗的範圍之外了（即隊頭小于i-k）。如果是，則将隊頭元素出隊
4）判斷滑動視窗狀态，被周遊的元素個數小于K，表示還不能動結果數組，隻能繼續更新隊列；如果大于等于k，表示最大值已經出現，隊頭元素就是最大值
const maxSlidingWindow = function (nums, k) {
// 緩存數組的長度
const len = nums.length;
// 初始化結果數組
const res = [];
// 初始化雙端隊列
const deque = [];
// 開始周遊數組
for (let i = 0; i < len; i++) {
// 當隊尾元素小于目前元素時
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
// 将隊尾元素（索引）不斷出隊，直至隊尾元素大于等于目前元素
deque.pop();
}
// 入隊目前元素索引（注意是索引）
deque.push(i);
// 當隊頭元素的索引已經被排除在滑動視窗之外時
while (deque.length && deque[0] <= i - k) {
// 将隊頭元素索引出隊
deque.shift();
}
// 判斷滑動視窗的狀态，隻有在被周遊的元素個數大于 k 的時候，才更新結果數組
if (i >= k - 1) {
res.push(nums[deque[0]]);
}
}
// 傳回結果數組
return res;
}
設計循環隊列
循環隊列是一種線性資料結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接配接在隊首之後以形成一個循環。它也被稱為“環形緩沖器”
循環隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列裡，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環隊列，我們能使用這些空間去存儲新的值。
循環隊列可以高效利用存儲空間，普通隊列需要很大的存儲空間，存儲空間會往上跑，循環隊列可以避免這個問題。
你的實作應該支援如下操作：
MyCircularQueue(k): 構造器，設定隊列長度為 k 。
Front: 從隊首擷取元素。如果隊列為空，傳回 -1 。
Rear: 擷取隊尾元素。如果隊列為空，傳回 -1 。
enQueue(value): 向循環隊列插入一個元素。如果成功插入則傳回真。
deQueue(): 從循環隊列中删除一個元素。如果成功删除則傳回真。
isEmpty(): 檢查循環隊列是否為空。
isFull(): 檢查循環隊列是否已滿。
class MyCircularQueue{
constructor(k) {
// 用來儲存資料長度為k的資料結構
this.list = Array(k)
// 隊首指針
this.front = 0
// 隊尾的指針
this.rear = 0
// 隊列的長度
this.max = k
}
// 入隊：rear指針指向哪裡，哪裡就可以入隊，且rear指針+1
enQueue(num) {
if (this.isFull()) {
return false
} else {
this.list[this.rear] = num
// 指針向後移動
this.rear = (this.rear + 1) % this.max
return true
}
}
// 出隊：front指針指向誰，誰就出隊，且front指針+1
deQueue() {
let v = this.list[this.front]
this.list[this.front] = ''
console.log('front----->'+this.front)
// front指針往後移動
this.front = (this.front + 1) % this.max
console.log('front222----->'+this.front)
return v
}
isEmpty() {
return this.front === this.rear && !this.list[this.front]
}
isFull() {
return this.front === this.rear && !!this.list[this.front]
}
Front() {
return this.list[this.front]
}
rear() {
let rear = this.rear - 1
return this.list[rear < 0 ? this.max - 1 : rear]
}
}
const cQueue = new MyCircularQueue(5); // 設定長度為 3
cQueue.enQueue(1); // 傳回 true
cQueue.enQueue(2); // 傳回 true
cQueue.enQueue(3); // 傳回 true
cQueue.enQueue(4); // 傳回 false，隊列已滿
// cQueue.rear(); // 傳回 3
// cQueue.isFull(); // 傳回 true
cQueue.deQueue(); // 傳回 true
cQueue.deQueue(); // 傳回 true
cQueue.deQueue(); // 傳回 true
// cQueue.enQueue(4); // 傳回 true
// cQueue.rear(); // 傳回 4
console.log(cQueue)
任務排程器
給定一個用字元數組表示的 CPU 需要執行的任務清單。其中包含使用大寫的 A - Z 字母表示的26 種不同種類的任務。任務可以以任意順序執行，并且每個任務都可以在 1 個機關時間内執行完。CPU 在任何一個機關時間内都可以執行一個任務，或者在待命狀态。
然而，兩個相同種類的任務之間必須有長度為 n 的冷卻時間，是以至少有連續 n 個機關時間内 CPU 在執行不同的任務，或者在待命狀态。
你需要計算完成所有任務所需要的最短時間。
示例 ：
輸入：tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2
輸出：8
解釋：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
在本示例中，兩個相同類型任務之間必須間隔長度為 n = 2 的冷卻時間，而執行一個任務隻需要一個機關時間，是以中間出現了（待命）狀态。
思路：任務清單keys [‘A’,‘B’] 是用來周遊循環，拿到目前數量最多的任務，然後個push到臨時隊列tmp中，臨時隊列隻能放到n+1個（3個）任務，不夠放的就用’-'來補齊（做到兩個相同類型任務之間必須長度為n）。執行完一個臨時隊列tmp後，再循環判斷還有沒有任務清單keys，有的話繼續前面的動作，直到keys[0]=undefined為止
步驟：
1）先記錄每類任務的數量 Q:{A:3, B:3}
2）max記錄最多數量的先執行，先被push到臨時任務隊列tmp中，這個tmp就是AB-AB-AB（不夠n+1個的往裡面補"-"）
- 擷取任務清單keys（[‘A’,‘B’]），周遊任務清單找到數量最多的key，拿到數量最多的A先push到臨時隊列tmp中，表示執行這個隊列，是以得把Q中A的數量減一，從任務清單keys清除A
- 這個臨時隊列容量為n+1，是以能被循環小于n次，執行完一個臨時隊列後，把臨時隊列累加給p, 再去循環執行下一個臨時隊列
【前端算法系列】隊列queue
const leastInterval = (tasks, n) => {
// 表示最終隊列執行的結果
let q = ''
// 對歸類進行存儲
let Q = {}
tasks.forEach(item => {
if (Q[item]) {
Q[item]++
} else {
Q[item] = 1
}
});
// 隊列中還有任務就要循環，為什麼為1，是因為效率問題，不要一直判斷對象Q是否為空，會重複計算
while (1) {
// 處理邊界問題
// 任務清單：隻要有key值，表示任務隊列中還有，key值沒有就表示已經都處理掉了，就不用每次去判斷Q是否為空
let keys = Object.keys(Q)
if (!keys[0]) {
break
}
// 處理任務：找到哪個數量最多，數量最多的就優先處理
// 聲明一個隊列用來存儲1+n任務單元
let tmp = []
for (let i = 0; i <= n; i++) {
// 記錄最大值
let max=0
// 最大值名稱
let key
// 最大值索引位置
let pos
// 任務清單中找目前任務還剩下多少
keys.forEach((item, idx)=>{
// 找最大值
if(Q[item]>max){
max = Q[item]
key = item
pos = idx
// console.log(item)
// console.log(idx)
}
})
// 判斷是否找到最大值key，如果是就push到臨時隊列
if(key){
// console.log('11--->'+key)
tmp.push(key)
// 在任務清單中清除
keys.splice(pos, 1) // ["A", "B"] ===> ["B"]
Q[key]--
if(Q[key]<1){
delete Q[key]
}
// console.log('222--->'+keys)
}else{
break
}
}
// 如果不夠，後面補什麼
q +=tmp.join('').padEnd(n+1,'-')
}
// 邊界處理，最後不要出現冷卻時間
q = q.replace(/-+$/g, '')
return q.length
}
const tasks = ["A", "A", "A", "B", "B", "B"], n = 2
console.log(leastInterval(tasks, n))