花花酱 LeetCode 698. Partition to K Equal Sum Subsets

By zxi on July 13, 2018

Problem

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into knon-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

Solution: Search

Time complexity: O(n!)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms (<99.21%)

class Solution {

public:

bool canPartitionKSubsets(vector<int>& nums, int k) {

const int sum = accumulate(nums.begin(), nums.end(), 0);

if (sum % k != 0) return false;

sort(nums.rbegin(), nums.rend());

return dfs(nums, sum / k, 0, k, 0);

}

private:

bool dfs(const vector<int>& nums, int target, int cur, int k, int used) {

if (k == 0) return used == (1 << nums.size()) - 1;

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

if (used & (1 << i)) continue;

int t = cur + nums[i];

if (t > target) break; // Important

int new_used = used | (1 << i);

if (t == target && dfs(nums, target, 0, k - 1, new_used)) return true;

else if (dfs(nums, target, t, k, new_used)) return true;

}

return false;

}

};

花花酱 LeetCode 590. N-ary Tree Postorder Traversal

By zxi on July 12, 2018

Problem

Given an n-ary tree, return the postorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its postorder traversal as: [5,6,3,2,4,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursive

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<int> postorder(Node* root) {

vector<int> ans;

postorder(root, ans);

return ans;

}

private:

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

if (!root) return;

for (auto child : root->children)

postorder(child, ans);

ans.push_back(root->val);

}

};

Solution 2: Iterative

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<int> postorder(Node* root) {

if (!root) return {};

vector<int> ans;

stack<Node*> s;

s.push(root);

while (!s.empty()) {

const Node* node = s.top(); s.pop();

ans.push_back(node->val);

for (auto child : node->children)

s.push(child);

}

reverse(begin(ans), end(ans));

return ans;

}

};

Problem

Given an n-ary tree, return the preorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].

Note: Recursive solution is trivial, could you do it iteratively?

Solution1: Recursive

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

vector<int> preorder(Node* root) {

vector<int> ans;

preorder(root, ans);

return ans;

}

private:

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

if (!root) return;

ans.push_back(root->val);

for (const auto& child : root->children)

preorder(child, ans);

}

};

Solution2: Iterative

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<int> preorder(Node* root) {

if (!root) return {};

vector<int> ans;

stack<Node*> s;

s.push(root);

while (!s.empty()) {

const Node* node = s.top(); s.pop();

ans.push_back(node->val);

for (auto it = node->children.rbegin(); it != node->children.rend(); ++it)

s.push(*it);

}

return ans;

}

};

Related Problems

花花酱 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 701. Insert into a Binary Search Tree

By zxi on July 12, 2018

Problem

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

Given the tree:

/ \

2 7

/ \

1 3

And the value to insert: 5

You can return this binary search tree:

/ \

2 7

/ \ /

1 3 5

This tree is also valid:

/ \

2 7

/ \

1 3

Solution: Recursion

Time complexity: O(logn ~ n)

Space complexity: O(logn ~ n)

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

TreeNode* insertIntoBST(TreeNode* root, int val) {

if (root == nullptr) return new TreeNode(val);

if (val > root->val)

root->right = insertIntoBST(root->right, val);

else

root->left = insertIntoBST(root->left, val);

return root;

}

};

Huahua's Tech Road

花花酱 LeetCode 698. Partition to K Equal Sum Subsets

Problem

Solution: Search

花花酱 LeetCode 590. N-ary Tree Postorder Traversal

Problem

Solution 1: Recursive

C++

Solution 2: Iterative

C++

Related Problems

花花酱 LeetCode 589. N-ary Tree Preorder Traversal

Problem

Solution1: Recursive

Solution2: Iterative

Related Problems

花花酱 LeetCode 622. Design Circular Queue

Solution: Simulate with an array

C++

Java

Python3

花花酱 LeetCode 701. Insert into a Binary Search Tree

Problem

Solution: Recursion