Huahua’s Tech Road

花花酱 LeetCode 1366. Rank Teams by Votes

By zxi on March 2, 2020

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position.

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter so his votes are used for the ranking.

Example 4:

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: 
Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.

Example 5:

Input: votes = ["M","M","M","M"]
Output: "M"
Explanation: Only team M in the competition so it has the first rank.

Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English upper-case letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

Solution: Sort by rank

Time complexity: O(v*n + n^2*logn)
Space complexity: O(n*n)

C++

// Author: Huahua

class Solution {

public:

string rankTeams(vector<string>& votes) {

const int n = votes[0].length();

string ans(votes[0]);

vector<vector<int>> rank(26, vector<int>(n));

for (const auto& vote : votes)

for (int i = 0; i < n; ++i)

++rank[vote[i] - 'A'][i];

sort(begin(ans), end(ans), [&](const char i, const char j) {

if (rank[i - 'A'] != rank[j - 'A']) return rank[i - 'A'] > rank[j - 'A'];

return i < j;

});

return ans;

}

};

花花酱 LeetCode 1367. Linked List in Binary Tree

By zxi on March 1, 2020

Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

1 <= node.val <= 100 for each node in the linked list and binary tree.
The given linked list will contain between 1 and 100 nodes.
The given binary tree will contain between 1 and 2500 nodes.

Solution: Recursion

We need two recursion functions: isSubPath / isPath, the later one does a strict match.

Time complexity: O(|L| * |T|)
Space complexity: O(|T|)

C++

class Solution {

public:

bool isSubPath(ListNode* head, TreeNode* root) {

if (!root) return false;

return isPath(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);

}

private:

bool isPath(ListNode* head, TreeNode* root) {

if (!head) return true;

if (!root) return false;

if (root->val != head->val) return false;

return isPath(head->next, root->left) || isPath(head->next, root->right);

}

};

花花酱 LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid

By zxi on February 29, 2020

Given a m x ngrid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some invalid signs on the cells of the grid which points outside the grid.

You will initially start at the upper left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path doesn’t have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.

Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).

Example 3:

Input: grid = [[1,2],[4,3]]
Output: 1

Example 4:

Input: grid = [[2,2,2],[2,2,2]]
Output: 3

Example 5:

Input: grid = [[4]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100

Solution 1: Lazy BFS (fake DP)

dp[i][j] := min steps to reach (i, j)

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

C++

// Author: Huahua

class Solution {

public:

int minCost(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2));

dp[0][0] = 0;

auto solve = [&](int x, int y) {

int& v = dp[y][x];

if (x > 0) v = min(v, dp[y][x - 1] + (grid[y][x - 1] != 1));

if (y > 0) v = min(v, dp[y - 1][x] + (grid[y - 1][x] != 3));

if (x < n - 1) v = min(v, dp[y][x + 1] + (grid[y][x + 1] != 2));

if (y < m - 1) v = min(v, dp[y + 1][x] + (grid[y + 1][x] != 4));

};

// At most m + n steps to propagate the results to (m - 1, n -1).

for (int k = 0; k <= (m + n); ++k) {

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x)

solve(x, y);

for (int y = m - 1; y >= 0; --y)

for (int x = n - 1; x >= 0; --x)

solve(x, y);

}

return dp[m - 1][n - 1];

}

};

C++

// Author: Huahua, 88 ms / 22.9 MB

class Solution {

public:

int minCost(vector<vector<int>>& grid) {

const int m = grid.size();

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

vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2));

dp[0][0] = 0;

while (true) {

auto prev(dp);

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

for (int j = 0; j < n; ++j) {

if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (grid[i - 1][j] != 3));

if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (grid[i][j - 1] != 1));

}

for (int i = m - 1; i >= 0; --i)

for (int j = n - 1; j >= 0; --j) {

if (i != m - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + (grid[i + 1][j] != 4));

if (j != n - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + (grid[i][j + 1] != 2));

}

if (prev == dp) break; // optimal solution obtained.

}

return dp[m - 1][n - 1];

}

};

Solution 2: 0-1 BFS

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

C++

// Author: Huahua

class Solution {

public:

int minCost(vector<vector<int>>& grid) {

const int m = grid.size();

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

deque<pair<int, int>> q{{0, 0}};

vector<char> seen(m * n);

vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

while (!q.empty()) {

auto [p, cost] = q.front(); q.pop_front();

int x = p % n, y = p / n;

if (x == n - 1 && y == m - 1) return cost;

if (seen[p]++) continue;

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

int tx = x + dirs[i][0], ty = y + dirs[i][1];

int tp = ty * n + tx;

if (tx < 0 || ty < 0 || tx >= n || ty >= m || seen[tp]) continue;

if (grid[y][x] == i + 1)

q.emplace_front(tp, cost);

else

q.emplace_back(tp, cost + 1);

}

return -1;

}

};

花花酱 LeetCode 1348. Tweet Counts Per Frequency

By zxi on February 29, 2020

Implement the class TweetCounts that supports two methods:

1. recordTweet(string tweetName, int time)

Stores the tweetName at the recorded time (in seconds).

2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)

Returns the total number of occurrences for the given tweetName per minute, hour, or day (depending on freq) starting from the startTime (in seconds) and ending at the endTime (in seconds).
freq is always minute, hour or day, representing the time interval to get the total number of occurrences for the given tweetName.
The first time interval always starts from the startTime, so the time intervals are [startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)> for some non-negative number i and delta (which depends on freq).

