花花酱 LeetCode 501. Find Mode in Binary Search Tree

By zxi on July 19, 2018

Problem

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solution1: Recursion w/ extra space

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> findMode(TreeNode* root) {

inorder(root);

return ans_;

}

private:

int val_ = 0;

int count_ = 0;

int max_count_ = 0;

vector<int> ans_;

void inorder(TreeNode* root) {

if (root == nullptr) return;

inorder(root->left);

visit(root->val);

inorder(root->right);

}

void visit(int val) {

if (count_ > 0 && val == val_) {

++count_;

} else {

val_ = val;

count_ = 1;

}

if (count_ > max_count_) {

max_count_ = count_;

ans_.clear();

}

if (count_ == max_count_)

ans_.push_back(val);

}

};

Solution2: Recursion w/o extra space

Two passes. First pass to find the count of the mode, second pass to collect all the modes.

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> findMode(TreeNode* root) {

inorder(root);

mode_count_ = max_count_;

count_ = 0;

inorder(root);

return ans_;

}

private:

int val_ = 0;

int count_ = 0;

int mode_count_ = INT_MAX;

int max_count_ = 0;

vector<int> ans_;

void inorder(TreeNode* root) {

if (root == nullptr) return;

inorder(root->left);

visit(root->val);

inorder(root->right);

}

void visit(int val) {

if (count_ > 0 && val == val_) {

++count_;

} else {

val_ = val;

count_ = 1;

}

if (count_ > max_count_)

max_count_ = count_;

if (count_ == mode_count_)

ans_.push_back(val);

}

};

花花酱 LeetCode 427. Construct Quad Tree

By zxi on July 17, 2018

Problem

We want to use quad trees to store an N x N boolean grid. Each cell in the grid can only be true or false. The root node represents the whole grid. For each node, it will be subdivided into four children nodes until the values in the region it represents are all the same.

Each node has another two boolean attributes : isLeaf and val. isLeaf is true if and only if the node is a leaf node. The val attribute for a leaf node contains the value of the region it represents.

Your task is to use a quad tree to represent a given grid. The following example may help you understand the problem better:

Given the 8 x 8 grid below, we want to construct the corresponding quad tree:

It can be divided according to the definition above:

The corresponding quad tree should be as following, where each node is represented as a (isLeaf, val)pair.

For the non-leaf nodes, val can be arbitrary, so it is represented as *.

Note:

N is less than 1000 and guaranteened to be a power of 2.
If you want to know more about the quad tree, you can refer to its wiki.

Solution: Recursion

Time complexity: O(n^2*logn)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

Node* construct(vector<vector<int>>& grid) {

return construct(grid, 0, 0, grid.size());

}

private:

Node* construct(const vector<vector<int>>& grid, int x, int y, int n) {

if (n == 0) return nullptr;

bool all_zeros = true;

bool all_ones = true;

for (int i = y; i < y + n; ++i)

for (int j = x; j < x + n; ++j)

if (grid[i][j] == 0)

all_ones = false;

else

all_zeros = false;

if (all_zeros || all_ones)

return new Node(all_ones, true, nullptr, nullptr, nullptr, nullptr);

return new Node(true, false,

construct(grid, x, y, n/2), // topLeft

construct(grid, x + n/2, y, n/2), // topRight

construct(grid, x, y + n/2, n/2), // bottomLeft

construct(grid, x + n/2, y + n/2, n/2)); // bottomRight

}

};

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Running time: 56 ms

class Solution {

public:

Node* construct(vector<vector<int>>& grid) {

return construct(grid, 0, 0, grid.size());

}

private:

Node* construct(const vector<vector<int>>& grid, int x, int y, int n) {

if (n == 0) return nullptr;

if (n == 1) return new Node(grid[y][x], true, nullptr, nullptr, nullptr, nullptr);

auto tl = construct(grid, x, y, n/2); // topLeft

auto tr = construct(grid, x + n/2, y, n/2); // topRight

auto bl = construct(grid, x, y + n/2, n/2); // bottomLeft

auto br = construct(grid, x + n/2, y + n/2, n/2); // bottomRight

if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf

&& tl->val == tr->val && tl->val == bl->val && tl->val == br->val) {

auto root = new Node(tl->val, true, nullptr, nullptr, nullptr, nullptr);

delete tl;

delete tr;

delete bl;

delete br;

return root;

}

return new Node(true, false, tl, tr, bl, br);

}

};

花花酱 LeetCode 491. Increasing Subsequences

By zxi on July 17, 2018

Problem

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

The length of the given array will not exceed 15.
The range of integer in the given array is [-100,100].
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 140 ms (<99.88%)

class Solution {

public:

vector<vector<int>> findSubsequences(vector<int>& nums) {

vector<vector<int>> ans;

vector<int> cur;

dfs(nums, 0, cur, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int s, vector<int>& cur, vector<vector<int>>& ans) {

unordered_set<int> seen;

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

if (!cur.empty() && nums[i] < cur.back()) continue;

// each number can be used only once at the same depth.

if (seen.count(nums[i])) continue;

seen.insert(nums[i]);

cur.push_back(nums[i]);

if (cur.size() > 1)

ans.push_back(cur);

dfs(nums, i + 1, cur, ans);

cur.pop_back();

}

};

花花酱 LeetCode 872. Implement Rand10() Using Rand7()

By zxi on July 16, 2018

Problem

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

rand7 is predefined.
Each testcase has one argument: n, the number of times that rand10 is called.

Solution: Math

Time complexity: O(49/40) = O(1)

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int rand10() {

int target = 40;

while (target >= 40)

target = 7 * (rand7() - 1) + (rand7() - 1);

return target % 10 + 1;

}

};

Time complexity: O(7/6 + 7 / 5) = O(1)

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int rand10() {

int i = INT_MAX;

int j = INT_MAX;

while (i > 6) i = rand7(); // i = [1, 2, 3, 4, 5, 6]

while (j > 5) j = rand7(); // j = [1, 2, 3, 4, 5]

return j + 5 * (i & 1);

}

};

花花酱 LeetCode 357. Count Numbers with Unique Digits

By zxi on July 16, 2018

Problem

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10ⁿ.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Solution: Math

f(0) = 1 (0)

f(1) = 10 (0 – 9)

f(2) = 9 * 9 (1-9 * (0 ~ 9 exclude the one from first digit))

f(3) = 9 * 9 * 8

f(4) = 9 * 9 * 8 * 7

…

f(x) = 0 if x >= 10

ans = sum(f[1] ~ f[n])

Time complexity: O(1)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int countNumbersWithUniqueDigits(int n) {

if (n == 0) return 1;

vector<int> f(11);

f[1] = 10;

f[2] = 9 * 9;

for (int i = 3; i <= 10; ++i)

f[i] = f[i - 1] * (10 - i + 1);

int ans = 0;

for (int i = 0; i <= min(10, n); ++i)

ans += f[i];

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 501. Find Mode in Binary Search Tree

Problem

Solution1: Recursion w/ extra space

Solution2: Recursion w/o extra space

花花酱 LeetCode 427. Construct Quad Tree

Problem

Solution: Recursion

花花酱 LeetCode 491. Increasing Subsequences

Problem

Solution: DFS

花花酱 LeetCode 872. Implement Rand10() Using Rand7()

Problem

Solution: Math

花花酱 LeetCode 357. Count Numbers with Unique Digits

Problem

Solution: Math