Huahua’s Tech Road

花花酱 LeetCode 1144. Decrease Elements To Make Array Zigzag

By zxi on August 4, 2019

Given an array nums of integers, a move consists of choosing any element and decreasing it by 1.

An array A is a zigzag array if either:

Every even-indexed element is greater than adjacent elements, ie. A[0] > A[1] < A[2] > A[3] < A[4] > ...
OR, every odd-indexed element is greater than adjacent elements, ie. A[0] < A[1] > A[2] < A[3] > A[4] < ...

Return the minimum number of moves to transform the given array nums into a zigzag array.

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: We can decrease 2 to 0 or 3 to 1.

Example 2:

Input: nums = [9,6,1,6,2]
Output: 4

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 1000

Solution: Greedy

One pass, making each element local minimum.

[9,6,1,6,2]
i = 0, [inf, 9, 6], 9 => 5, even cost 4
i = 1, [9, 6, 1], 6 => 0, odd cost 6
i = 2, [6, 1, 6], 1 => 1, even cost 0
i = 3, [1, 6, 2], 6 => 0, odd cost 12
i = 4, [6, 2, inf], 2 => 2, even cost 0
total even cost 4, new array => [5, 6, 1, 6, 2]
total odd cost 18, new array => [9, 0, 1, 0, 2]

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

C++

// Author: Huahua

class Solution {

public:

int movesToMakeZigzag(vector<int>& nums) {

const int n = nums.size();

vector<int> moves(2);

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

int l = i == 0 ? INT_MAX : nums[i - 1];

int r = i == n - 1 ? INT_MAX : nums[i + 1];

moves[i % 2] += max(0, nums[i] - min(l, r) + 1);

}

return min(moves[0], moves[1]);

}

};

花花酱 LeetCode 1140. Stone Game II

By zxi on July 27, 2019

Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Constraints:

1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

Solution: Recursion + Memoization

def solve(s, m) = max diff score between two players starting from s for the given M.

cache[s][M] = max{sum(piles[s:s+x]) – solve(s+x, max(x, M)}, 1 <= x <= 2*M, s + x <= n

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

C++

// Author: Huahua, 12 ms / 9.7 MB

class Solution {

public:

int stoneGameII(vector<int>& piles) {

const int n = piles.size();

unordered_map<int, int> cache;

// Maximum diff starting from piles[s] given M.

function<int(int, int)> solve = [&](int s, int M) {

if (s >= n) return 0;

const int key = (s << 8) | M;

if (cache.count(key)) return cache[key];

int best = INT_MIN;

int curr = 0;

for (int x = 1; x <= 2 * M; ++x) {

if (s + x > n) break;

curr += piles[s + x - 1];

best = max(best, curr - solve(s + x, max(x, M)));

}

return cache[key] = best;

};

int total = accumulate(begin(piles), end(piles), 0);

return (total + solve(0, 1)) / 2;

}

};

花花酱 LeetCode 1139. Largest 1-Bordered Square

By zxi on July 27, 2019

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn’t exist in the grid.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] is 0 or 1

Solution: DP

Compute the sums of all rectangles that has left-top corner at (0, 0) in O(m*n) time.
For each square and check whether its borders are all ones in O(1) time.

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

C++

// Author: Huahua

class Solution {

public:

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

int n = grid.size();

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

vector<vector<int>> dp(n + 1, vector<int>(m + 1));

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

for (int j = 1; j <= m; ++j)

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + grid[i - 1][j - 1];

for (int len = min(n, m); len > 0; --len)

for (int x1 = 1, x2 = x1 + len - 1; x2 <= m; ++x1, ++x2)

for (int y1 = 1, y2 = y1 + len - 1; y2 <= n; ++y1, ++y2)

if (getArea(x1, y1, x2, y1, dp) == len

&& getArea(x1, y1, x1, y2, dp) == len

&& getArea(x1, y2, x2, y2, dp) == len

&& getArea(x2, y1, x2, y2, dp) == len)

return len * len;

return 0;

}

private:

int getArea(int x1, int y1, int x2, int y2, const vector<vector<int>>& dp) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

}

};

花花酱 LeetCode 1137. N-th Tribonacci Number

By zxi on July 27, 2019

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Solution: DP

Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua

class Solution {

public:

int tribonacci(int n) {

if (n == 0) return n;

int t0 = 0;

int t1 = 1;

int t2 = 1;

int t = 1;

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

t = t0 + t1 + t2;

t0 = t1;

t1 = t2;

t2 = t;

}

return t;

}

};

花花酱 LeetCode 1138. Alphabet Board Path

By zxi on July 27, 2019

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].

We may make the following moves:

'U' moves our position up one row, if the square exists;
'D' moves our position down one row, if the square exists;
'L' moves our position left one column, if the square exists;
'R' moves our position right one column, if the square exists;
'!' adds the character board[r][c] at our current position (r, c) to the answer.

Return a sequence of moves that makes our answer equal to target in the minimum number of moves. You may return any path that does so.

Example 1:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Example 2:

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

Constraints:

1 <= target.length <= 100
target consists only of English lowercase letters.

Solution: Manhattan walk

Compute the coordinates of each char, walk from (x1, y1) to (x2, y2) in Manhattan way.
Be aware of the last row, we can only walk on ‘z’, so go left and up first if needed.

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

C++

// Author: Huahua

class Solution {

public:

string alphabetBoardPath(string target) {

vector<vector<string>> paths(26, vector<string>(26));

for (int s = 0; s < 26; ++s)

for (int t = 0; t < 26; ++t) {

int dx = t % 5 - s % 5;

int dy = t / 5 - s / 5;

string path;

while (dx < 0) { path.push_back('L'); dx++; }

while (dy < 0) { path.push_back('U'); dy++; }

while (dx > 0) { path.push_back('R'); dx--; }

while (dy > 0) { path.push_back('D'); dy--; }

paths[s][t] = path;

}

char l = 'a';

string ans;

for (char c : target) {

ans += paths[l - 'a'][c - 'a'] + "!";

l = c;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1144. Decrease Elements To Make Array Zigzag

Solution: Greedy

C++

花花酱 LeetCode 1140. Stone Game II

Solution: Recursion + Memoization

C++

花花酱 LeetCode 1139. Largest 1-Bordered Square

Solution: DP

C++

花花酱 LeetCode 1137. N-th Tribonacci Number

Solution: DP

C++

花花酱 LeetCode 1138. Alphabet Board Path

Solution: Manhattan walk

C++