Huahua’s Tech Road

花花酱 LeetCode 1679. Max Number of K-Sum Pairs

By zxi on December 6, 2020

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

Solution 1: Frequency Map

For each x, check freq[x] and freq[k – x]. Note: there is a special case when x + x == k.

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

C++

class Solution {

public:

int maxOperations(vector<int>& nums, int k) {

unordered_map<int, int> m;

int ans = 0;

for (int x : nums) ++m[x];

for (int x : nums) {

if (m[x] < 1 || m[k - x] < 1 + (x + x == k)) continue;

--m[x];

--m[k - x];

++ans;

}

return ans;

}

};

Python3

class Solution:

def maxOperations(self, nums: List[int], k: int) -> int:

m = defaultdict(int)

ans = 0

for x in nums: m[x] += 1

for x in nums:

if m[x] < 1 or m[k - x] < 1 + (x + x == k): continue

m[x] -= 1

m[k - x] -= 1

ans += 1

return ans

Solution 2: Two Pointers

Sort the number, start from i = 0, j = n – 1, compare s = nums[i] + nums[j] with k and move i, j accordingly.

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

C++

class Solution {

public:

int maxOperations(vector<int>& nums, int k) {

sort(begin(nums), end(nums));

int i = 0, j = nums.size() - 1;

int ans = 0;

while (i < j) {

const int s = nums[i] + nums[j];

if (s == k) {

++ans;

++i; --j;

} else if (s < k) {

++i;

} else {

--j;

}

return ans;

}

};

花花酱 LeetCode 1678. Goal Parser Interpretation

By zxi on December 5, 2020

You own a Goal Parser that can interpret a string command. The command consists of an alphabet of "G", "()" and/or "(al)" in some order. The Goal Parser will interpret "G" as the string "G", "()" as the string "o", and "(al)" as the string "al". The interpreted strings are then concatenated in the original order.

Given the string command, return the Goal Parser‘s interpretation of command.

Example 1:

Input: command = "G()(al)"
Output: "Goal"
Explanation: The Goal Parser interprets the command as follows:
G -> G
() -> o
(al) -> al
The final concatenated result is "Goal".

Example 2:

Input: command = "G()()()()(al)"
Output: "Gooooal"

Example 3:

Input: command = "(al)G(al)()()G"
Output: "alGalooG"

Constraints:

1 <= command.length <= 100
command consists of "G", "()", and/or "(al)" in some order.

Solution: String

If we encounter ‘(‘ check the next character to determine whether it’s ‘()’ or ‘(al’)

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

C++

class Solution {

public:

string interpret(string command) {

string ans;

for (int i = 0; i < command.size(); ++i) {

if (command[i] == 'G') ans += "G";

else if (command[i] == '(') {

if (command[i + 1] == ')') ans += "o";

else ans += "al";

}

return ans;

}

};

Python3

class Solution:

def interpret(self, command: str) -> str:

ans = []

for i, c in enumerate(command):

if c == 'G': ans.append('G')

elif c == '(':

ans.append('o' if command[i + 1] == ')' else 'al')

return ''.join(ans)

花花酱 LeetCode 1515. Best Position for a Service Centre

By zxi on November 30, 2020

A delivery company wants to build a new service centre in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new centre in a position such that the sum of the euclidean distances to all customers is minimum.

Given an array positions where positions[i] = [x_i, y_i] is the position of the ith customer on the map, return the minimum sum of the euclidean distances to all customers.

In other words, you need to choose the position of the service centre [x_centre, y_centre] such that the following formula is minimized:

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

Example 1:

Input: positions = [[0,1],[1,0],[1,2],[2,1]]
Output: 4.00000
Explanation: As shown, you can see that choosing [x_centre, y_centre] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.

Example 2:

Input: positions = [[1,1],[3,3]]
Output: 2.82843
Explanation: The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843

Example 3:

Input: positions = [[1,1]]
Output: 0.00000

Example 4:

Input: positions = [[1,1],[0,0],[2,0]]
Output: 2.73205
Explanation: At the first glance, you may think that locating the centre at [1, 0] will achieve the minimum sum, but locating it at [1, 0] will make the sum of distances = 3.
Try to locate the centre at [1.0, 0.5773502711] you will see that the sum of distances is 2.73205.
Be careful with the precision!

Example 5:

Input: positions = [[0,1],[3,2],[4,5],[7,6],[8,9],[11,1],[2,12]]
Output: 32.94036
Explanation: You can use [4.3460852395, 4.9813795505] as the position of the centre.

Constraints:

1 <= positions.length <= 50
positions[i].length == 2
0 <= positions[i][0], positions[i][1] <= 100

Solution: Weiszfeld’s algorithm

Use Weiszfeld’s algorithm to compute geometric median of the samples.

Time complexity: O(f(epsilon) * O)
Space complexity: O(1)

C++

template<typename T1, typename T2>

double dist(const vector<T1>& a, const vector<T2>& b) {

return sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));

};

class Solution {

public:

double getMinDistSum(vector<vector<int>>& positions) {

constexpr double kDelta = 1e-7;

constexpr double kEpsilon = 1e-15;

vector<double> c{-1, -1};

double ans = 0;

while (true) {

ans = 0;

double nx = 0, ny = 0;

double denominator = 0;

for (const auto& p : positions) {

double d = dist(c, p) + kEpsilon;

ans += d;

nx += p[0] / d;

ny += p[1] / d;

denominator += 1.0 / d;

}

vector<double> t{nx / denominator, ny / denominator};

if (dist(c, t) < kDelta) return ans;

c = t;

}

return -1;

}

};

花花酱 LeetCode 1286. Iterator for Combination

By zxi on November 30, 2020

Design an Iterator class, which has:

A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
A function next() that returns the next combination of length combinationLength in lexicographical order.
A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

1 <= combinationLength <= characters.length <= 15
There will be at most 10^4 function calls per test.
It’s guaranteed that all calls of the function next are valid.

Solution: Bitmask

Use a bitmask to represent the chars selected.
start with (2^n – 1), decrease the mask until there are c bit set.
stop when mask reach to 0.

mask: 111 => abc
mask: 110 => ab
mask: 101 => ac
mask: 011 => bc
mask: 000 => “” Done

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

C++

class CombinationIterator {

public:

CombinationIterator(string characters, int combinationLength):

chars_(rbegin(characters), rend(characters)),

length_(combinationLength),

mask_((1 << characters.size()) - 1) {}

string next() {

hasNext();

string ans;

for (int i = chars_.size() - 1; i >= 0 ; --i)

if ((mask_ >> i) & 1)

ans.push_back(chars_[i]);

--mask_;

return ans;

}

bool hasNext() {

while (mask_ >= 0 && __builtin_popcount(mask_) != length_) --mask_;

return mask_ > 0;

}

private:

int mask_ = 0;

const int length_;

const string chars_;

};

花花酱 LeetCode 1675. Minimize Deviation in Array

By zxi on November 29, 2020

You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

If the element is even, divide it by 2.
- For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2].
If the element is odd, multiply it by 2.
- For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [2,2,3,4].

