Huahua's Tech Road

花花酱 LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

By zxi on March 13, 2020

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Follow up: Solve the problem if repeated values on the tree are allowed.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target =  7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4:

Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5

Example 5:

Input: tree = [1,2,null,3], target = 2
Output: 2

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

Solution: Recursion

Traverse both trees in the same order, if original == target, return cloned.

Time complexity: O(n)
Space complexity: O(h)

C++

// Author: Huahua

class Solution {

public:

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {

if (!original) return nullptr;

if (original == target) return cloned;

auto l = getTargetCopy(original->left, cloned->left, target);

auto r = getTargetCopy(original->right, cloned->right, target);

return l ? l : r;

}

};

Python3

# Author: Huahua

class Solution:

def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

if not original: return None

if original == target: return cloned

return self.getTargetCopy(original.left, cloned.left, target) or \

self.getTargetCopy(original.right, cloned.right, target)

花花酱 LeetCode 375. Guess Number Higher or Lower II

By zxi on March 13, 2020

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Solution: DP

Use dp[l][r] to denote the min money to win the game if the current guessing range is [l, r], to guarantee a win, we need to try all possible numbers in [l, r]. Let say we guess K, we need to pay K and the game might continue if we were wrong. cost will be K + max(dp(l, K-1), dp(K+1, r)), we need max to cover all possible cases. Among all Ks, we picked the cheapest one.

dp[l][r] = min(k + max(dp[l][k – 1], dp[k+1][r]), for l <= k <= r.

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int getMoneyAmount(int n) {

constexpr int kInf = 1e9;

vector<vector<int>> cache(n + 2, vector<int>(n + 2, kInf));

function<int(int, int)> dp = [&](int l, int r) {

int& ans = cache[l][r];

if (l >= r) return 0;

if (ans != kInf) return ans;

for (int x = l; x <= r; ++x)

ans = min(ans, x + max(dp(l, x - 1), dp(x + 1, r)));

return ans;

};

return dp(1, n);

}

};

Python3

# Author: Huahua

class Solution:

def getMoneyAmount(self, n: int) -> int:

@lru_cache(maxsize=None)

def dp(l, r):

return min([k + max(dp(l, k - 1), dp(k + 1, r))

for k in range(l, r + 1)]) if l < r else 0

return dp(1, n)

花花酱 LeetCode 355. Design Twitter

By zxi on March 10, 2020

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

Solution: hashtables

Time complexity:
postTweet O(1)
follow O(1)
unfollow O(1)
getNewsFeed O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

constexpr size_t kMaxTweets = 10;

class Twitter {

public:

/** Initialize your data structure here. */

Twitter() {}

/** Compose a new tweet. */

void postTweet(int userId, int tweetId) {

auto& tweets = user_tweets_[userId];

if (tweets.size() == kMaxTweets)

tweets.pop_front();

tweets.emplace_back(++time_, tweetId);

}

/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */

vector<int> getNewsFeed(int userId) {

vector<pair<int, int>> feed(begin(user_tweets_[userId]),

end(user_tweets_[userId]));

for (int uid : user_followers_[userId])

feed.insert(end(feed),

begin(user_tweets_[uid]),

end(user_tweets_[uid]));

sort(rbegin(feed), rend(feed));

vector<int> ans;

for (int i = 0; i < min(kMaxTweets, feed.size()); ++i)

ans.push_back(feed[i].second);

return ans;

}

/** Follower follows a followee. If the operation is invalid, it should be a no-op. */

void follow(int followerId, int followeeId) {

if (followerId == followeeId) return;

user_followers_[followerId].insert(followeeId);

}

/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */

void unfollow(int followerId, int followeeId) {

if (followerId == followeeId) return;

user_followers_[followerId].erase(followeeId);

}

private:

int time_;

unordered_map<int, deque<pair<int, int>>> user_tweets_;

unordered_map<int, set<int>> user_followers_;

};

/**

* Your Twitter object will be instantiated and called as such:

* Twitter* obj = new Twitter();

* obj->postTweet(userId,tweetId);

* vector<int> param_2 = obj->getNewsFeed(userId);

* obj->follow(followerId,followeeId);

* obj->unfollow(followerId,followeeId);

花花酱 LeetCode 672. Bulb Switcher II

By zxi on March 9, 2020

There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.

Suppose n lights are labeled as number [1, 2, 3 …, n], function of these 4 buttons are given below:

Flip all the lights.
Flip lights with even numbers.
Flip lights with odd numbers.
Flip lights with (3k + 1) numbers, k = 0, 1, 2, …

Example 1:

Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]

Example 2:

Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]

Example 3:

Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].

Note: n and m both fit in range [0, 1000].

Solution1: Bitmask + Simulation

The light pattern will be repeated if we have more than 6 lights, so n = n % 6, n = 6 if n == 0.

Time complexity: O(m*2^6)
Space complexity: O(2^6)

C++

// Author: Huahua

class Solution {

public:

int flipLights(int n, int m) {

if (n > 6) n = n % 6 + 6;

unordered_set<int> s1{(1 << n) - 1};

auto flip = [n](int s, int start, int step) {

for (int i = start; i < n; i += step)

s ^= (1 << i);

return s;

};

for (int i = 0; i < m; ++i) {

unordered_set<int> s2;

for (int s : s1) {

s2.insert(flip(s, 0, 1));

s2.insert(flip(s, 0, 2));

s2.insert(flip(s, 1, 2));

s2.insert(flip(s, 0, 3));

}

s1.swap(s2);

}

return s1.size();

}

};

花花酱 LeetCode 529. Minesweeper

By zxi on March 9, 2020

Let’s play the minesweeper game (Wikipedia, online game)!

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

If a mine (‘M’) is revealed, then the game is over – change it to ‘X’.
If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
Return the board when no more squares will be revealed.

Example 1:

Input: 

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Example 2:

Input: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Note:

The range of the input matrix’s height and width is [1,50].
The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
The input board won’t be a stage when game is over (some mines have been revealed).
For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

Solution: DFS

Time complexity: O(m*n)
Space complexity: O(m* n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {

const int m = board.size();

const int n = board[0].size();

function<void(int, int)> dfs = [&](int x, int y) {

if (board[y][x] != 'E') return;

int c = 0;

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty)

if (tx >= 0 && tx < n && ty >= 0 && ty < m)

c += board[ty][tx] == 'M';

if (c > 0) {

board[y][x] = '0' + c;

return;

}

board[y][x] = 'B';

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty)

if (tx >= 0 && tx < n && ty >= 0 && ty < m)

dfs(tx, ty);

};

int x = click[1];

int y = click[0];

dfs(x, y);

if (board[y][x] == 'M') board[y][x] = 'X';

return board;

}

};

Solution 2: BFS

Python3

# Author: Huahua

class Solution:

def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:

m, n = len(board), len(board[0])

cx, cy = click[1], click[0]

q = [(cx, cy)]

while q:

q2 = []

for x, y in q:

if board[y][x] != 'E': continue

c = 0

for tx in range(x - 1, x + 2):

for ty in range(y - 1, y + 2):

if 0 <= tx < n and 0 <= ty < m and board[ty][tx] == 'M':

c += 1

if c > 0:

board[y][x] = chr(ord('0') + c)

continue

board[y][x] = 'B'

for tx in range(x - 1, x + 2):

for ty in range(y - 1, y + 2):

if 0 <= tx < n and 0 <= ty < m and board[ty][tx] == 'E':

q2.append((tx, ty))

q = q2

if board[cy][cx] == 'M': board[y][x] = 'X'

return board