Leetcode刷題學習筆記 – Queue

Introduction

  1. 設計一個circular queue
  2. 用queue來做BFS。通常是求最小的數量題目。
  3. 使用queue來達到輪流的效果

622. Design Circular Queue

設計circular queue。

  1. 定義每個變數的使用方法。
    head : 指向queue的第一個element。
    tail : 指向queue的最後一個element。
  2. FIFO從empty -> sz = 1，因為必須滿足(1)。所以head和tail必須指向同一個index，這邊是回到0。
  3. FIFO從sz = 1 -> empty，因為必須滿足(1)。所以head和tail必須回到-1。

























































class MyCircularQueue {
    vector<int> data;
    // 不要混用head和tail的定義，
    // head定義: 指向queue的第一個element, 如果queue沒element? 那就指向-1
    // tail定義: 指向queue的最後一個element, 如果queue沒element? 那就指向-1
    int head, tail, sz;
public:
    MyCircularQueue(int k) {
        data.resize(k);
        head = -1;
        tail = -1;
        sz = k;
    }
    
    bool enQueue(int value) {
        if(isFull()) return false;
        if(isEmpty()) // 因為fifo為空，所以head = tail = -1，則從idx 0 開始使用
            head = 0;
        
        tail = ((tail + 1) % sz);
        data[tail] = value;
    
        return true;
    }
    
    bool deQueue() {
        if(isEmpty()) return false;
        if(head == tail) {// 最後一個element, 把head, tail還原成-1
            head = -1;
            tail = -1;
        } else{
            head++;
            head %= sz;
        }
        return true;
    }
    
    int Front() {
        if(isEmpty()) return -1;
        return data[head];
    }
    
    int Rear() {
        if(isEmpty()) return -1;
        return data[tail];
    }
    
    bool isEmpty() {
        return head == -1;
    }
    
    bool isFull() {
        return head == (tail + 1) % sz;
    }
};

279. Perfect Squares

perfect squares : 是指那些1(\(1^2\)), 4(\(2^2\)), 9(\(3^2\))這些數。
這題是給你一個n，求出最少數量的perfect suqare和。
例如 : n = 12 = 4 + 4 + 4，則回傳3。






















int numSquares(int n) {
    if(n == 1) return 1;
    queue<int> q;
    q.push(n); // 目標放進queue
    int rtn = 0;
    while(!q.empty()) {
        for(int loop = q.size(); loop > 0; --loop) {
            int cur = q.front(); q.pop();
            // 減掉從小到大的perfect square
            for(int i = 1; i * i <= cur; ++i) {
                int next = cur - i * i; 
                // 如果達到0就返回
                if(next == 0) return rtn + 1; 
                // 否則就把下一個數字推進去
                q.push(next);
            }
        }
        rtn++;
    }
    return rtn;
}

752. Open the Lock

給你一個數字鎖從"0000"開始，還有一些deadends數字，如果轉到deadends數字，鎖就動不了了。所以要避開deadends數字，求出最少的轉動次數，可以把數字鎖轉到target數字。






























int openLock(vector<string>& deadends, string target) {    
    unordered_set<string> deadlock(deadends.begin(), deadends.end());
    // special case
    if (deadlock.count("0000")) return -1;
    if (target == "0000") return 0;
    int res = 0;
    // 紀錄訪問過的數字
    unordered_set<string> visited{{"0000"}};
    queue<string> q{{"0000"}};
    while (!q.empty()) {
        ++res;
        for (int k = q.size(); k > 0; --k) {
            auto t = q.front(); q.pop();
            for (int i = 0; i < t.size(); ++i) {
                // 把第i個數字向上向下旋轉
                for (int j = -1; j <= 1; ++j) {
                    if (j == 0) continue;
                    string str = t;
                    str[i] = ((t[i] - '0') + 10 + j) % 10 + '0';
                    if (str == target) return res;
                    //沒訪問過，也不是deadend數字，就加入queue
                    if (!visited.count(str) && !deadlock.count(str)) q.push(str);        
                    visited.insert(str);
                }
            }
        }
    }
    return -1;
}

281. Zigzag Iterator

給你兩個vector<int> v1和v2，設計一個class iterator，可以輪流取v1和v2的值出來。

  1. 使用queue來達到輪流的效果，取第一個之後，如果還沒取完就排到最後去。達到輪流的效果。
  2. queue只存每個vector的iterator，這樣就不用複製整個vector進來。
  3. 以前都習慣用index來存取vector其實用iterator會更好用。因為iterator類似pointer，不需要像index還需要知道本體在哪裡。


















class ZigzagIterator {
    queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        if(!v1.empty()) q.push({v1.begin(), v1.end()});
        if(!v2.empty()) q.push({v2.begin(), v2.end()});
    }

    int next() {
        auto [b, e] = q.front(); q.pop();
        if(b + 1 != e) q.push({b + 1, e});
        return *b;
    }

    bool hasNext() {
        return !q.empty();
    }
};
tags: leetcode 刷題
Select a repo