# Queue & Stack

###### tags: `LeetCode筆記`

## :memo: 一、Queue

## Enqueue

## Dequeue

* process the elements in order, using a queue might be a good choice.
* C++, Java provides built-in Queue library

## :memo: 二、Circular Queue 變數假設
* 如果Queue從0開始放東西:
* front,rear要設為-1
* size要給k
* 如果Queue從1開始放東西:
* front,rear要設為0
* size要給k+1

## :memo: 三、Circular Queue Implement C
### 結構

typedef struct {
    int* buffer;
    int size;
    int front;
    int rear;
} MyCircularQueue;

### Initialization

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* ringbuffer = (MyCircularQueue*) malloc(sizeof(MyCircularQueue));
    ringbuffer->buffer = (int*) malloc(sizeof(int) * (k + 1));   //key-point : k要加1 
    ringbuffer->size = k + 1;  //key-point : k要加1
    ringbuffer->front = 0; //因為1才開始,0沒放
    ringbuffer->rear = 0;  //因為1才開始,0沒放
    
    return ringbuffer;
}

### Enqueue

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    
    obj->rear = (obj->rear + 1) % obj->size;
    obj->buffer[obj->rear] = value;  
    
    return true;
}

### Dequeue

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    
    obj->front = (obj->front + 1) % obj->size;
    
    return true;
}

### 回傳Front的值

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1; 
    }
    
    return obj->buffer[(obj->front + 1) % obj->size];
}

### 回傳Rear的值

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1; 
    }

    return obj->buffer[obj->rear % obj->size];
}

### 檢查Circular Queue是否為空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if (obj->front == obj->rear)
    {
        return true;
    }

    return false;
}

### 檢查Circular Queue是否為滿

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if ((obj->rear + 1) % obj->size == obj->front)
    {
        return true;
    }
    
    return false;
}

### 釋放

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->buffer);
    free(obj);
}

## :memo: 四、Circular Queue Implement C++

class MyCircularQueue {
public:
    int *data;
    int head;
    int tail;
    int size;    
    MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }
    
    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            head = 0;
        }
        
        tail = (tail + 1) % size;
        
        data[tail] = value;
        
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        
        if (head == tail) {
            head = tail = -1;
        }
        else {
            head = (head + 1) % size;
        }
        
        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 ((tail + 1) % size) == head;
    }    
};

## :memo: 五、Queue - Usage

1. Initialize a queue.
**queue<int\> q;**
2. Push new element.
**q.push(5);**
3. Check if queue is empty.
**q.empty()**
4. Pop an element.
**q.pop();**
5. Get the first element.
**q.front();**
6. Get the last element.
**q.back();**
7. Get the size of the queue.
**q.size()**

## :memo: Moving Average from Data Stream (Easy)
**Input:**
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
**Output:**
[null, 1.0, 5.5, 4.66667, 6.0]

**Explanation**
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

### 作法
用全域變數去存sum比較快

class MovingAverage {
public:
    queue<int> q;
    int averageSize;
    double sum;
    
    MovingAverage(int size) {
        averageSize = size;
        sum = 0;
    }
    
    double next(int val) {
        sum += val;
        q.push(val);
        
        int queueSize = (int)q.size();
        
        if (queueSize <= averageSize) {
            return sum / queueSize;
        }
        else {
            sum -= q.front();
            q.pop();
            
            return sum / averageSize;
        }
    }
};

## :memo: 六、Queue and BFS
We can use **BFS** to find a path, especially **the shortest path**, from a start node to a target node.

We can use **BFS**, in even more abstract scenarios, to **traverse all the possible statuses**. In this case, we can regard the statuses as the nodes in the graph while the legal transition paths as the edges in the graph.

1. It is important to make sure that we **never visit a node twice**.
2. Otherwise, we might get stuck in an infinite loop, e.g. in graph **with cycle**.
3. If so, we can add a hash set **"visited"** to the code above to solve this problem.
4. There are some cases where one does **not need** keep the visited hash set:

You are absolutely sure there is no cycle, for example, in tree traversal.
You do want to add the node to the queue multiple times.

## :memo: 七、BFS - Template
**find the shortest path** or **do traversal**

### Template I

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
        step = step + 1;
    }
    return -1;          // there is no path from root to target
}

### Template II
make sure that we **never visit a node twice**
用**hashset(visited**)去檢查圖形有迴圈cycle

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> visited;  // store all the nodes that we've visited
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    add root to visited;
    // BFS
    while (queue is not empty) {
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in visited) {
                    add next to queue;
                    add next to visited;
                }
            }
            remove the first node from queue;
        }
        step = step + 1;
    }
    return -1;          // there is no path from root to target
}

## :memo: *Walls and Gates (Medium)


### 作法 BFS C++

class Solution {
public:
    #define EMPTYROOM INT_MAX
    #define GATE 0
    #define WALL -1
    // Right , Down, Left, Up
    vector<vector<int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.size() == 0 || rooms[0].size() == 0) {
            return;
        }
        
        queue<pair<int, int>> q;
        for (int row = 0; row < rooms.size(); row++) {
            for (int col = 0; col < rooms[0].size(); col++) {
                if (rooms[row][col] == GATE) {
                    q.push(make_pair(row, col));
                }
            }
        }
        
        while (!q.empty()) {
            pair<int ,int> curCell = q.front();
            q.pop();
            int curRow = curCell.first;
            int curCol = curCell.second;
            
            for (int d = 0; d < DIRECTIONS.size(); d++) {
                int nextRow = curRow + DIRECTIONS[d][0];
                int nextCol = curCol + DIRECTIONS[d][1];
                
                if (nextRow < 0 
                || nextRow >= rooms.size() 
                || nextCol < 0 
                || nextCol >= rooms[0].size() 
                || rooms[nextRow][nextCol] == WALL 
                || rooms[nextRow][nextCol] != EMPTYROOM) {
                    continue;
                }
                
                rooms[nextRow][nextCol] = rooms[curRow][curCol] + 1;
                q.push(make_pair(nextRow, nextCol));
            }
        }
    }
};

### 作法 DFS C
從大門(0)開始，因為有一個條件是遇到另一個大門(0)要return，所以一開始不能丟traverse(...,i,j,...)，要直接從大門4個方向的格子去traverse，traverse function一開始設回傳條件:
1.超出範圍
2.遇到牆(-1)
3.遇到另一個大門(0)
**4.這個格子有一個與其他大門較短的距離**
接著: 當dist小於當前格子擁有距離或還沒有距離就設為dist
最後一步: 往上下左右遞迴

