sort – Page 4 – Huahua’s Tech Road

花花酱 LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points

By zxi on October 31, 2020

Given n points on a 2D plane where points[i] = [x_i, y_i], Return the widest vertical area between two points such that no points are inside the area.

A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.

Note that points on the edge of a vertical area are not considered included in the area.

Example 1:

Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.

Example 2:

Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
Output: 3

Constraints:

n == points.length
2 <= n <= 10⁵
points[i].length == 2
0 <= x_i, y_i <= 10⁹

Solution: Sort by x coordinates

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

C++

class Solution {

public:

int maxWidthOfVerticalArea(vector<vector<int>>& points) {

sort(begin(points), end(points), [](const auto& p1, const auto& p2) {

return p1[0] != p2[0] ? p1[0] < p2[0] : p1[1] < p2[1];

});

int ans = 0;

for (int i = 1; i < points.size(); ++i)

ans = max(ans, points[i][0] - points[i - 1][0]);

return ans;

}

};

花花酱 LeetCode 1619. Mean of Array After Removing Some Elements

By zxi on October 17, 2020

Given an integer array arr, return the mean of the remaining integers after removing the smallest 5% and the largest 5% of the elements.

Answers within 10^-5 of the actual answer will be considered accepted.

Example 1:

Input: arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
Output: 2.00000
Explanation: After erasing the minimum and the maximum values of this array, all elements are equal to 2, so the mean is 2.

Example 2:

Input: arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
Output: 4.00000

Example 3:

Input: arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
Output: 4.77778

Example 4:

Input: arr = [9,7,8,7,7,8,4,4,6,8,8,7,6,8,8,9,2,6,0,0,1,10,8,6,3,3,5,1,10,9,0,7,10,0,10,4,1,10,6,9,3,6,0,0,2,7,0,6,7,2,9,7,7,3,0,1,6,1,10,3]
Output: 5.27778

Example 5:

Input: arr = [4,8,4,10,0,7,1,3,7,8,8,3,4,1,6,2,1,1,8,0,9,8,0,3,9,10,3,10,1,10,7,3,2,1,4,9,10,7,6,4,0,8,5,1,2,1,6,2,5,0,7,10,9,10,3,7,10,5,8,5,7,6,7,6,10,9,5,10,5,5,7,2,10,7,7,8,2,0,1,1]
Output: 5.29167

Constraints:

20 <= arr.length <= 1000
arr.lengthis a multiple of 20.
0 <= arr[i] <= 10⁵

Solution: Sorting

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

C++

// Author: Huahua

class Solution {

public:

double trimMean(vector<int>& arr) {

sort(begin(arr), end(arr));

const int offset = arr.size() / 20;

const int sum = accumulate(begin(arr) + offset, end(arr) - offset, 0);

return static_cast<double>(sum) / (arr.size() - 2 * offset);

}

};

花花酱 LeetCode 1508. Range Sum of Sorted Subarray Sums

By zxi on July 11, 2020

Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.

Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.

Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

Constraints:

1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

Solution 1: Brute Force

Find sums of all the subarrays and sort the values.

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

C++

// Author: Huahua

class Solution {

public:

int rangeSum(vector<int>& nums, int n, int left, int right) {

constexpr int kMod = 1e9 + 7;

vector<int> sums;

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

for (int j = i, sum = 0; j < n; ++j)

sums.push_back(sum += nums[j]);

sort(begin(sums), end(sums));

return accumulate(begin(sums) + left - 1, begin(sums) + right, 0LL) % kMod;

}

};

Java

// Author: Huahua

