Huahua's Tech Road

花花酱 LeetCode 1563. Stone Game V

By zxi on August 23, 2020

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice’s score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice’s is initially zero.

Return the maximum score that Alice can obtain.

Example 1:

Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.

Example 2:

Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28

Example 3:

Input: stoneValue = [4]
Output: 0

Constraints:

1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10^6

Solution: Range DP + Prefix Sum

dp[l][r] := max store Alice can get from range [l, r]
sum_l = sum(l, k), sum_r = sum(k + 1, r)
dp[l][r] = max{
dp[l][k] + sum_l if sum_l < sum_r
dp[k+1][r] + sum_r if sum_r < sum_l
max(dp[l][k], dp[k+1][r])) + sum_l if sum_l == sum_r)
} for k in [l, r)

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

C++

class Solution {

public:

int stoneGameV(vector<int>& stoneValue) {

const int n = stoneValue.size();

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stoneValue[i];

vector<vector<int>> cache(n, vector<int>(n, -1));

// max value alice can get from range [l, r]

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

if (l == r) return 0;

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

if (ans != -1) return ans;

for (int k = l; k < r; ++k) {

// left: [l, k], right: [k + 1, r]

int sum_l = sums[k + 1] - sums[l];

int sum_r = sums[r + 1] - sums[k + 1];

if (sum_l > sum_r)

ans = max(ans, sum_r + dp(k + 1, r));

else if (sum_l < sum_r)

ans = max(ans, sum_l + dp(l, k));

else

ans = max(ans, sum_l + max(dp(l, k), dp(k + 1, r)));

}

return ans;

};

return dp(0, n - 1);

}

};

花花酱 LeetCode 1562. Find Latest Group of Size M

By zxi on August 23, 2020

Given an array arr that represents a permutation of numbers from 1 to n. You have a binary string of size n that initially has all its bits set to zero.

At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1. You are given an integer m and you need to find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1s such that it cannot be extended in either direction.

Return the latest step at which there exists a group of ones of length exactly m. If no such group exists, return -1.

Example 1:

Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.

Example 2:

Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.

Example 3:

Input: arr = [1], m = 1
Output: 1

Example 4:

Input: arr = [2,1], m = 2
Output: 2

Constraints:

n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= n
All integers in arr are distinct.
1 <= m <= arr.length

Solution: Hashtable

Similar to LC 128

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

C++

// Author: Huahua

class Solution {

public:

int findLatestStep(vector<int>& arr, int m) {

const int n = arr.size();

vector<int> len(n + 2);

vector<int> counts(n + 2);

int ans = -1;

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

const int x = arr[i];

const int l = len[x - 1];

const int r = len[x + 1];

const int t = 1 + l + r;

len[x - l] = len[x + r] = t;

--counts[l];

--counts[r];

++counts[t];

if (counts[m]) ans = i + 1;

}

return ans;

}

};

花花酱 LeetCode 1561. Maximum Number of Coins You Can Get

By zxi on August 23, 2020

There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

In each step, you will choose any 3 piles of coins (not necessarily consecutive).
Of your choice, Alice will pick the pile with the maximum number of coins.
You will pick the next pile with maximum number of coins.
Your friend Bob will pick the last pile.
Repeat until there are no more piles of coins.

Given an array of integers piles where piles[i] is the number of coins in the i^th pile.

Return the maximum number of coins which you can have.

Example 1:

Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.

Example 2:

Input: piles = [2,4,5]
Output: 4

Example 3:

Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18

Constraints:

3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4

Solution: Greedy

Always take the second largest element of a in the sorted array.
[1, 2, 3, 4, 5, 6, 7, 8, 9]
tuples: (1, 8, 9), (2, 6, 7), (3, 4, 5)
Alice: 9, 7, 5
You: 8, 6, 4
Bob: 1, 2, 3

Time complexity: O(nlogn) -> O(n + k)
Space complexity: O(1)

C++

class Solution {

public:

int maxCoins(vector<int>& piles) {

const int n = piles.size() / 3;

sort(begin(piles), end(piles));

int ans = 0;

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

ans += piles[n * 3 - 2 - i * 2];

return ans;

}

};

C++ counting sort

class Solution {

public:

int maxCoins(vector<int>& piles) {

constexpr int kMax = 10000;

const int n = piles.size() / 3;

vector<int> counts(kMax + 1);

for (int v : piles) ++counts[v];

int idx = 0;

for (int i = 1; i <= kMax; ++i)

while (counts[i]--) piles[idx++] = i;

int ans = 0;

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

ans += piles[n * 3 - 2 - i * 2];

return ans;

}

};

花花酱 LeetCode 1560. Most Visited Sector in a Circular Track

By zxi on August 23, 2020

Given an integer n and an integer array rounds. We have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The i^th round starts at sector rounds[i - 1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds[0] and ends at sector rounds[1]

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).

Example 1:

Input: n = 4, rounds = [1,3,1,2]
Output: [1,2]
Explanation: The marathon starts at sector 1. The order of the visited sectors is as follows:
1 --> 2 --> 3 (end of round 1) --> 4 --> 1 (end of round 2) --> 2 (end of round 3 and the marathon)
We can see that both sectors 1 and 2 are visited twice and they are the most visited sectors. Sectors 3 and 4 are visited only once.

Example 2:

Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output: [2]

Example 3:

Input: n = 7, rounds = [1,3,5,7]
Output: [1,2,3,4,5,6,7]

Constraints:

2 <= n <= 100
1 <= m <= 100
rounds.length == m + 1
1 <= rounds[i] <= n
rounds[i] != rounds[i + 1] for 0 <= i < m

Solution: Simulation

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

C++

class Solution {

public:

vector<int> mostVisited(int n, vector<int>& rounds) {

vector<int> counts(n);

counts[rounds[0] - 1] = 1;

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

for (int s = rounds[i - 1]; ; ++s) {

++counts[s %= n];

if (s == rounds[i] - 1) break;

}

const int max_count = *max_element(begin(counts), end(counts));

vector<int> ans;

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

if (counts[i] == max_count) ans.push_back(i + 1);

return ans;

}

};

花花酱 LeetCode 1559. Detect Cycles in 2D Grid

By zxi on August 23, 2020

Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid.

A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it – in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cycle of the same value exists in grid, otherwise, return false.

Example 1:

Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:

Example 2:

Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:

Example 3:

Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid consists only of lowercase English letters.

Solution: DFS

Finding a cycle in an undirected graph => visiting a node that has already been visited and it’s not the parent node of the current node.
b b
b b
null -> (0, 0) -> (0, 1) -> (1, 1) -> (1, 0) -> (0, 0)
The second time we visit (0, 0) which has already been visited before and it’s not the parent of the current node (1, 0) ( (1, 0)’s parent is (1, 1) ) which means we found a cycle.

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

C++

class Solution {

public:

bool containsCycle(vector<vector<char>>& grid) {

const int m = grid.size();

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

vector<vector<int>> seen(m, vector<int>(n));

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

function<bool(int, int, int, int)> dfs = [&](int i, int j, int pi, int pj) {

++seen[i][j];

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

int ni = i + dirs[d];

int nj = j + dirs[d + 1];

if (ni < 0 || nj < 0 || ni >= m || nj >= n) continue;

if (grid[ni][nj] != grid[i][j]) continue;

if (!seen[ni][nj]) {

if (dfs(ni, nj, i, j)) return true;

} else if (ni != pi || nj != pj) {

return true;

}

return false;

};

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

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

if (!seen[i][j]++ && dfs(i, j, -1, -1))

return true;

return false;

}

};