void traverse(int** rooms, int row, int col, int dist, int m, int n){
    if (row < 0 || col < 0 || row >= m || col >= n)
    {
        return;
    }
    if (rooms[row][col] == -1)
    {
        return;
    }
    if (rooms[row][col] == 0)
    {
        return;
    }
    if (rooms[row][col] <= dist)
    {
        return;
    }
    if (rooms[row][col] > dist || rooms[row][col] == INT_MAX)
    {
        rooms[row][col] = dist;    
    }    

    traverse(rooms, row - 1,col, dist + 1, m, n);
    traverse(rooms, row + 1,col, dist + 1, m, n);
    traverse(rooms, row, col - 1, dist + 1, m, n);
    traverse(rooms, row, col + 1, dist + 1, m, n);   
}

void wallsAndGates(int** rooms, int roomsSize, int* roomsColSize){
    int dist = 1;
    
    for (int i = 0; i < roomsSize; i++)
    {
        for (int j = 0; j < *roomsColSize; j++)
        {
            if (rooms[i][j] == 0)
            {
                traverse(rooms, i + 1, j, dist, roomsSize, *roomsColSize);
                traverse(rooms, i - 1, j, dist, roomsSize, *roomsColSize);
                traverse(rooms, i, j - 1, dist, roomsSize, *roomsColSize);
                traverse(rooms, i, j + 1, dist, roomsSize, *roomsColSize);
            }
        }
    }   
}

## :memo: *Number of Islands (Medium)

### 作法 BFS
**跟Walls and Gates不一樣**，這題因為要一直擴張找1所以while(!q.empty())是在nested-for裡面，並且變0標記為visited

class Solution {
public:    
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) {
            return 0;
        }
        int nc = grid[0].size();
        
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    grid[r][c] = '0';    //mark as visited
                    queue<pair<int, int>> neighbors;
                    neighbors.push({r, c});
                    while (!neighbors.empty()) {
                        auto rc = neighbors.front();
                        neighbors.pop();
                        int row = rc.first;
                        int col = rc.second;
                        if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                            neighbors.push({row - 1, col});
                            grid[row - 1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row + 1][col] == '1') {
                            neighbors.push({row + 1, col});
                            grid[row + 1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                            neighbors.push({row, col - 1});
                            grid[row][col - 1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col + 1] == '1') {
                            neighbors.push({row, col + 1});
                            grid[row][col + 1] = '0';
                        }
                    }
                }
            }
        }
        
        return num_islands;
    }
};

## :memo: Open the Lock (Medium)

### 作法 C
題目意思是要找到從"目標數字組合"轉到"0000"的最少次數，這一題雖然看起來很難，也自己寫不出來，但是在看完範例後，做法就是把deadends的數字的visited先設為1，然後從"0000"，分往上旋轉+1和往下旋轉-1，從個位數到千位數，每一個位數做這兩種拜訪，拜訪完後該數字組合的hop要加1，主要code如下:

while (is_empty() != 1)
{
    if (hop[target_int] != -1)
    {
        return hop[target_int];
    }
    current_wheel = dequeue();
    current_wheel_int = convert_wheels_to_int(current_wheel);

    //Find the possible neighbors and enqueue

    for (int i = 0; i < 4; i++)
    {
        memcpy(&neighbor[0], current_wheel, sizeof(char) * 4);
        //INC
        if (neighbor[i] == '9')
        {
            neighbor[i] = '0';
        }
        else
        {
            neighbor[i] = neighbor[i] + 1;
        }

        if (visited[convert_wheels_to_int(neighbor)] == 0)
        {
            enqueue(neighbor);
            hop[convert_wheels_to_int(neighbor)] = hop[current_wheel_int] + 1;
            visited[convert_wheels_to_int(neighbor)] = 1;               
        }

        memcpy(&neighbor[0], current_wheel, sizeof(char)*4);
        //DEC
        if (neighbor[i] == '0')
        {
            neighbor[i] = '9';
        }
        else
        {
            neighbor[i] = neighbor[i] - 1;
        }
        if(visited[convert_wheels_to_int(neighbor)]==0)
        {
            enqueue(neighbor);
            hop[convert_wheels_to_int(neighbor)] = hop[current_wheel_int] + 1;
            visited[convert_wheels_to_int(neighbor)] = 1;
        }
    }
}

return hop[target_int]; 

### 作法 one directional BFS 慢 C++

class Solution {
public:
    vector<string> nbrStrs(string key) {    // return 8 nodes
        vector<string> res;
        for (int i = 0; i < 4; i++) {
            string tmp = key;
            tmp[i] = (key[i] - '0' + 1) % 10 + '0';
            res.push_back(tmp);
            tmp[i] = (key[i] - '0' - 1 + 10) % 10 + '0';
            res.push_back(tmp);
        }
        return res;
    }
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dds(deadends.begin(), deadends.end());
        unordered_set<string> visited;
        queue<string> bfs;
        string init = "0000";
        if (dds.find(init) != dds.end()) {
            return -1;
        }
        visited.insert("0000");
        bfs.push("0000");
        int res = 0;
        while (!bfs.empty()) {
            int sz = bfs.size();
            for (int i = 0; i < sz; i++) {
                string t = bfs.front();
                bfs.pop();
                if (t == target) {
                    return res;
                }
                vector<string> nbrs = nbrStrs(t);
                for (auto s : nbrs) {
                    if (dds.find(s) == dds.end() && visited.find(s) == visited.end()) {
                        bfs.push(s);
                        visited.insert(s);
                    }
                }
            }
            ++res;
        }
        
        return -1;
    }
};

### 作法 bidirectional BFS 快 C++

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {       
        //  bidirectional BFS
        int res = 0, trg = stoi(target);
        vector<bool> visited_s(10000, false), visited_e(10000, false);
        for (auto &s : deadends) {
            int n = stoi(s);
            visited_s[n] = visited_e[n] = true;            
        }
        if (visited_s[0]) return -1;
        if (trg == 0) return res;
        queue<int> q_s({0}), q_e({trg});
        visited_s[0] = true; visited_e[trg] = true;
        
        while (!q_s.empty() && !q_e.empty()) {
            if (q_e.size() < q_s.size()) {
                // 直接swap 整個queue 整個vector 
                swap(q_s, q_e);
                swap(visited_s, visited_e);
            }
            int fringe = q_s.size();   
            res++;
            while(fringe--) {
                int pass = q_s.front();
                q_s.pop();
                int n = pass;
                for (int i = 0; i < 4; i++) {
                    int diff = pow(10, i);
                    int d = n % 10;
                    n /= 10;
                    int inc = pass + (d == 9 ? -9 * diff : diff);
                    if (!visited_s[inc]) {
                        if (visited_e[inc]) return res;
                        visited_s[inc] = true;
                        q_s.push(inc);
                    }
                    int dec = pass + (d == 0 ? 9 * diff : -diff);
                    if (!visited_s[dec]) {
                        if (visited_e[dec]) return res;
                        visited_s[dec] = true;
                        q_s.push(dec);
                    }
                }
            }
        }
        return -1;
    }
};

