Huahua’s Tech Road

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

}

};

花花酱 LeetCode 225. Implement Stack using Queues

By zxi on March 13, 2018

题目大意：用队列来实现栈。

Problem:

https://leetcode.com/problems/implement-stack-using-queues/description/

Implement the following operations of a stack using queues.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
empty() — Return whether the stack is empty.

Notes:

You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Idea:

Using a single queue, for every push, shift the queue (n – 1) times such that the last element becomes the first element in the queue.

e.g.

push(1): q: [1]

push(2): q: [1, 2] -> [2, 1]

push(3): q: [2, 1, 3] -> [1, 3, 2] -> [3, 2, 1]

push(4): q: [3, 2, 1, 4] -> [2, 1, 4, 3] -> [1, 4, 3, 2] -> [4, 3, 2, 1]

Solution:

Time complexity:

Push: O(n)

Pop/top/empty: O(1)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 3 ms

class MyStack {

public:

/** Initialize your data structure here. */

MyStack() {}

/** Push element x onto stack. */

void push(int x) {

q_.push(x);

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

q_.push(q_.front());

q_.pop();

}

/** Removes the element on top of the stack and returns that element. */

int pop() {

int top = q_.front();

q_.pop();

return top;

}

/** Get the top element. */

int top() {

return q_.front();

}

/** Returns whether the stack is empty. */

bool empty() {

return q_.empty();

}

private:

queue<int> q_;

};

Huahua's Tech Road

花花酱 LeetCode 337. House Robber III

花花酱 LeetCode 275. H-Index II

花花酱 LeetCode 278. First Bad Version

花花酱 LeetCode 203. Remove Linked List Elements

花花酱 LeetCode 225. Implement Stack using Queues