花花酱 LeetCode 641. Design Circular Deque

By zxi on July 14, 2018

Problem

Design your implementation of the circular double-ended queue (deque).
Your implementation should support following operations:

MyCircularDeque(k): Constructor, set the size of the deque to be k.
insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
getRear(): Gets the last item from Deque. If the deque is empty, return -1.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.

Example:

MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);			// return true
circularDeque.insertLast(2);			// return true
circularDeque.insertFront(3);			// return true
circularDeque.insertFront(4);			// return false, the queue is full
circularDeque.getRear();  				// return 32
circularDeque.isFull();				// return true
circularDeque.deleteLast();			// return true
circularDeque.insertFront(4);			// return true
circularDeque.getFront();				// return 4

Note:

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

Solution

Using head and tail to pointer to the head and the tail in the circular buffer.

// Author: Huahua

// Running time: 20 ms

class MyCircularDeque {

public:

/** Initialize your data structure here. Set the size of the deque to be k. */

MyCircularDeque(int k): k_(k), q_(k), head_(1), tail_(-1), size_(0) {}

/** Adds an item at the front of Deque. Return true if the operation is successful. */

bool insertFront(int value) {

if (isFull()) return false;

head_ = (head_ - 1 + k_) % k_;

q_[head_] = value;

if (size_ == 0) tail_ = head_;

++size_;

return true;

}

/** Adds an item at the rear of Deque. Return true if the operation is successful. */

bool insertLast(int value) {

if (isFull()) return false;

tail_ = (tail_ + 1 + k_) % k_;

q_[tail_] = value;

if (size_ == 0) head_ = tail_;

++size_;

return true;

}

/** Deletes an item from the front of Deque. Return true if the operation is successful. */

bool deleteFront() {

if (isEmpty()) return false;

head_ = (head_ + 1 + k_) % k_;

--size_;

return true;

}

/** Deletes an item from the rear of Deque. Return true if the operation is successful. */

bool deleteLast() {

if (isEmpty()) return false;

tail_ = (tail_ - 1 + k_) % k_;

--size_;

return true;

}

/** Get the front item from the deque. */

int getFront() {

if (isEmpty()) return -1;

return q_[head_];

}

/** Get the last item from the deque. */

int getRear() {

if (isEmpty()) return -1;

return q_[tail_];

}

/** Checks whether the circular deque is empty or not. */

bool isEmpty() {

return size_ == 0;

}

/** Checks whether the circular deque is full or not. */

bool isFull() {

return size_ == k_;

}

private:

const int k_;

int head_;

int tail_;

int size_;

vector<int> q_;

};

Problem

Given a positive integer N, find and return the longest distance between two consecutive 1’s in the binary representation of N.

If there aren’t two consecutive 1’s, return 0.

Example 1:

Input: 22
Output: 2
Explanation: 
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2.

Example 2:

Input: 5
Output: 2
Explanation: 
5 in binary is 0b101.

Example 3:

Input: 6
Output: 1
Explanation: 
6 in binary is 0b110.

Example 4:

Input: 8
Output: 0
Explanation: 
8 in binary is 0b1000.
There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.\

Note:

1 <= N <= 10^9

Solution: Bit

Time complexity: O(logN)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int binaryGap(int N) {

int l = -1;

int ans = 0;

for (int i = 0; i < 31; ++i)

if (N & (1 << i)) {

if (l >= 0)

ans = max(ans, i - l);

l = i;

}

return ans;

}

};

花花酱 LeetCode 429. N-ary Tree Level Order Traversal

By zxi on July 14, 2018

Problem

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

We should return its level order traversal:

[
     [1],
     [3,2,4],
     [5,6]
]

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Solution1: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<vector<int>> levelOrder(Node* root) {

vector<vector<int>> ans;

preorder(root, 0, ans);

return ans;

}

private:

void preorder(Node* root, int d, vector<vector<int>>& ans) {

if (root == nullptr) return;

while (ans.size() <= d) ans.push_back({});

ans[d].push_back(root->val);

for (auto child : root->children)

preorder(child, d + 1, ans);

}

};

Solution2: Iterative

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<vector<int>> levelOrder(Node* root) {

if (!root) return {};

vector<vector<int>> ans;

queue<Node*> q;

q.push(root);

int depth = 0;

while (!q.empty()) {

int size = q.size();

ans.push_back({});

while (size--) {

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

ans[depth].push_back(n->val);

for (auto child : n->children)

q.push(child);

}

++depth;

}

return ans;

}

};

花花酱 LeetCode 350. Intersection of Two Arrays II

By zxi on July 14, 2018

Problem

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution1: Hashtable

Time complexity: O(m + n)

Space complexity: O(m)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

unordered_map<int, int> count;

vector<int> ans;

for (int num : nums1)

++count[num];

for (int num : nums2)

if (count.count(num) &&count[num] > 0) {

--count[num];

ans.push_back(num);

}

return ans;

}

};

Posts published in July 2018

花花酱 LeetCode 641. Design Circular Deque

Problem

Solution

Related Problems

花花酱 LeetCode 868. Binary Gap

Problem

Solution: Bit

花花酱 LeetCode 429. N-ary Tree Level Order Traversal

Problem

Solution1: Recursion

Solution2: Iterative

花花酱 LeetCode 350. Intersection of Two Arrays II

Problem

Solution1: Hashtable

Posts published in July 2018

花花酱 LeetCode 445. Add Two Numbers II

Problem

Solution: Simulation

Related Problems

花花酱 LeetCode 641. Design Circular Deque

Problem

Solution

Related Problems

花花酱 LeetCode 868. Binary Gap

Problem

Solution: Bit

花花酱 LeetCode 429. N-ary Tree Level Order Traversal

Problem

Solution1: Recursion

Solution2: Iterative

花花酱 LeetCode 350. Intersection of Two Arrays II

Problem

Solution1: Hashtable