## :memo: Perfect Squares (Medium)
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself.
For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.


### 作法 BFS C++

class Solution {
public:
    int numSquares(int n) {
        vector<int> square_nums;
        for (int i = 1; i * i <= n; i++) {
            square_nums.push_back(i * i);
        }
        
        queue<int> q;
        q.push(n);
        int level = 0;        
        while (!q.empty()) {            
            level++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int cur = q.front();
                q.pop();                
                for (int square : square_nums) {
                    if (cur == square) {
                        return level;
                    }
                    else if (cur < square) {
                        break;
                    }
                    else {
                        q.push(cur - square);
                    }
                }
            }                        
        }
        
        return level;
    }
};

### 作法 Brute-force Enumeration [Time Limit Exceeded] Python

class Solution(object):
    def numSquares(self, n):
        square_nums = [i**2 for i in range(1, int(math.sqrt(n))+1)]

        def minNumSquares(k):
            """ recursive solution """
            # bottom cases: find a square number
            if k in square_nums:
                return 1
            min_num = float('inf')

            # Find the minimal value among all possible solutions
            for square in square_nums:
                if k < square:
                    break
                new_num = minNumSquares(k-square) + 1
                min_num = min(min_num, new_num)
            return min_num

        return minNumSquares(n)

### 作法 Greedy Enumeration Java

class Solution {
    Set<Integer> square_nums = new HashSet<Integer>();

    protected boolean is_divided_by(int n, int count) {
        if (count == 1) {
            return square_nums.contains(n);
        }    

        for (Integer square : square_nums) {
            if (is_divided_by(n - square, count - 1)) {
                return true;
            }
        }
        
        return false;
    }

    public int numSquares(int n) {
        this.square_nums.clear();

        for (int i = 1; i * i <= n; ++i) {
            this.square_nums.add(i * i);
        }

        int count = 1;
        for (; count <= n; ++count) {
            if (is_divided_by(n, count))
                return count;
        }
        
        return count;
    }
}

### 作法 Dynamic Programming C
這一題用到Dynamic Programming，一開始temp內的數字都要設為最大值，程式如下:

int* temp = (int*) malloc(sizeof(int) * (n + 1));
memset(temp, 10000, sizeof(int)* (n + 1));    
    
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j * j <= i; j++)
    {
        temp[i] = temp[i] < temp[i - j * j] + 1 ? temp[i] : temp[i - j * j] + 1;
    }
}

return temp[n];

### 作法 Mathematics Java

class Solution {
    protected boolean isSquare(int n) {
        int sq = (int) Math.sqrt(n);
        
        return n == sq * sq;
    }

    public int numSquares(int n) {
        // four-square and three-square theorems.
        while (n % 4 == 0)
            n /= 4;
        if (n % 8 == 7)
            return 4;

        if (this.isSquare(n))
            return 1;
        // enumeration to check if the number can be decomposed into sum of two squares.
        for (int i = 1; i * i <= n; ++i) {
            if (this.isSquare(n - i * i))
                return 2;
        }
        // bottom case of three-square theorem.
        return 3;
    }
}

## :memo: Shortest Distance from All Buildings (Hard)


### 作法 BFS from Empty Land to All Houses

class Solution {
private:
    int bfs(vector<vector<int>>& grid, int row, int col, int totalHouses) {
        // Next four directions.
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        int rows = grid.size();
        int cols = grid[0].size();
        int distanceSum = 0;
        int housesReached = 0;

        // Queue to do a bfs, starting from (r,c) cell
        queue<pair<int, int>> q;
        q.push({ row, col });

        // Keep track of visited cells
        vector<vector<bool>> vis(rows, vector<bool> (cols, false));
        vis[row][col] = true;

        int steps = 0;

        while (!q.empty() && housesReached != totalHouses) {
            for (int i = q.size(); i > 0; --i) {
                auto curr = q.front();
                q.pop();

                row = curr.first;
                col = curr.second;

                // If this cell is a house, then add the distance from the source to this cell
                // and we go past from this cell.
                if (grid[row][col] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }

                // This cell was an empty cell, hence traverse the next cells which is not a blockage.
                for (auto& dir : dirs) {
                    int nextRow = row + dir[0];
                    int nextCol = col + dir[1];

                    if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols) {
                        if (!vis[nextRow][nextCol] && grid[nextRow][nextCol] != 2) {
                            vis[nextRow][nextCol] = true;
                            q.push({nextRow, nextCol});
                        }
                    }
                }
            }
            
            // After traversing one level cells, increment the steps by 1 to reach to next level.
            steps++;
        }

        // If we did not reach all houses, then any cell visited also cannot reach all houses.
        // Set all cells visted to 2 so we do not check them again and return INT_MAX.
        if (housesReached != totalHouses) {
            for (row = 0; row < rows; row++) {
                for (col = 0; col < cols; col++) {
                    if (grid[row][col] == 0 && vis[row][col]) {
                        grid[row][col] = 2;
                    }
                }
            }
            return INT_MAX;
        }
        // If we have reached all houses then return the total distance calculated.
        return distanceSum;
    }

public:
    int shortestDistance(vector<vector<int>>& grid) {
        int minDistance = INT_MAX;
        int rows = grid.size();
        int cols = grid[0].size();
        int totalHouses = 0;

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == 1) { 
                    totalHouses++;
                }
            }
        }

        // Find the min distance sum for each empty cell.
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == 0) {
                    minDistance = min(minDistance, bfs(grid, row, col, totalHouses));
                }
            }
        }

        // If it is impossible to reach all houses from any empty cell, then return -1.
        if (minDistance == INT_MAX) {
            return -1;
        }
        return minDistance;
    }
};

### 作法 BFS from Houses to Empty Land
When there are **fewer houses than empty lands**, then this approach will require less time than the previous approach and vice versa. While, on average, this approach is not an improvement on the previous approach, it will serve as a mental stepping stone to better understand the third approach.

