Huahua’s Tech Road

花花酱 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 }'

花花酱 LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

By zxi on May 5, 2020

You are given an m * n matrix, mat, and an integer k, which has its rows sorted in non-decreasing order.

You are allowed to choose exactly 1 element from each row to form an array. Return the Kth smallest array sum among all possible arrays.

Example 1:

Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.

Example 2:

Input: mat = [[1,3,11],[2,4,6]], k = 9
Output: 17

Example 3:

Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
Output: 9
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.

Example 4:

Input: mat = [[1,1,10],[2,2,9]], k = 7
Output: 12

Constraints:

m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] is a non decreasing array.

Solution 1: Priority Queue

Generate the arrays in order.

Each node is {sum, idx_0, idx_1, …, idx_m},

Start with {sum_0, 0, 0, …, 0}.

For expansion, pick one row and increase its index

Time complexity: O(k * m ^ 2* log k)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

int kthSmallest(vector<vector<int>>& mat, int k) {

const int m = mat.size();

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

priority_queue<vector<int>> q;

vector<int> node(m + 1); // {-sum, idx_0, idx_1, ..., idx_m}

for (int i = 0; i < m; ++i) node[0] -= mat[i][0];

q.push(node);

set<vector<int>> seen{{node}};

while (!q.empty()) {

const vector<int> cur = q.top(); q.pop();

if (--k == 0) return -cur[0];

for (int i = 1; i <= m; ++i) {

if (cur[i] == n - 1) continue;

vector<int> nxt(cur);

++nxt[i]; // increase i-th row's index.

// Update sum.

nxt[0] -= (mat[i - 1][nxt[i]] - mat[i - 1][nxt[i] - 1]);

if (!seen.insert(nxt).second) continue;

q.push(move(nxt));

}

return -1;

}

};

Huahua's Tech Road

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

Solution 1: Brute Force (TLE)

C++

Solution 2: Prefix XORs

C++

Solution 3: Prefix XORs II

C++

Solution 3: HashTable

C++

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

Solution: Simulation

C++

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

Solution: DFS

C++

if edge is not ordered

C++

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

Download Data

download.sh

V1

V2

V3

花花酱 LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

Solution 1: Priority Queue

C++