Posts tagged as “queue”

花花酱 LeetCode 133. Clone Graph

By zxi on February 13, 2019

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.
OJ’s undirected graph serialization (so you can understand error output):

Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don’t need to understand the serialization to solve the problem.

Solution: Queue + Hashtable

Time complexity: O(V+E)
Space complexity: O(V+E)

C++

// Author: Huahua, 44ms, 16.8MB

class Solution {

public:

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

if (!node) return nullptr;

typedef UndirectedGraphNode Node;

unordered_set<Node*> done;

unordered_map<Node*, Node*> m;

queue<Node*> q;

q.push(node);

while (!q.empty()) {

Node* s = q.front(); q.pop();

if (done.count(s)) continue;

done.insert(s);

if (!m.count(s))

m[s] = new Node(s->label);

Node* t = m[s];

for (Node* ss : s->neighbors) {

if (!m.count(ss))

m[ss] = new Node(ss->label);

q.push(ss);

t->neighbors.push_back(m[ss]);

}

return m[node];

}

};

花花酱 LeetCode 933. Number of Recent Calls

By zxi on November 4, 2018

Problem

Write a class RecentCounter to count recent requests.

It has only one method: ping(int t), where t represents some time in milliseconds.

Return the number of pings that have been made from 3000 milliseconds ago until now.

Any ping with time in [t - 3000, t] will count, including the current ping.

It is guaranteed that every call to ping uses a strictly larger value of t than before.

Example 1:

Input: inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]

Note:

Each test case will have at most 10000 calls to ping.
Each test case will call ping with strictly increasing values of t.
Each call to ping will have 1 <= t <= 10^9.

Solution: Queue

Use a FIFO queue to track all the previous pings that are within 3000 ms to current.

Time complexity: Avg O(1), Total O(n)

Space complexity: O(n)

C++

class RecentCounter {

public:

RecentCounter() {}

int ping(int t) {

while (!q.empty() && t - q.front() > 3000) q.pop();

q.push(t);

return q.size();

}

private:

queue<int> q;

};

花花酱 LeetCode 622. Design Circular Queue

By zxi on July 12, 2018

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support following operations:

MyCircularQueue(k): Constructor, set the size of the queue to be k.
Front: Get the front item from the queue. If the queue is empty, return -1.
Rear: Get the last item from the queue. If the queue is empty, return -1.
enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
isEmpty(): Checks whether the circular queue is empty or not.
isFull(): Checks whether the circular queue is full or not.

Example:

MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1);  // return true
circularQueue.enQueue(2);  // return true
circularQueue.enQueue(3);  // return true
circularQueue.enQueue(4);  // return false, the queue is full
circularQueue.Rear();  // return 3
circularQueue.isFull();  // return true
circularQueue.deQueue();  // return true
circularQueue.enQueue(4);  // return true
circularQueue.Rear();  // return 4

Note:

