Huahua's Tech Road

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

}

};

花花酱 LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

By zxi on May 3, 2020

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

Solution 1: Sliding Window + TreeSet

Use a treeset to maintain a range of [l, r] such that max(nums[l~r]) – min(nums[l~r]) <= limit.
Every time, we add nums[r] into the tree, and move l towards r to keep the max diff under limit.

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

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums, int limit) {

multiset<int> s;

int l = 0;

int ans = 0;

for (int r = 0; r < nums.size(); ++r) {

s.insert(nums[r]);

while (*rbegin(s) - *begin(s) > limit)

s.erase(s.equal_range(nums[l++]).first);

ans = max(ans, r - l + 1);

}

return ans;

}

};

Solution 2: Dual Monotonic Queue

We want to maintain a range [l, r] that max(nums[l~r]) – min(nums[l~r]) <= limit, to track the max/min of a range efficiently we could use monotonic queue. One for max and one for min.

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

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums, int limit) {

deque<int> max_q;

deque<int> min_q;

int ans = 0;

int l = 0;

for (int r = 0; r < nums.size(); ++r) {

while (!min_q.empty() && nums[r] < min_q.back())

min_q.pop_back();

while (!max_q.empty() && nums[r] > max_q.back())

max_q.pop_back();

min_q.push_back(nums[r]);

max_q.push_back(nums[r]);

while (max_q.front() - min_q.front() > limit) {

if (max_q.front() == nums[l]) max_q.pop_front();

if (min_q.front() == nums[l]) min_q.pop_front();

++l;

}

ans = max(ans, r - l + 1);

}

return ans;

}

};

花花酱 LeetCode 1437. Check If All 1’s Are at Least Length K Places Away

By zxi on May 3, 2020

Given an array nums of 0s and 1s and an integer k, return True if all 1’s are at least k places away from each other, otherwise return False.

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Example 3:

Input: nums = [1,1,1,1,1], k = 0
Output: true

Example 4:

Input: nums = [0,1,0,1], k = 1
Output: true

Constraints:

1 <= nums.length <= 10^5
0 <= k <= nums.length
nums[i] is 0 or 1

Solution: Scan the array

Only need to check adjacent ones. This problem should be easy instead of medium.

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

C++

// Author: Huahua

class Solution {

public:

bool kLengthApart(vector<int>& nums, int k) {

int d = k + 1; // distant enough

for (int n : nums) {

if (n == 0) {

++d;

} else {

if (d < k) return false;

d = 0;

}

return true;

}

};