花花酱 LeetCode 392. Is Subsequence

By zxi on March 16, 2018

题目大意：问s是不是t的子序列。

Problem:

https://leetcode.com/problems/is-subsequence/description/

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and sis a short string (<=100).

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:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Solution: Brute force

Time Complexity: O(|s| + |t|)

Space Complexity: O(1)

C++

// Author: Huahua

// Running time: 65 ms (beats 99.37%)

class Solution {

public:

bool isSubsequence(const string& s, const string& t) {

int i = 0;

const int n = t.length();

for (const char c : s) {

while (i < n && t[i] != c) ++i;

if (i++ == n) return false;

}

return true;

}

};

花花酱 LeetCode 383. Ransom Note

By zxi on March 15, 2018

题目大意：给你一个字符串，问能否用它其中的字符组成另外一个字符串，每个字符只能使用一次。

Problem:

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Solution: HashTable

Time complexity: O(n + m)

Space complexity: O(128)

C++

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

bool canConstruct(string ransomNote, string magazine) {

vector<int> counts(128, 0);

for (const char c : magazine)

++counts[c];

for (const char c : ransomNote)

if (--counts[c] < 0) return false;

return true;

}

};

// Author: Huahua

// Running time: 9 ms (beats 100%)

static int x=[](){

std::ios::sync_with_stdio(false);

cin.tie(NULL);

return 0;

}();

class Solution {

public:

bool canConstruct(const string& ransomNote, const string& magazine) {

vector<int> counts(128, 0);

for (const char c : magazine)

++counts[c];

for (const char c : ransomNote)

if (--counts[c] < 0) return false;

return true;

}

};

Python3

"""

Author: Huahua

Running time: 64 ms

"""

class Solution:

def canConstruct(self, ransomNote, magazine):

return not collections.Counter(ransomNote) - collections.Counter(magazine);

花花酱 LeetCode 337. House Robber III

By zxi on March 15, 2018

题目大意：给你一棵二叉树，不能同时取两个相邻的节点(parent/child)，问最多能取得的节点的值的和是多少。

Problem:

https://leetcode.com/problems/house-robber-iii/description/

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.

Idea:

Compare grandparent + max of grandchildren(l.l + l.r + r.l + r.r) vs max of children (l + r)

Solution 1: Recursion w/o memorization

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 1289 ms

class Solution {

public:

int rob(TreeNode* root) {

if (root == nullptr) return 0;

int val = root->val;

int ll = root->left ? rob(root->left->left) : 0;

int lr = root->left ? rob(root->left->right) : 0;

int rl = root->right ? rob(root->right->left) : 0;

int rr = root->right ? rob(root->right->right) : 0;

return max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));

}

};

Solution 2: Recursion w/ memorization

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int rob(TreeNode* root) {

if (root == nullptr) return 0;

if (m_.count(root)) return m_[root];

int val = root->val;

int ll = root->left ? rob(root->left->left) : 0;

int lr = root->left ? rob(root->left->right) : 0;

int rl = root->right ? rob(root->right->left) : 0;

int rr = root->right ? rob(root->right->right) : 0;

return m_[root] = max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));

}

private:

unordered_map<TreeNode*, int> m_;

};

Solution 3: Recursion return children’s value

// Author: Huahua

// Running time: 10 ms (beats 97.57%)

class Solution {

public:

int rob(TreeNode* root) {

int l = 0;

int r = 0;

return rob(root, l, r);

}

private:

// return rob(root) and stores rob(root->left/right) in l/r.

int rob(TreeNode* root, int& l, int& r) {

if (root == nullptr) return 0;

int ll = 0;

int lr = 0;

int rl = 0;

int rr = 0;

l = rob(root->left, ll, lr);

r = rob(root->right, rl, rr);

return max(root->val + ll + lr + rl + rr, l + r);

}

};

Python3

"""

Author: Huahua

Running time: 64 ms (beats 93.18%)

"""

class Solution:

def rob(self, root):

def rob(root):

if not root: return 0, 0, 0

l, ll, lr = rob(root.left)

r, rl, rr = rob(root.right)

return max(root.val + ll + lr + rl + rr, l + r), l, r

return rob(root)[0]

Related Problems:

花花酱 LeetCode 198. House Robber

花花酱 LeetCode 275. H-Index II

By zxi on March 15, 2018

题目大意：给你已排序的引用次数的数组，求h-index。

Problem:

https://leetcode.com/problems/h-index-ii/description/

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Solution 1: Linear Scan

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 33 ms

class Solution {

public:

int hIndex(vector<int>& citations) {

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

if (*(citations.rbegin() + i - 1) < i) return i - 1;

return citations.size();

}

};

Solution 2: Binary Search

Time Complexity: O(logn)

Space Complexity: O(1)

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int hIndex(vector<int>& citations) {

int n = citations.size();

int l = 0;

int r = n;

while (l < r) {

int m = l + (r - l) / 2;

if (citations[n - m - 1] <= m)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 278. First Bad Version

By zxi on March 15, 2018

题目大意：给你一个API查询版本是否坏了，让你找出第一个坏掉的版本。

Problem:

https://leetcode.com/problems/first-bad-version/description/

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution 1: Brute Force

Time Complexity: O(n) TLE

Space Complexity: O(1)

Solution 2: Binary Search

Time Complexity: O(logn)

Space Complexity: O(1)

// Forward declaration of isBadVersion API.

bool isBadVersion(int version);

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

int firstBadVersion(int n) {

int l = 1;

int r = n;

while (l < r) {

int m = l + (r - l) / 2;

if (isBadVersion(m))

r = m;

else

l = m + 1;

}

return l;

}

};

Huahua's Tech Road

花花酱 LeetCode 392. Is Subsequence

Problem:

Solution: Brute force

花花酱 LeetCode 383. Ransom Note

花花酱 LeetCode 337. House Robber III

花花酱 LeetCode 275. H-Index II

花花酱 LeetCode 278. First Bad Version