Huahua’s Tech Road

花花酱 LeetCode 1444. Number of Ways of Cutting a Pizza

By zxi on May 15, 2020

Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell) and given the integer k. You have to cut the pizza into k pieces using k-1 cuts.

For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.

Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: pizza = ["A..","AAA","..."], k = 3
Output: 3 
Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.

Example 2:

Input: pizza = ["A..","AA.","..."], k = 3
Output: 1

Example 3:

Input: pizza = ["A..","A..","..."], k = 1
Output: 1

Constraints:

1 <= rows, cols <= 50
rows == pizza.length
cols == pizza[i].length
1 <= k <= 10
pizza consists of characters 'A' and '.' only.

Solution: DP

dp(n, m, k) := # of ways to cut pizza[n:N][m:M] with k cuts.

dp(n, m, k) = sum(hasApples(n, m, N – 1, y) * dp(y + 1, n, k – 1) for y in range(n, M)) + sum(hasApples(n, m, x, M – 1) * dp(m, x + 1, k – 1) for x in range(n, M))

Time complexity: O(M*N*(M+N)*K) = O(N^3 * K)
Space complexity: O(M*N*K)

C++

// Author: Huahua

class Solution {

public:

int ways(vector<string>& pizza, int K) {

constexpr int kMod = 1e9 + 7;

const int M = pizza.size();

const int N = pizza[0].size();

vector<vector<int>> A(M + 1, vector<int>(N + 1));

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

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

A[y + 1][x + 1] = A[y + 1][x] + A[y][x + 1] + (pizza[y][x] == 'A') - A[y][x];

auto hasApples = [&](int x1, int y1, int x2, int y2) {

return (A[y2 + 1][x2 + 1] - A[y2 + 1][x1] - A[y1][x2 + 1] + A[y1][x1]) > 0;

};

vector<vector<vector<int>>> cache(M, vector<vector<int>>(N, vector<int>(K, -1)));

// dp(m, n, k) := # of ways to cut pizza[m:M][n:N] with k cuts.

function<int(int, int, int)> dp = [&](int m, int n, int k) -> int {

if (k == 0) return hasApples(n, m, N - 1, M - 1);

int& ans = cache[m][n][k];

if (ans != -1) return ans;

ans = 0;

for (int y = m; y < M - 1; ++y) // Cut horizontally.

ans = (ans + hasApples(n, m, N - 1, y) * dp(y + 1, n, k - 1)) % kMod;

for (int x = n; x < N - 1; ++x) // Cut vertically.

ans = (ans + hasApples(n, m, x, M - 1) * dp(m, x + 1, k - 1)) % kMod;

return ans;

};

return dp(0, 0, K - 1);

}

};

花花酱 LeetCode 1442. Count Triplets That Can Form Two Arrays of Equal XOR

By zxi on May 11, 2020

Given an array of integers arr.

We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).

Let’s define a and b as follows:

a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j and k) Where a == b.

Example 1:

Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2:

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

Example 3:

Input: arr = [2,3]
Output: 0

Example 4:

Input: arr = [1,3,5,7,9]
Output: 3

Example 5:

Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8

Constraints:

1 <= arr.length <= 300
1 <= arr[i] <= 10^8

Solution 1: Brute Force (TLE)

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

C++

// Author: Huahua

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

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

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

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

int a = 0;

int b = 0;

for (int t = i; t < j; ++t)

a ^= arr[t];

for (int t = j; t <= k; ++t)

b ^= arr[t];

if (a == b) ++ans;

}

return ans;

}

};

Solution 2: Prefix XORs

Let xors[i] = arr[0] ^ arr[1] ^ … ^ arr[i-1]
arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1] = (arr[0] ^ … ^ arr[j – 1]) ^ (arr[0] ^ … ^ arr[i-1]) = xors[j] ^ xors[i]

We then can compute a and b in O(1) time.

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

C++

// Author: Huahua, 232 ms

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

vector<int> xors(n + 1);

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

xors[i + 1] = xors[i] ^ arr[i];

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

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

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

const int a = xors[j] ^ xors[i];

const int b = xors[k + 1] ^ xors[j];

if (a == b) ++ans;

}

return ans;

}

};

Solution 3: Prefix XORs II

a = arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
a == b => a ^ b == 0
XORs(i ~ k) == 0
XORS(0 ~ k) ^ XORs(0 ~ i – 1) = 0

Problem => find all pairs of (i – 1, k) such that xors[k+1] == xors[i]
For each pair (i – 1, k), there are k – i positions we can insert j.

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

C++

// Author: Huahua

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

vector<int> xors(n + 1);

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

xors[i + 1] = xors[i] ^ arr[i];

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

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

if (xors[k + 1] == xors[i])