All values will be in the range of [0, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Queue library.

Solution: Simulate with an array

We need a fixed length array, and the head location as well as the size of the current queue.

We can use q[head] to access the front, and q[(head + size – 1) % k] to access the rear.

Time complexity: O(1) for all the operations.
Space complexity: O(k)

C++

// Author: Huahua

class MyCircularQueue {

public:

MyCircularQueue(int k): q_(k) {}

bool enQueue(int value) {

if (isFull()) return false;

q_[(head_ + size_) % q_.size()] = value;

++size_;

return true;

}

bool deQueue() {

if (isEmpty()) return false;

head_ = (head_ + 1) % q_.size();

--size_;

return true;

}

int Front() { return isEmpty() ? -1 : q_[head_]; }

int Rear() { return isEmpty() ? -1 : q_[(head_ + size_ - 1) % q_.size()]; }

bool isEmpty() { return size_ == 0; }

bool isFull() { return size_ == q_.size(); }

private:

vector<int> q_;

int head_ = 0;

int size_ = 0;

};

Java

class MyCircularQueue {

private int[] q;

private int head;

private int size;

public MyCircularQueue(int k) {

this.q = new int[k];

this.head = 0;

this.size = 0;

}

public boolean enQueue(int value) {

if (this.isFull()) return false;

this.q[(this.head + this.size) % this.q.length] = value;

++this.size;

return true;

}

public boolean deQueue() {

if (this.isEmpty()) return false;

this.head = (this.head + 1) % this.q.length;

--this.size;

return true;

}

public int Front() {

return this.isEmpty() ? -1 : this.q[this.head];

}

public int Rear() {

return this.isEmpty() ? -1 : this.q[(this.head + this.size - 1) % this.q.length];

}

public boolean isEmpty() { return this.size == 0; }

public boolean isFull() { return this.size == this.q.length; }

}

Python3

class MyCircularQueue:

def __init__(self, k: int):

self.q = [0] * k

self.k = k

self.head = self.size = 0

def enQueue(self, value: int) -> bool:

if self.isFull(): return False

self.q[(self.head + self.size) % self.k] = value

self.size += 1

return True

def deQueue(self) -> bool:

if self.isEmpty(): return False

self.head = (self.head + 1) % self.k

self.size -= 1

return True

def Front(self) -> int:

return -1 if self.isEmpty() else self.q[self.head]

def Rear(self) -> int:

return -1 if self.isEmpty() else self.q[(self.head + self.size - 1) % self.k]

def isEmpty(self) -> bool:

return self.size == 0

def isFull(self) -> bool:

return self.size == self.k

花花酱 LeetCode 225. Implement Stack using Queues

By zxi on March 13, 2018

题目大意：用队列来实现栈。

Problem:

https://leetcode.com/problems/implement-stack-using-queues/description/

Implement the following operations of a stack using queues.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
empty() — Return whether the stack is empty.

Notes:

You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Idea:

Using a single queue, for every push, shift the queue (n – 1) times such that the last element becomes the first element in the queue.

e.g.

push(1): q: [1]

push(2): q: [1, 2] -> [2, 1]

push(3): q: [2, 1, 3] -> [1, 3, 2] -> [3, 2, 1]

push(4): q: [3, 2, 1, 4] -> [2, 1, 4, 3] -> [1, 4, 3, 2] -> [4, 3, 2, 1]

Solution:

Time complexity:

Push: O(n)

Pop/top/empty: O(1)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 3 ms

class MyStack {

public:

/** Initialize your data structure here. */

MyStack() {}

/** Push element x onto stack. */

void push(int x) {

q_.push(x);

for (int i = 1; i < q_.size(); ++i) {

q_.push(q_.front());

q_.pop();

}

/** Removes the element on top of the stack and returns that element. */

int pop() {

int top = q_.front();

q_.pop();

return top;

}

/** Get the top element. */

int top() {

return q_.front();

}

/** Returns whether the stack is empty. */

bool empty() {

return q_.empty();

}

private:

queue<int> q_;

};

花花酱 LeetCode 239. Sliding Window Maximum

By zxi on January 24, 2018

题目大意：给你一个数组，让你输出移动窗口的最大值。

Problem:

https://leetcode.com/problems/sliding-window-maximum/

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max

--------------- -----

[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

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

Idea:

Solution 1: Brute Force

Time complexity: O((n – k + 1) * k)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 180 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

vector<int> ans;

for (int i = k - 1; i < nums.size(); ++i) {

ans.push_back(*max_element(nums.begin() + i - k + 1, nums.begin() + i + 1));

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 80 ms

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {

if (k == 0) return new int[0];

int[] ans = new int[nums.length - k + 1];

for (int i = k - 1; i < nums.length; ++i) {

int maxNum = nums[i];

for (int j = 1; j < k; ++j)

if (nums[i - j] > maxNum) maxNum = nums[i - j];

ans[i - k + 1] = maxNum;

}

return ans;

}

Python

"""

Author: Huahua

Running time: 1044 ms

"""

class Solution:

def maxSlidingWindow(self, nums, k):

if not nums: return []

return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

Solution 2: BST

Time complexity: O((n – k + 1) * logk)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

vector<int> ans;

if (nums.empty()) return ans;

multiset<int> window(nums.begin(), nums.begin() + k - 1);

for (int i = k - 1; i < nums.size(); ++i) {

window.insert(nums[i]);

ans.push_back(*window.rbegin());

if (i - k + 1 >= 0)

window.erase(window.equal_range(nums[i - k + 1]).first);

}

return ans;

}

};

Solution 3: Monotonic Queue

Time complexity: O(n)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 70 ms

class MonotonicQueue {

public:

void push(int e) {

while(!data_.empty() && e > data_.back()) data_.pop_back();

data_.push_back(e);

}

void pop() {

data_.pop_front();

}

int max() const { return data_.front(); }

private:

deque<int> data_;

};

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

MonotonicQueue q;

vector<int> ans;

for (int i = 0; i < nums.size(); ++i) {

q.push(nums[i]);

if (i - k + 1 >= 0) {

ans.push_back(q.max());

if (nums[i - k + 1] == q.max()) q.pop();

}

return ans;

}

};

C++ V2

// Author: Huahua

// Running time: 65 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

deque<int> index;

vector<int> ans;

for (int i = 0; i < nums.size(); ++i) {

while (!index.empty() && nums[i] >= nums[index.back()]) index.pop_back();

index.push_back(i);

if (i - k + 1 >= 0) ans.push_back(nums[index.front()]);

if (i - k + 1 >= index.front()) index.pop_front();

}

return ans;

}

};

C++ V3

// Author: Huahua

// Running time: 67 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

deque<int> q;

vector<int> ans;

for (int i = 0; i < nums.size(); ++i) {

while (!q.empty() && nums[i] > q.back()) q.pop_back();

q.push_back(nums[i]);

const int s = i - k + 1;

if (s < 0) continue;

ans.push_back(q.front());

if (nums[s] == q.front()) q.pop_front();

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 19 ms

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {

if (k == 0) return nums;

int[] ans = new int[nums.length - k + 1];

Deque<Integer> indices = new LinkedList<>();

for (int i = 0; i < nums.length; ++i) {

while (indices.size() > 0 && nums[i] >= nums[indices.getLast()])

indices.removeLast();

indices.addLast(i);

if (i - k + 1 >= 0) ans[i - k + 1] = nums[indices.getFirst()];

if (i - k + 1 >= indices.getFirst()) indices.removeFirst();

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 238 ms

"""

class MaxQueue:

def __init__(self):

self.q_ = collections.deque()

def push(self, e):

while self.q_ and e > self.q_[-1]: self.q_.pop()

self.q_.append(e)

def pop(self):

self.q_.popleft()

def max(self):

return self.q_[0]

class Solution:

def maxSlidingWindow(self, nums, k):

q = MaxQueue()

ans = []

for i in range(len(nums)):

q.push(nums[i])

if i >= k - 1:

ans.append(q.max())

if nums[i - k + 1] == q.max(): q.pop()

return ans

Python3 V2

"""

Author: Huahua

Running time: 193 ms

"""

class Solution:

def maxSlidingWindow(self, nums, k):

indices = collections.deque()

ans = []

for i in range(len(nums)):

while indices and nums[i] >= nums[indices[-1]]: indices.pop()

indices.append(i)

if i >= k - 1: ans.append(nums[indices[0]])

if i - k + 1 == indices[0]: indices.popleft()

return ans