class Solution {
private:
    void bfs(vector<vector<int>>& grid, vector<vector<vector<int>>>& distances, int row, int col) {
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        int rows = grid.size(), cols = grid[0].size();
        
        // Queue to do a bfs, starting from each cell located at (r,c).
        queue<pair<int, int>> q;
        q.push({ row, col });
        
        // Keep track of visited cells.
        vector<vector<bool>> vis (rows, vector<bool>(cols, false));
        vis[row][col] = true;
        
        int steps = 0;
        
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto curr = q.front();
                q.pop();
                row = curr.first;
                col = curr.second;
                
                // If we reached an empty cell, then add the distance
                // and increment the count of houses reached at this cell.
                if (grid[row][col] == 0) {
                    distances[row][col][0] += steps;
                    distances[row][col][1] += 1;
                }
                
                // Traverse the next cells which is not a blockage.
                for (auto& dir : dirs) {
                    int nextRow = row + dir[0];
                    int nextCol = col + dir[1];
                    if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols) {
                        if (!vis[nextRow][nextCol] && grid[nextRow][nextCol] == 0) {
                            vis[nextRow][nextCol] = true;
                            q.push({ nextRow, nextCol });
                        }
                    }
                }
            }
            
            // After traversing one level cells, increment the steps by 1.
            steps++;
        }
    }
    
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int minDistance = INT_MAX;
        int rows = grid.size();
        int cols = grid[0].size();
        int totalHouses = 0;
        
        // Store { total_dist, houses_count } for each cell.
        vector<vector<vector<int>>> distances (rows, vector<vector<int>> (cols, {0, 0}));
        
        // Count houses and start bfs from each house.
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == 1) {
                    totalHouses++;
                    bfs(grid, distances, row, col);
                }
            }
        }
        
        // Check all empty lands with houses count equal to total houses and find the min ans.
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (distances[row][col][1] == totalHouses) {
                    minDistance = min(minDistance, distances[row][col][0]);
                }
            }
        }
        
        // If we haven't found a valid cell return -1.
        if (minDistance == INT_MAX) {
            return -1;
        }
        return minDistance;
    }
};

### 作法 BFS from Houses to Empty Land (Optimized)
If there was an empty land cell that was not reachable in the previous iteration, then its value has not been decreased, hence we will not insert that cell in the queue when we start a BFS from another house cell.
Therefore, this approach prunes many iterations and saves some time since we are not creating a new matrix to track visited cells for each BFS call.

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        // Next four directions.
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        int rows = grid.size();
        int cols = grid[0].size();
        
        // Total Mtrix to store total distance sum for each empty cell.
        vector<vector<int>> total(rows, vector<int> (cols, 0));

        int emptyLandValue = 0;
        int minDist = INT_MAX;

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {

                // Start a bfs from each house.
                if (grid[row][col] == 1) {
                    minDist = INT_MAX;

                    // Use a queue to perform a BFS, starting from the cell located at (row, col).
                    queue<pair<int, int>> q;
                    q.push({ row, col });
                    
                    int steps = 0;

                    while (!q.empty()) {
                        steps++;

                        for (int level = q.size(); level > 0; --level) {
                            auto curr = q.front();
                            q.pop();

                            for (auto& dir : dirs) {
                                int nextRow = curr.first + dir[0];
                                int nextCol = curr.second + dir[1];

                                // For each cell with the value equal to empty land value
                                // add distance and decrement the cell value by 1.
                                if (nextRow >= 0 && nextRow < rows &&
                                    nextCol >= 0 && nextCol < cols &&
                                    grid[nextRow][nextCol] == emptyLandValue) {
                                    grid[nextRow][nextCol]--;
                                    total[nextRow][nextCol] += steps;

                                    q.push({ nextRow, nextCol });
                                    minDist = min(minDist, total[nextRow][nextCol]);
                                }
                            }
                        }
                    }

                    // Decrement empty land value to be searched in next iteration.
                    emptyLandValue--;
                }
            }
        }

        return minDist == INT_MAX ? -1 : minDist;
    }
};

## :memo: 八、Stack

## Push

## Pop

## :memo: 九、Stack Implement C
### 結構

#define Size 30000

typedef struct {
    int* stack;
    int top;
} Stack;

### Initialization

Stack* minStackCreate()
{

    Stack* stack = (Stack*) malloc(sizeof(Stack));
    stack->stack = (int*) malloc(sizeof(int) * Size);
    stack->top = 0;
    
    return stack;
}

### Push

void Push(Stack* obj, int val)
{
    if (obj->top < Size)
    {
        obj->stack[obj->top] = val;
        obj->top++;
    }
}

### Pop

void Pop(Stack* obj)
{
    if (obj->top != 0)
    { 
        obj->top--;
    }
}

### 回傳頂部值

int Top(Stack* obj)
{
    return obj->stack[(obj->top) - 1];  // 原本的obj->top數值是真Top+1，所以要-1才是真Top
}

### 釋放

void Free(Stack* obj)
{
    free(obj->stack);
    free(obj);
}

## :memo: 十、Stack Implement with vector C++

#include <iostream>

class MyStack {
    private:
        vector<int> data;  // store elements
    public:
        /** Insert an element into the stack. */
        void push(int x) {
            data.push_back(x);
        }
        /** Checks whether the queue is empty or not. */
        bool isEmpty() {
            return data.empty();
        }
        /** Get the top item from the queue. */
        int top() {
            return data.back();
        }
        /** Delete an element from the queue. 
            Return true if the operation is successful. */
        bool pop() {
            if (isEmpty()) {
                return false;
            }
            data.pop_back();
            return true;
        }
};

int main() {
    MyStack s;
    s.push(1);
    s.push(2);
    s.push(3);
    for (int i = 0; i < 4; ++i) {
        if (!s.isEmpty()) {
            cout << s.top() << endl;
        }
        cout << (s.pop() ? "true" : "false") << endl;
    }
}

## :memo: 十一、Stack - Usage
1. Initialize a stack.
**stack<int\> s;**
2. Push new element.
**s.push(5);**
3. Check if stack is empty.
**s.empty()**
4. Pop an element.
**s.pop();**
5. Get the top element.
**s.top()**
6. Get the size of the stack.
**s.size()**

## :memo: *Valid Parentheses (Easy)
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
1 Open brackets must be closed by the same type of brackets.
2 Open brackets must be closed in the correct order.
3 Every close bracket has a corresponding open bracket of the same type.