ans += k - i;

return ans;

}

};

Solution 3: HashTable

Similar to target sum, use a hashtable to store the frequency of each prefix xors.

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

C++

// Author: Huahua

// Author: Huahua 4 ms

class Solution {

public:

int countTriplets(vector<int>& arr) {

const int n = arr.size();

int ans = 0;

unordered_map<int, int> freq{{0, 1}};

unordered_map<int, int> sum;

int X = 0;

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

X ^= arr[i];

ans += freq[X] * i - sum[X];

++freq[X];

sum[X] += i + 1;

}

return ans;

}

};

花花酱 LeetCode 1441. Build an Array With Stack Operations

By zxi on May 11, 2020

Given an array target and an integer n. In each iteration, you will read a number from list = {1,2,3..., n}.

Build the target array using the following operations:

Push: Read a new element from the beginning list, and push it in the array.
Pop: delete the last element of the array.
If the target array is already built, stop reading more elements.

You are guaranteed that the target array is strictly increasing, only containing numbers between 1 to n inclusive.

Return the operations to build the target array.

You are guaranteed that the answer is unique.

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: 
Read number 1 and automatically push in the array -> [1]
Read number 2 and automatically push in the array then Pop it -> [1]
Read number 3 and automatically push in the array -> [1,3]

Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]

Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: You only need to read the first 2 numbers and stop.

Example 4:

Input: target = [2,3,4], n = 4
Output: ["Push","Pop","Push","Push","Push"]

Constraints:

1 <= target.length <= 100
1 <= target[i] <= 100
1 <= n <= 100
target is strictly increasing.

Solution: Simulation

For each number in target, keep discarding i if i != num by “Push” + “Pop”, until i == num. One more “Push”.

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

C++

// Author: Huahua

class Solution {

public:

vector<string> buildArray(vector<int>& target, int n) {

vector<string> ans;

int i = 1;

for (int num : target) {

while (i != num) {

ans.push_back("Push");

ans.push_back("Pop");

++i;

}

ans.push_back("Push");

++i;

}

return ans;

}

};

花花酱 LeetCode 1443. Minimum Time to Collect All Apples in a Tree

By zxi on May 10, 2020

Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend in order to collect all apples in the tree starting at vertex 0 and coming back to this vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [from_i, to_i] means that exists an edge connecting the vertices from_i and to_i. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple, otherwise, it does not have any apple.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8 
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

Example 2:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Output: 6
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

Example 3:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
Output: 0

Constraints:

1 <= n <= 10^5
edges.length == n-1
edges[i].length == 2
0 <= from_i, to_i <= n-1
from_i < to_i
hasApple.length == n

Solution: DFS

Build the graph (tree) and DFS.

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

C++

// Author: Huahua

class Solution {

public:

int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {

vector<vector<int>> g(n);

for (const auto& e : edges)

g[e[0]].push_back(e[1]);

function<int(int)> dfs = [&] (int cur) {

int total = 0;

for (int nxt : g[cur]) {

int cost = dfs(nxt);

if (cost > 0 || hasApple[nxt]) total += 2 + cost;

}

return total;

};

return dfs(0);

}

};

if edge is not ordered

C++

// Author: Huahua

class Solution {

public:

int minTime(int n, vector<vector<int>>& edges,

vector<bool>& hasApple) {

vector<vector<int>> g(n);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n);

function<int(int)> dfs = [&] (int cur) {

seen[cur] = 1;

int total = 0;

for (int child : g[cur]) {

if (seen[child]) continue;

int cost = dfs(child);

if (cost > 0 || hasApple[child])

total += 2 + cost;

}

return total;

};

return dfs(0);

}

};

玩转Linux命令行 – 事件处理 – EP3

By zxi on May 8, 2020

Download Data

download.sh

for i in $(seq -w 01 80)

curl -O -J https://raw.githubusercontent.com/rozim/ChessData/master/mega2400_part_${i}.pgn

done

V1

1	cat *.pgn \| grep "Result" \| sort \| uniq -c

V2

1	cat *.pgn \| grep "Result" \| awk '{ split($0, a, "-"); res = substr(a[1], length(a[1]), 1); if (res == 1) white++; if (res == 0) black++; if (res == 2) draw++;} END { print white+black+draw, white, black, draw }'

V3

find . -type f -name '*.pgn' -print0 | xargs -0 -n1 -P8 mawk '/Result/ { split($0, a, "-"); res = substr(a[1], length(a[1]), 1); if (res == 1) white++; if (res == 0) black++; if (res == 2) draw++ } END { print white+black+draw, white, black, draw }' | awk '{games += $1; white += $2; black += $3; draw += $4; } END { print games, white, black, draw }'