class Solution {

public int rangeSum(int[] nums, int n, int left, int right) {

final int kMod = (int)(1e9 + 7);

int[] sums = new int[n * (n + 1) / 2];

int idx = 0;

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

for (int j = i, sum = 0; j < n; ++j, ++idx)

sums[idx] = sum += nums[j];

Arrays.sort(sums);

int ans = 0;

for (int i = left; i <= right; ++i)

ans = (ans + sums[i - 1]) % kMod;

return ans;

}

Python3

# Author: Huahua

class Solution:

def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:

sums = []

for i in range(n):

s = 0

for j in range(i, n):

s += nums[j]

sums.append(s)

sums.sort()

return sum(sums[left - 1:right])

Solution 2: Priority Queue / Min Heap

For each subarray, start with one element e.g nums[i], put them into a priority queue (min heap). Each time, we have the smallest subarray sum, and extend that subarray and put the new sum back into priority queue. Thought it has the same time complexity as the brute force one in worst case, but space complexity can be reduce to O(n).

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

C++

struct Entry {

int sum;

int i;

bool operator<(const Entry& e) const { return sum > e.sum; }

};

class Solution {

public:

int rangeSum(vector<int>& nums, int n, int left, int right) {

constexpr int kMod = 1e9 + 7;

priority_queue<Entry> q; // Sort by e.sum in descending order.

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

q.push({nums[i], i});

long ans = 0;

for (int j = 1; j <= right; ++j) {

const auto e = std::move(q.top()); q.pop();

if (j >= left) ans += e.sum;

if (e.i + 1 < n) q.push({e.sum + nums[e.i + 1], e.i + 1});

}

return ans % kMod;

}

};

Java

import java.util.AbstractMap;

class Solution {

public int rangeSum(int[] nums, int n, int left, int right) {

final int kMod = (int)(1e9 + 7);

var q = new PriorityQueue<Map.Entry<Integer, Integer>>((a, b) -> a.getKey() - b.getKey());

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

q.offer(new AbstractMap.SimpleEntry<>(nums[i], i));

int ans = 0;

for (int k = 1; k <= right; ++k) {

var e = q.poll();

int sum = e.getKey();

int i = e.getValue();

if (k >= left)

ans = (ans + sum) % kMod;

if (i + 1 < n)

q.offer(new AbstractMap.SimpleEntry<>(sum + nums[i + 1], i + 1));

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:

q = [(num, i) for i, num in enumerate(nums)]

heapq.heapify(q)

ans = 0

for k in range(1, right + 1):

s, i = heapq.heappop(q)

if k >= left:

ans += s

if i + 1 < n:

heapq.heappush(q, (s + nums[i + 1], i + 1))

return ans % int(1e9 + 7)

Solution 3: Binary Search + Sliding Window

Use binary search to find S s.t. that there are at least k subarrys have sum <= S.

Given S, we can use sliding window to count how many subarrays have sum <= S and their total sum.

ans = sums_of_first(right) – sums_of_first(left – 1).

Time complexity: O(n * log(sum(nums))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int rangeSum(vector<int>& nums, int n, int left, int right) {

constexpr int kMod = 1e9 + 7;

// Returns number of subarrays that have

// sum <= target and their total sum.

auto countAndSum = [&](int target) -> pair<int, long> {

int count = 0;

long cur = 0;

long sum = 0;

long total_sum = 0;

for (long j = 0, i = 0; j < n; ++j) {

cur += nums[j];

sum += nums[j] * (j - i + 1);

while (cur > target) {

sum -= cur;

cur -= nums[i++];

}

count += j - i + 1;

total_sum += sum;

}

return {count, total_sum};

};

// Returns the total sums of smallest k subarrays.

// Use binary search to find the smallest sum l s.t.

// there are at least k of subarrays have sums <= l.

const int min_sum = *min_element(begin(nums), end(nums));

const int max_sum = accumulate(begin(nums), end(nums), 0) + 1;

auto sumOfFirstK = [&](int k) -> long {

int l = min_sum;

int r = max_sum;

while (l < r) {

int mid = l + (r - l) / 2;

if (countAndSum(mid).first >= k)

r = mid;

else

l = mid + 1;

}

const auto [count, sum] = countAndSum(l);

// There can be more subarrays have the same sum of l.

return sum - l * (count - k);

};

return (sumOfFirstK(right) - sumOfFirstK(left - 1)) % kMod;

}

};

花花酱 LeetCode 1481. Least Number of Unique Integers after K Removals

By zxi on June 14, 2020

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

Solution: Greedy

Count the frequency of each unique number. Sort by frequency, remove items with lowest frequency first.

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

C++

// Author: Huahua

class Solution {

public:

int findLeastNumOfUniqueInts(vector<int>& arr, int k) {

unordered_map<int, int> c;

for (int x : arr) ++c[x];

vector<int> m; // freq

for (const auto [x, f] : c)

m.push_back(f);

sort(begin(m), end(m));

int ans = m.size();

int i = 0;

while (k--) {

if (--m[i] == 0) {

++i;

--ans;

}

return ans;

}

};

玩转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 }'