### 作法
用stack去檢查三種左括號在top的情形

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        
        for (int i = 0; i < s.length(); i++) {
            if (st.empty()) {
                st.push(s[i]);    
            }
            else {
                if (st.top() == '(') {
                    if (s[i] == ']') {
                        return false;
                    }
                    else if (s[i] == '}') {
                        return false;
                    }
                    else if (s[i] == ')') {
                        st.pop();
                    }
                    else {
                        st.push(s[i]);
                    }
                }
                else if (st.top() == '[') {
                    if (s[i] == ']') {
                        st.pop();
                    }
                    else if (s[i] == '}') {
                        return false;
                    }
                    else if (s[i] == ')') {
                        return false;
                    }
                    else {
                        st.push(s[i]);
                    }
                }
                else if (st.top() == '{') {
                    if (s[i] == ']') {
                        return false;
                    }
                    else if (s[i] == '}') {
                        st.pop();
                    }
                    else if (s[i] == ')') {
                        return false;
                    }
                    else {
                        st.push(s[i]);
                    }
                }
            }
        }
        
        if (st.empty()) {
            return true;
        }
        
        return false;
    }
};

## :memo: Min Stack (Medium)

### 作法
data.back(); 回傳最後一個元素的值
data.pop_back(); 吐最後一個元素
pop()時要注意是否吐到最小值

class MinStack {
private:
    vector<int> data;
    int Min = INT_MAX;
public:    
    MinStack() {
        
    }
    
    void push(int val) {
        data.push_back(val);
        Min = min(Min, val);
    }
    
    void pop() {
        if (data.size() == 0) {
            return;
        }
        if (data.back() == Min) {
            Min = INT_MAX;
            for (int i = 0; i < data.size() - 1; i++) {
                Min = min(Min, data[i]);
            }
        }
        
        data.pop_back();
    }
    
    int top() {
        return data.back();
    }
    
    int getMin() {
        return Min;
    }
};

### 作法 MinHeap and Hashmap

class MinStack {
public:
    stack<int> st;  // Stack to store elements
    priority_queue<int, vector<int>, greater<int>> pq;  // Hash map to keep track of element counts
    unordered_map<int, int> mp;  // Min heap to get the minimum element
    MinStack() {
        // Constructor to initialize the stack and data structures.
    }
    
    void push(int val) {
        st.push(val);       // Push the value onto the stack.
        pq.push(val);       // Push the value onto the min heap.     
        mp[val]++;          // Increment the count of the value in the hash map.
    }
    
    void pop() {
        mp[st.top()]--;     // Decrement the count of the top element.
        st.pop();           // Pop the top element from the stack.
    }
    
    int top() {
        return st.top();    // Return the top element of the stack.
    }
    
    int getMin() {
        while (mp[pq.top()] == 0) {
            pq.pop();       // Remove elements from the min heap that have zero count.
        }

        return pq.top();    // Return the top element of the min heap, which is the minimum element.
    }
};

## :memo: *Daily Temperatures (Medium)

### 作法
**while 迴圈**
這一題要記錄離每一天溫度的下一次高溫的最近日期差幾天，這一題stack裡面存的是**index**也就是**第i天**，這個是此問題的關鍵，
當遇到下一個高溫，結果陣列的第i天答案會=**當前i - stack的最頂部的index**，算完top-1，
如果沒遇到就把當前i放到stack頂部，res[i] = 0

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> s;
        vector<int> res(temperatures.size());
        int t = 0;
        
        for (int i = 0; i < temperatures.size(); i++) {
            while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
                int index = s.top();
                res[index] = i - index;
                s.pop();
            }
            s.push(i);
        }
        
        return res;
    }
};

## :memo: *Evaluate Reverse Polish Notation (Medium)

這一題要實作簡單的四則運算後序表示的計算，很簡單，遇到數字就往stack丟，遇到運算符號就去丟頂部前兩個去做該運算，算完丟回頂部，此問題遇到的運算符號順序，就是要運算的順序，最後回傳stack底部的值為答案
### 作法 C

int evalRPN(char ** tokens, int tokensSize) {
    int stack[10001];
    int top = 0;
    int temp = 0;
    
    memset(stack, -201, sizeof(stack));
    
    for (int i = 0; i < tokensSize; i++)
    {
        if (!strcmp(tokens[i], "+"))
        {
            temp = stack[top - 1] + stack[top];
            top--;
            stack[top] = temp;
            temp = 0;
        }
        else if (!strcmp(tokens[i], "-"))
        {
            temp = stack[top - 1] - stack[top];
            top--;
            stack[top] = temp;
            temp = 0;
        }
        else if (!strcmp(tokens[i], "*"))
        {
            temp = stack[top - 1] * stack[top];
            top--;
            stack[top] = temp;
            temp = 0;
        }
        else if (!strcmp(tokens[i], "/"))
        {
            temp = stack[top - 1] / stack[top];
            top--;
            stack[top] = temp;
            temp = 0;
        }
        else
        {
            top++;
            stack[top] = atoi(tokens[i]);
        }
    }
    
    return stack[1];
}

### 作法 C++

class Solution {
    
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (string s: tokens) {
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                long long a = st.top();
                st.pop();
                long long b = st.top();
                st.pop();
                if(s == "+") st.push(b + a);
                else if(s == "-") st.push(b - a);
                else if(s == "*") st.push(b * a);
                else st.push(b / a);
            }
            else st.push((int)stoi(s));
        }
        return st.top();
    }
};

## :memo: 十二、Stack and DFS

we can **use DFS** to do **pre-order**, **in-order** and **post-order** traversal.

**The first path you found in DFS is not always the shortest path.**

## :memo: 十三、DFS - Template
**tree traversal**

### Template I - Recursion

boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visited;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

### Template II - Iteration

boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> stack;
    add root to stack;
    while (stack is not empty) {
        Node cur = the top element in stack;
        remove the cur from the stack;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to visited;
                add next to stack;
            }
        }
    }
    return false;
}

## :memo: *Binary Tree Inorder Traversal (Easy)


### 作法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* curr = root;
        while (curr != nullptr || !s.empty()) {
            while (curr != nullptr) {
                s.push(curr);
                curr = curr->left;
            }
            curr = s.top();
            s.pop();
            res.push_back(curr->val);
            curr = curr->right;
        }
        
        return res;
    }
};

## :memo: *Number of Islands (Medium)

### 作法 DFS
這一題gris[r][c]=0代表拜訪過，跑4個方向的dfs

class Solution {    // DFS
private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();
        
        grid[r][c] = '0';
        if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();
        
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }
        
        return num_islands;
    }
};

## :memo: Clone Graph (Medium)


### 作法 C
這一題要利用dfs去複製一張圖，準備好struct Node* visited[size]後，**特別注意visited是struct Node**，去用dfs拜訪原圖，都是將clone的指標指向visited的指標