Example:

Input
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

Output
[null,null,null,null,[2]
[2,1],null,[4]]

Explanation
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);                             // All tweets correspond to "tweet3" with recorded times at 0, 10 and 60.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]. The frequency is per minute (60 seconds), so there is one interval of time: 1) [0, 60> - > 2 tweets.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2, 1]. The frequency is per minute (60 seconds), so there are two intervals of time: 1) [0, 60> - > 2 tweets, and 2) [60,61> - > 1 tweet.
tweetCounts.recordTweet("tweet3", 120);                            // All tweets correspond to "tweet3" with recorded times at 0, 10, 60 and 120.
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // return [4]. The frequency is per hour (3600 seconds), so there is one interval of time: 1) [0, 211> - > 4 tweets.

Constraints:

There will be at most 10000 operations considering both recordTweet and getTweetCountsPerFrequency.
0 <= time, startTime, endTime <= 10^9

Solution: Hashtable + binary search

Time complexity:
Record: O(logn)
getCount: O(logn + |entries|)

Space complexity: O(n)

C++

// Author: Huahua

class TweetCounts {

public:

TweetCounts() {

m_.clear();

}

void recordTweet(string tweetName, int time) {

m_[tweetName].insert(time);

}

vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {

auto tit = m_.find(tweetName);

if (tit == m_.end()) return {};

const set<int>& s = tit->second;

int delta = 1;

if (freq == "minute") delta = 60;

else if (freq == "hour") delta = 60 * 60;

else if (freq == "day") delta = 60 * 60 * 24;

int slots = (endTime - startTime + delta - 1) / delta;

vector<int> ans(slots);

for (int i = startTime; i <= endTime; i += delta) {

auto it1 = s.lower_bound(i);

auto it2 = s.lower_bound(min(i + delta, endTime + 1));

ans.push_back(distance(it1, it2)); // O(|entries|)

}

return ans;

}

private:

unordered_map<string, set<int>> m_;

};

花花酱 LeetCode 1363. Largest Multiple of Three

By zxi on February 23, 2020

Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

Example 4:

Input: digits = [0,0,0,0,0,0]
Output: "0"

Constraints:

1 <= digits.length <= 10^4
0 <= digits[i] <= 9
The returning answer must not contain unnecessary leading zeros.

Solution: Greedy + Math + Counting sort

Count the numbers of each digit.
if sum % 3 == 0, we can use all digits.
if sum % 1 == 0, we can remove one digits among {1, 4, 7} => sum % 3 == 0
if sum % 2 == 0, we can remove one digits among {2, 5, 8} => sum % 3 == 0
if sum % 2 == 0, we have to remove two digits among {1, 4, 7} => sum % 3 == 0
if sum % 1 == 0, we have to remove two digits among {2, 5, 8} => sum % 3 == 0

Time complexity: O(n)
Space complexity: O(n) w/ output, O(1) w/o output

C++

// Author: Huahua

class Solution {

public:

string largestMultipleOfThree(vector<int>& digits) {

vector<int> c(10);

for (int d : digits) ++c[d];

auto getNum = [&](const vector<int>& ds) {

for (int d : ds) --c[d];

string ans;

for (int d = 9; d >= 1; --d) ans.append(c[d], '0' + d);

ans.append(ans.empty() ? min(1, c[0]) : c[0], '0');

return ans;

};

const int r = accumulate(begin(digits), end(digits), 0) % 3;

vector<vector<int>> rs{{0, 3, 6, 9}, {1, 4, 7}, {2, 5, 8}};

// Use all digitis.

if (r == 0) return getNum({});

// Remove one among {1, 4, 7}, {2, 5, 8}

for (int d : rs[r]) if (c[d]) return getNum({d});

// Remove two among {1, 4, 7}^2 (r = 2), {2, 5, 8}^2 (r = 1)

for (int d1 : rs[3 - r])

for (int d2 : rs[3 - r])

if (d1 == d2 && c[d1] > 1 || d1 != d2 && c[d1] && c[d2])

return getNum({d1, d2});

return "";

}

};

Python3

# Author: Huahua

class Solution:

def largestMultipleOfThree(self, digits: List[int]) -> str:

c = collections.Counter(digits)

def getNum(ds):

ans = []

for d in ds: c[d] -= 1

for d in range(9, 0, -1): ans += [d] * c[d]

ans += [0] * min(1 if not ans else c[0], c[0])

return ''.join(map(str, ans))

rs = [[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]]

r = sum(digits) % 3

if r == 0: return getNum([])

for d in rs[r]:

if c[d] > 0: return getNum([d])

for d1, d2 in zip(rs[3 - r], rs[3 - r]):

if d1 == d2 and c[d1] >= 2 or d1 != d2 and c[d1] and c[d2]:

return getNum([d1, d2])

return ""

Huahua's Tech Road

花花酱 LeetCode 1366. Rank Teams by Votes

Solution: Sort by rank

C++

花花酱 LeetCode 1367. Linked List in Binary Tree

Solution: Recursion

C++

花花酱 LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid

Solution 1: Lazy BFS (fake DP)

C++

C++

Solution 2: 0-1 BFS

C++

花花酱 LeetCode 1348. Tweet Counts Per Frequency

Solution: Hashtable + binary search

C++

花花酱 LeetCode 1363. Largest Multiple of Three

C++

Python3