Huahua’s Tech Road

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

花花酱 LeetCode 227. Basic Calculator II

By zxi on March 9, 2020

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

Solution: Stack

if operator is ‘+’ or ‘-’, push the current num * sign onto stack.
if operator ‘*’ or ‘/’, pop the last num from stack and * or / by the current num and push it back to stack.

The answer is the sum of numbers on stack.

3+2*2 => {3}, {3,2}, {3, 2*2} = {3, 4} => ans = 7
3 +5/2 => {3}, {3,5}, {3, 5/2} = {3, 2} => ans = 5
1 + 2*3 – 5 => {1}, {1,2}, {1,2*3} = {1,6}, {1, 6, -5} => ans = 2

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

C++

// Author: Huahua

class Solution {

public:

int calculate(string s) {

vector<int> nums;

char op = '+';

int cur = 0;

int pos = 0;

while (pos < s.size()) {

if (s[pos] == ' ') {

++pos;

continue;

}

while (isdigit(s[pos]) && pos < s.size())

cur = cur * 10 + (s[pos++] - '0');

if (op == '+' || op == '-') {

nums.push_back(cur * (op == '+' ? 1 : -1));

} else if (op == '*') {

nums.back() *= cur;

} else if (op == '/') {

nums.back() /= cur;

}

cur = 0;

op = s[pos++];

}

return accumulate(begin(nums), end(nums), 0);

}

};

python3

# Author: Huahua

class Solution:

def calculate(self, s: str) -> int:

nums = []

op = '+'

cur = 0

i = 0

while i < len(s):

if s[i] == ' ':

i += 1

continue

while i < len(s) and s[i].isdigit():

cur = cur * 10 + ord(s[i]) - ord('0')

i += 1

if op in '+-':

nums.append(cur * (1 if op == '+' else -1))

elif op == '*':

nums[-1] *= cur

elif op == '/':

sign = -1 if nums[-1] < 0 or cur < 0 else 1

nums[-1] = abs(nums[-1]) // abs(cur) * sign

cur = 0

if (i < len(s)): op = s[i]

i += 1

return sum(nums)

Huahua's Tech Road

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

Solution: DP

C++

Python3

花花酱 LeetCode 355. Design Twitter

Solution: hashtables

C++

花花酱 LeetCode 672. Bulb Switcher II

Solution1: Bitmask + Simulation

C++

花花酱 LeetCode 529. Minesweeper

Solution: DFS

C++

Solution 2: BFS

Python3

花花酱 LeetCode 227. Basic Calculator II

Solution: Stack

C++

python3

Related Problems