void dfs(struct Node* head, struct Node** visited,struct Node* s) {
    head->val = s->val;
    head->numNeighbors = s->numNeighbors;
    visited[s->val] = head;
    
    if (s->numNeighbors == 0)
    {
        return;
    }
    
    head->neighbors = (struct Node**) malloc(sizeof(struct Node*) * s->numNeighbors);
    for (int i = 0; i < s->numNeighbors; i++)
    {
        if (visited[s->neighbors[i]->val] == NULL)
        {
            head->neighbors[i] = (struct Node*)malloc(sizeof(struct Node));
            dfs(head->neighbors[i], visited, s->neighbors[i]);
        }
        else
        {
            head->neighbors[i] = visited[s->neighbors[i]->val];
        }
    }
}

struct Node *cloneGraph(struct Node *s) {
    if (s == NULL)
    {
        return NULL;
    }
    
    struct Node* clone = (struct Node*) malloc(sizeof(struct Node));
    struct Node* visited[101] = {NULL};
    
    dfs(clone, visited, s);
    
    return clone;
}

### 作法 C++

class Solution {
public:
    Node* dfs(Node* cur, unordered_map<Node*, Node*>& mp) {
        vector<Node*> neighbour;
        Node* clone = new Node(cur->val);
        mp[cur] = clone;
        for (auto it: cur->neighbors) {
            if (mp.find(it) != mp.end()) {
                neighbour.push_back(mp[it]);
            }
            else {
                neighbour.push_back(dfs(it, mp));
            }
        }
        clone->neighbors = neighbour;
        
        return clone;
    }
    Node* cloneGraph(Node* node) {
        unordered_map<Node*, Node*> mp;
        if (node == NULL) {
            return NULL;
        }
        if (node->neighbors.size() == 0) {
            Node* clone = new Node(node->val);
            return clone;
        }
        
        return dfs(node, mp);
    }
};

## :memo: Target Sum (Medium)

### 作法
這一題要用一個二維陣列memo以動態規劃去記錄已經算過的target的次數，並隨著i增加去將sum加nums[i]或減nums[i]，分別迭代執行add()及sub()，最後的回傳值會是:
(*memo)[i][sum+total] = add() + sub()

int calculate(int* nums, int numsSize, int i, int sum, int target, int*** memo,int total){
    if (i == numsSize)
    {
        if (sum == target)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        if((*memo)[i][sum+total]!=INT_MIN)
        {
            return (*memo)[i][sum+total];
        }
        int add = calculate(nums, numsSize, i + 1, sum + nums[i], target, memo, total);
        int substract = calculate(nums, numsSize, i + 1, sum - nums[i], target, memo, total);
        (*memo)[i][sum+total] = add + substract;
        
        return (*memo)[i][sum+total];
    }
}

int findTargetSumWays(int* nums, int numsSize, int target){
    int total = 0;    
    for (int i = 0; i < numsSize; i++)
    {
        total += nums[i];
    }    
    
    int** memo = (int**) malloc(sizeof(int*) * numsSize);
    for (int i = 0; i < numsSize; i++)
    {
        memo[i] = malloc(sizeof(int) * (2 * total + 1));
        for(int j = 0; j < 2 * total + 1; j++)
        {
            memo[i][j] = INT_MIN;
        }
    }    

    return calculate(nums, numsSize, 0, 0, target, &memo, total);
}

### 作法 DFS 非常慢 C++

class Solution {
private:
    int res=0;
public:
    void dfs(vector<int>& nums, int S, int index, int path) {
        if (index == nums.size() && path == S) {
            res++;
            return;
        }
        if (index >= nums.size()) {
            return;
        }
        
        dfs(nums, S, index + 1, path + nums[index]);
        dfs(nums, S, index + 1, path - nums[index]);
    }
    
    int findTargetSumWays(vector<int>& nums, int target) {
        int tol = accumulate(nums.begin(), nums.end(), 0);  // = 0 + nums加總
        
        if (tol < target) {
            return 0;
        } 
        
        dfs(nums, target, 0, 0);
        
        return res;
    }
};

## :memo: 十四、Implement Queue using Stacks (Easy)
**這個作法是自己寫的，不確定是否正統**

### 結構

typedef struct {
    int stack_A[101];
    int stack_B[101];
    int top_A;
    int top_B;    
} MyQueue;

### Initialization

MyQueue* myQueueCreate() {
    MyQueue* queue = (MyQueue*) malloc(sizeof(MyQueue));
    queue->top_A = 0;
    queue->top_B = 0;
    
    return queue;
}

### Push

void myQueuePush(MyQueue* obj, int x) {
    obj->top_A++;
    if obj->top_A <= 100)
    {
        obj->stack_A[obj->top_A] = x;    
    }    
}

### Pop

int myQueuePop(MyQueue* obj) {
    if (obj->top_B == 0)
    {
        for (int i = obj->top_A; i > 0; i--)
        {
            obj->stack_B[obj->top_A - (i - 1)] = obj->stack_A[i];
        }
        obj->top_B = obj->top_A;
        obj->top_A = 0;
    }
    obj->top_B--;
    
    return obj->stack_B[obj->top_B+1];
}

### 回傳Rear的值

int myQueuePeek(MyQueue* obj) {
    if (obj->top_B == 0)
    {
        for (int i = obj->top_A; i > 0; i--)
        {
            obj->stack_B[obj->top_A - (i - 1)] = obj->stack_A[i];
        }
        obj->top_B = obj->top_A;
        obj->top_A = 0;
    }
    
    return obj->stack_B[obj->top_B];
}

### 檢查Queue是否為空

bool myQueueEmpty(MyQueue* obj) {
    if (obj->top_A == 0 && obj->top_B == 0)
    {
        return true;
    }
  
    return false;
}

### 釋放

void myQueueFree(MyQueue* obj) {
    free(obj);
}

## :memo: 十五、Implement Stack using Queues (Easy)
**這個作法是自己寫的，不確定是否正統**



### 結構

typedef struct {
    int queue_A[101];
    int queue_B[101];
    int front_A;
    int tail_A;
    int front_B;
    int tail_B;
} MyStack;

### Initialization

MyStack* myStackCreate() {
    MyStack* stack = (MyStack*) malloc(sizeof(MyStack));
    stack->front_A = 0;
    stack->tail_A = 0;
    stack->front_B = 0;
    stack->tail_B = 0;
    
    return stack;
}

### Push

void myStackPush(MyStack* obj, int x) {
    if (obj->front_A <= 100)
    {
        obj->front_A++;
        obj->queue_A[obj->front_A] = x;
    }
}

### Pop

int myStackPop(MyStack* obj) {
    while (obj->tail_A != obj->front_A)
    {
        obj->queue_B[obj->front_B] = obj->queue_A[obj->tail_A];
        obj->front_B++;
        obj->tail_A++;
    }
    int ret = obj->queue_A[obj->tail_A];
    obj->front_B--;    
    obj->tail_A = 0;
    
    for (int i = 1; i <= obj->front_B; i++)
    {
        obj->queue_A[i] = obj->queue_B[i];
    }
    obj->front_A = obj->front_B;
    obj->front_B = 0;
    
    return ret;
}