The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Example 1:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

Example 2:

Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

Example 3:

Input: nums = [2,10,8]
Output: 3

Constraints:

n == nums.length
2 <= n <= 10⁵
1 <= nums[i] <= 10⁹

Solution: Priority Queue

If we double an odd number it becomes an even number, then we can only divide it by two which gives us back the original number. So we can pre-double all the odd numbers and only do division in the following process.

We push all numbers including pre-doubled odd ones onto a priority queue, and track the difference between the largest and smallest number.

Each time, we pop the largest number out and divide it by two then put it back to the priority queue, until the largest number becomes odd. We can not discard it and divide any other smaller numbers by two will only increase the max difference, so we can stop here.

ex1: [3, 5, 8] => [6, 8, 10] (pre-double) => [5, 6, 8] => [4, 5, 6] => [3, 4, 5] max diff is 5 – 3 = 2
ex2: [4,1,5,20,3] => [2, 4, 6, 10, 20] (pre-double) => [2, 4, 6, 10] => [2, 4, 5, 6] => [2,3,4,5] max diff = 5-2 = 3

Time complexity: O(n*logm*logn)
Space complexity: O(n)

C++/Set

class Solution {

public:

int minimumDeviation(vector<int>& nums) {

set<int> s;

for (int x : nums)

s.insert(x & 1 ? x * 2 : x);

int ans = *rbegin(s) - *begin(s);

while (*rbegin(s) % 2 == 0) {

s.insert(*rbegin(s) / 2);

s.erase(*rbegin(s));

ans = min(ans, *rbegin(s) - *begin(s));

}

return ans;

}

};

C++/PQ

class Solution {

public:

int minimumDeviation(vector<int>& nums) {

priority_queue<int> q;

int lo = INT_MAX;

for (int x : nums) {

x = x & 1 ? x * 2 : x;

q.push(x);

lo = min(lo, x);

}

int ans = q.top() - lo;

while (q.top() % 2 == 0) {

int x = q.top(); q.pop();

q.push(x / 2);

lo = min(lo, x / 2);

ans = min(ans, q.top() - lo);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1679. Max Number of K-Sum Pairs

Solution 1: Frequency Map

C++

Python3

Solution 2: Two Pointers

C++

花花酱 LeetCode 1678. Goal Parser Interpretation

Solution: String

C++

Python3

花花酱 LeetCode 1515. Best Position for a Service Centre

Solution: Weiszfeld’s algorithm

C++

花花酱 LeetCode 1286. Iterator for Combination

Solution: Bitmask

C++

花花酱 LeetCode 1675. Minimize Deviation in Array

Solution: Priority Queue

C++/Set

C++/PQ