Posts published in August 2019

花花酱 LeetCode 1147. Longest Chunked Palindrome Decomposition

By zxi on August 4, 2019

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

Each a_i is a non-empty string;
Their concatenation a_1 + a_2 + ... + a_k is equal to text;
For all 1 <= i <= k, a_i = a_{k+1 - i}.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

Solution: Greedy

Break the string when the shortest palindrome is found.
prefer to use string_view

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

C++

// Author: Huahua, 0 ms, 8.7 ms

class Solution {

public:

int longestDecomposition(string_view text) {

const int n = text.length();

if (n == 0) return 0;

for (int l = 1; l <= n / 2; ++l) {

if (text.substr(0, l) == text.substr(n - l))

return 2 + longestDecomposition(text.substr(l, n - 2 * l));

}

return 1;

}

};

花花酱 LeetCode 1146. Snapshot Array

By zxi on August 4, 2019

Implement a SnapshotArray that supports the following interface:

SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
void set(index, val) sets the element at the given index to be equal to val.
int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Constraints:

1 <= length <= 50000
At most 50000 calls will be made to set, snap, and get.
0 <= index < length
0 <= snap_id < (the total number of times we call snap())
0 <= val <= 10^9

Solution: map + upper_bound

Use a vector to store maps, one map per element.
The map stores {snap_id -> val}, use upper_bound to find the first version > snap_id and use previous version’s value.

Time complexity:
Set: O(log|snap_id|)
Get: O(log|snap_id|)
Snap: O(1)
Space complexity: O(length + set_calls)

C++

// Author: Huahua

class SnapshotArray {

public:

SnapshotArray(int length): id_(0), vals_(length) {}

void set(int index, int val) {

vals_[index][id_] = val;

}

int snap() { return id_++; }

int get(int index, int snap_id) const {

auto it = vals_[index].upper_bound(snap_id);

if (it == begin(vals_[index])) return 0;

return prev(it)->second;

}

private:

int id_;

vector<map<int, int>> vals_;

};

花花酱 LeetCode 1145. Binary Tree Coloring Game

By zxi on August 4, 2019

Two players play a turn based game on a binary tree. We are given the root of this binary tree, and the number of nodes n in the tree. n is odd, and each node has a distinct value from 1 to n.

Initially, the first player names a value x with 1 <= x <= n, and the second player names a value y with 1 <= y <= n and y != x. The first player colors the node with value x red, and the second player colors the node with value yblue.

Then, the players take turns starting with the first player. In each turn, that player chooses a node of their color (red if player 1, blue if player 2) and colors an uncolored neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)

If (and only if) a player cannot choose such a node in this way, they must pass their turn. If both players pass their turn, the game ends, and the winner is the player that colored more nodes.

You are the second player. If it is possible to choose such a y to ensure you win the game, return true. If it is not possible, return false.

Example 1:

Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
Output: true
Explanation: The second player can choose the node with value 2.

Constraints:

root is the root of a binary tree with n nodes and distinct node values from 1 to n.
n is odd.
1 <= x <= n <= 100

Solution: Count size of red’s subtrees

There are two situations that blue can win.
1. one of the red’s subtree has more than n>>1 nodes. Blue colorize the root of the larger subtree.
2. red and its children has size less or equal to n>>1. Blue colorize red’s parent.

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

C++

// Author: Huahua

class Solution {

public:

bool btreeGameWinningMove(TreeNode* root, int n, int x) {

int red_left;

int red_right;

function<int(TreeNode*)> count = [&](TreeNode* node){

if (!node) return 0;

int l = count(node->left);

int r = count(node->right);

if (root->val == x) {

red_left = l;

red_right = r;

}

return 1 + l + r;

};

count(root);

// Color red's parent.

if (1 + red_left + red_right <= n / 2) return true;

// Color the child that has the larger subtree.

return max(red_left, red_right) > n / 2;

}

};

花花酱 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]);

}

};