### 回傳頂部值

int myStackTop(MyStack* obj) {
    return obj->queue_A[obj->front_A];
}

### 檢查Stack是否為空

bool myStackEmpty(MyStack* obj) {
    if (obj->front_A == obj->tail_A)
    {
        return true;
    }
    
    return false;
}

### 釋放

void myStackFree(MyStack* obj) {
    free(obj);
}

## :memo: *Flood Fill (Easy)

**Input:** image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
**Output:** [[2,2,2],[2,2,0],[2,0,1]]
**Explanation:** From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

### 作法
簡單的寫一個dfs副程式先判斷邊界和是否已染色後遞迴4個方向

class Solution {
public:
    void dfs(vector<vector<int>>& image, int row, int col, int color, int source) {
        if (row < 0 || row >= image.size() || col < 0 || col >= image[0].size() || image[row][col] == color) {
            return;
        }
        
        if (image[row][col] == source) {
            image[row][col] = color;
        }
        else {
            return;
        }
        
        dfs(image, row - 1, col, color, source);
        dfs(image, row + 1, col, color, source);
        dfs(image, row, col - 1, color, source);
        dfs(image, row, col + 1, color, source);
        
        return;
    }
    
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if (color == 0) {
            return image;
        }
        
        int source = image[sr][sc];
        dfs(image, sr, sc, color, source);
        
        return image;
    }
};

## :memo: Decode String (Medium)

### 作法 C++
用2個stack一個記數一個存文字，4種情形:
1.遇到數字*10加到Sum
2.遇到'\['將當前字串存到stack並將sum=0並將當前字串=""
3.遇到'\]'取出stack的Top=decodestring後，跑for迴圈大小為countStack.top()拼接當前字串到decodestring後，全部給當前字串
4.遇到英文字母，將英文字母加到當前字串

class Solution {
public:
    string decodeString(string s) {
        stack<int> countStack;
        stack<string> stringStack;
        string currentString;
        int Sum = 0;
        
        for (auto ch : s) {
            if (isdigit(ch)) {
                Sum = Sum * 10 + ch - '0';
            }
            else if (ch == '[') {
                countStack.push(Sum);
                stringStack.push(currentString);
                currentString = "";
                Sum = 0;
            }
            else if (ch == ']') {
                string decodedString = stringStack.top();
                stringStack.pop();
                
                for (int currentSum = countStack.top(); currentSum > 0; currentSum--) {
                    decodedString = decodedString + currentString;
                }
                
                countStack.pop();
                currentString = decodedString;
            }
            else {
                currentString = currentString + ch;
            }
        }
        
        return currentString;
    }
};

### 作法 C
這一題是用到Stack去完成，因為是C語言所以字串處理起來很繁瑣，不然概念上不算難，
簡單來說就是
遇到']'就要去從stack內pop出文字並拼接，直到pop出'['後結束拼接，
接著pop的數字計算數字當複製貼上幾次，
然後檢查stack是否為空，
不是就將拼完的字串反轉後丟回stack，之後繼續讀下一個s[i]，
stack為空就反轉字串拼貼在final後，之後繼續讀下一個s[i]，直到讀完s。
沒遇到']'就都push到stack內。
整個讀完s後再將最後一個temp反轉接在final後，最後回傳final為答案。

struct stack {
    int top;
    int capacity;
    char* arr;
};

struct stack* createStack(int capacity) {
    struct stack* stack = (struct stack*) malloc(sizeof(struct stack));
    stack->top = -1;
    stack->capacity = capacity;
    stack->arr = (char*) malloc(sizeof(char) * capacity);
    
    return stack;
}

bool isEmpty(struct stack* stack) {
    return stack->top==-1 ? true : false;
}

bool isFull(struct stack* stack){
    return stack->top == stack->capacity - 1 ? true : false;
}

void push(struct stack* stack, char a) {
    if (isFull(stack))
    {
        return;
    }
    stack->arr[++stack->top] = a;
}

char pop(struct stack* stack) {
    if (isEmpty(stack))
    {
        return '\0';
    }
    int ch = stack->arr[stack->top--];
    
    return ch;
}

void printStack(struct stack* stack) {
    if (stack->top == -1)
    {
        printf("stack empty\n");
    }
    for (int i = 0; i <= stack->top; i++)
    {
        printf("%c ", stack->arr[i]);
    }
    printf("\n");
}

void revstr(char* str1) {
    int i,len,temp;
    len = strlen(str1);
    
    for (i = 0; i < len / 2; i++)
    {
        temp = str1[i];
        str1[i] = str1[len - i - 1];
        str1[len - i - 1] = temp;
    }
}

char * decodeString(char * s) {
    int size = strlen(s);
    int capacity = 300*30;
    struct stack* stack = createStack(capacity);
    
    char* final = (char*) malloc(sizeof(char) * capacity);
    char* temp = (char*) malloc(sizeof(char) * capacity);
    memset(final, 0, sizeof(capacity));
    memset(temp, 0, sizeof(capacity));
    
    for (int i = 0; i < size; i++)
    {
        char curr = s[i];
        int times = 0;
        int idx = 1;
        if (curr == ']')
        {
            char ch = pop(stack);
            while (ch >= 'a' && ch <= 'z')
            {
                strncat(temp, &ch, 1);
                ch = pop(stack);
            }
            if (ch == '[')
            {
                ch = pop(stack);
            }
            while (ch >= '0' && ch <= '9')
            {
                times = times + (ch - '0') * idx;
                ch = pop(stack);
                idx = idx * 10;
            }
            
            if (times == 0)
            {
                times = 1;
            }
            
            if (!isEmpty(stack))
            {
                push(stack, ch);
                revstr(temp);
                
                for (int i = 0; i < times; i++)
                {
                    for (int j = 0; j < strlen(temp); j++)
                    {
                        push(stack, temp[j]);
                    }
                }
                memset(temp, 0, sizeof(capacity));
                continue;
            }            
            
            revstr(temp);
            
            for (int i = 0; i < times; i++)
            {
                strcat(final, temp);
            }           

            memset(temp, 0, sizeof(capacity));
        }
        else
        {
            push(stack, curr);
        }
    }
    
    while (!isEmpty(stack))
    {
        char ch = pop(stack);
        strncat(temp, &ch, 1);
    }
    revstr(temp);
    strcat(final, temp);
    
    return final;
}

