花花酱 LeetCode 115. Distinct Subsequences

By zxi on July 19, 2018

Problem

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:  As shown below, there are 3 ways you can generate "rabbit" from S. (The caret symbol ^ means the chosen letters) 
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:  As shown below, there are 5 ways you can generate "bag" from S. (The caret symbol ^ means the chosen letters)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^

Solution: DP

Time complexity: O(|s| * |t|)

Space complexity: O(|s| * |t|)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numDistinct(string s, string t) {

int ls = s.length();

int lt = t.length();

vector<vector<int>> dp(lt + 1, vector<int>(ls + 1));

fill(begin(dp[0]), end(dp[0]), 1);

for (int i = 1; i <= lt; ++i)

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

dp[i][j] = dp[i][j - 1] + (t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] : 0);

return dp[lt][ls];

}

};

Problem

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two (axis-aligned) rectangles, return whether they overlap.

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Notes:

Both rectangles rec1 and rec2 are lists of 4 integers.
All coordinates in rectangles will be between -10^9 and 10^9.

Solution: Geometry

Time complexity: O(1)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {

return rec1[0] < rec2[2] && rec2[0] < rec1[2] &&

rec1[1] < rec2[3] && rec2[1] < rec1[3];

}

};

花花酱 LeetCode 345. Reverse Vowels of a String

By zxi on July 19, 2018

Problem

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

Solution

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string reverseVowels(string s) {

int i = 0;

int j = s.size() - 1;

while (i < j) {

while (!isVowel(s[i]) && i < j) ++i;

while (!isVowel(s[j]) && i < j) --j;

swap(s[i++], s[j--]);

}

return s;

}

private:

bool isVowel(char c) {

c = tolower(c);

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

}

};

花花酱 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);

}

};

Posts published in July 2018

花花酱 LeetCode 115. Distinct Subsequences

Problem

Solution: DP

Related Problems:

花花酱 LeetCode 836. Rectangle Overlap

Problem

Solution: Geometry

花花酱 LeetCode 345. Reverse Vowels of a String

Problem

Solution

花花酱 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