## :memo: *01 Matrix (Medium)
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.



### 作法 BFS C++

class Solution {  // BFS
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int rows = mat.size();
        if (rows == 0) {
            return mat;
        }
        int cols = mat[0].size();
        vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
        queue<pair<int, int>> q;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.push({ i, j});
                }
            }
        }
        
        int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!q.empty()) {
            pair<int, int> curr = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int new_r = curr.first + dir[i][0];
                int new_c = curr.second + dir[i][1];
                if (new_r >= 0 && new_c >=0 && new_r < rows && new_c < cols) {
                    if (dist[new_r][new_c] > dist[curr.first][curr.second] + 1) {
                        dist[new_r][new_c] = dist[curr.first][curr.second] + 1;
                        q.push({new_r, new_c});
                    }                    
                }            
            }
        }
        
        return dist;
    }
};

### 作法 BFS C
這一題是參考Solution上的C++作法以C語言去實作code，算是蠻好的教學範例，標準寫法值得去記憶

//用C 去實作Solution上的C++寫法
struct queue {
    int i;
    int j;
    struct queue* next;
};

struct queue* head;
struct queue* tail;
 
void pop() {
    if (head != NULL)
    {
        head = head->next;
    }
}

void push(struct queue* q) {
    if (head == NULL)
    {
        head = q;
        tail = q;
        head->next = NULL;
        tail->next = NULL;
    }
    else
    {
        tail->next = q;
        tail = q;
        tail->next = NULL;
    }
}

int** array;

int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
    int row,col, row_a, col_a, res = 0, res_n = 10;
    int i, j;
    struct queue** q;
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    array = (int**) malloc(sizeof(int*) * matSize);
    q = (struct queuq**) malloc(sizeof(struct queue*) * matSize);
    for (int i = 0; i < matSize; i++)
    {
        array[i] = (int*) malloc(sizeof(int) * (*matColSize));
        q[i] = (struct queue*) malloc(sizeof(struct queue) * (*matColSize));
    }
    *returnSize = matSize;
    *returnColumnSizes = (int*) malloc(sizeof(int) * matSize);
    for (int i = 0; i < matSize; i++)
    {
        returnColumnSizes[0][i] = *matColSize;
    }
    //BFS
    for (int i = 0; i < matSize;i++)
    {
        for(int j = 0; j < *matColSize; j++)
        {
            if (mat[i][j])
            {
                array[i][j] = INT_MAX;
                q[i][j].i = i;
                q[i][j].j = j;
            }
            else
            {
                array[i][j] = 0;
                q[i][j].i = i;
                q[i][j].j = j;
                push(&q[i][j]);
            }
        }
    }
    while (head != NULL)
    {
        int new_r,new_c;
        for(int i = 0; i < 4; i++)
        {
            new_r = head->i + dir[i][0];
            new_c = head->j + dir[i][1];
            if (new_r >= 0 && new_c >= 0 && new_r < matSize && new_c < *matColSize)
            {
                if (array[new_r][new_c] > array[head->i][head->j] + 1)
                {
                    array[new_r][new_c] = array[head->i][head->j] + 1;
                    push(&q[new_r][new_c]);
                }
            }
        }
        pop();
    }
    
    return array;   
}

### 作法 Dynamic Programming C++

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) 
            return matrix;
        int cols = matrix[0].size();
        vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX - 100000));

        //First pass: check for left and top
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    dist[i][j] = 0;
                } else {
                    if (i > 0)
                        dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
                    if (j > 0)
                        dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
                }
            }
        }

        //Second pass: check for bottom and right
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                if (i < rows - 1)
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
                if (j < cols - 1)
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
            }
        }
        
        return dist;
    }
};

## :memo: Keys and Rooms (Medium)
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of **distinct keys** in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit **all** the rooms, or false otherwise.



### 作法 DFS

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<int> mark(rooms.size(), 0);
        mark[0] = 1;
        stack<int> s;
                
        s.push(0);        
        while (!s.empty()) {
            int next_room = s.top();
            s.pop();
            mark[next_room] = 1;
            for (int i = 0; i < rooms[next_room].size(); i++) {                
                if (!mark[rooms[next_room][i]]) {
                    mark[rooms[next_room][i]] = 1;
                    s.push(rooms[next_room][i]);
                }        
            }
        }
        
        for (int k : mark) {
            if (k == 0) {
                return false;
            }
        }
        
        return true;
    }
};

## :memo: 十六、Monotonic Stack
stack中保持著一定的順序，例如遞增或是遞減。
如果要新增的element比top還大/小。就把top pop出去。然後繼續往下比，直到保持一定的遞增或是遞減的順序。通常是找序列中比自己後面，但是值比自己還大/小的題目。

## :memo: Sum of Subarray Ranges (Medium)
You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.


### 作法 Monotonic Stack
**時間: O(N)**
**空間: O(N)**

class Solution {
public:
    // Monotonic Stack
    long long subArrayRanges(vector<int>& nums) {
        // calculate the times of the number being the minimum/maximum value in the subarray
        int n = nums.size();
        long long ans = 0;
        stack<int> stk;

        //min
        for (int right = 0; right <= n; right++) {
            while (!stk.empty() and (right == n || nums[stk.top()] >= nums[right])) {
                int mid = stk.top();
                stk.pop();
                int left = stk.empty() ? -1 : stk.top();
                ans -= (long long) nums[mid] * (right - mid) * (mid - left);
            }
            stk.push(right);
        }

        stk.pop();
        
        //max
        for (int right = 0; right <= n; right++) {
            while (!stk.empty() and (right == n || nums[stk.top()] <= nums[right])) {
                int mid = stk.top();
                stk.pop();
                int left = stk.empty() ? -1 : stk.top();
                ans += (long long) nums[mid] * (right - mid) * (mid - left);
            }
            stk.push(right);
        }

        return ans;
    }
};

## :memo: 刷題檢討
Queue和Stack這兩個資料結構，在解題上有很重要的地位，通常想到要用哪一種資料結構，基本上這一題就會寫了，由於C語言沒有Built-in library所以會變得比較多行較不方便，這類型題目大多為Medium，所以要多練習，至於Queue和Stack裡面要裝什麼東西也是一個重要關鍵，裝的是index還是val，會影響到整個過程，而BFS是利用Queue和DFS是利用Stack，有沒有加上visited去記錄很重要，BFS和DFS的時間空間複雜度還沒去探討，腦袋要裝進BFS和DFS的traverse過程，資料結構演算法理論部分要再去看書研究

BFS較快但空間需求大
DFS較慢但空間需求少

There are also some important extensions of the queue. For example,
* Priority Queue