Huahua’s Tech Road

花花酱 LeetCode 2007. Find Original Array From Doubled Array

By zxi on November 25, 2021

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

1 <= changed.length <= 10⁵
0 <= changed[i] <= 10⁵

Solution 1: Multiset

Start from the smallest number x, erase one x * 2 from the set.

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

C++/Multiset

// Author: Huahua

class Solution {

public:

vector<int> findOriginalArray(vector<int>& changed) {

if (changed.size() & 1) return {};

const int n = changed.size() / 2;

multiset<int> s(begin(changed), end(changed));

while (ans.size() != n) {

int o = *begin(s);

s.erase(begin(s));

ans.push_back(o);

auto it = s.find(o * 2);

if (it == end(s)) return {};

s.erase(it);

}

return ans;

}

};

Solution 2: Hashtable

Time complexity: O(max(nums) + n)
Space complexity: O(max(nums))

C++/Hashtable

// Author: Huahua

class Solution {

public:

vector<int> findOriginalArray(vector<int>& changed) {

if (changed.size() & 1) return {};

const int n = changed.size() / 2;

const int kMax = *max_element(begin(changed), end(changed));

vector<int> m(kMax + 1);

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

if (m[0] & 1) return {};

vector<int> ans(m[0] / 2, 0);

for (int x = 1; ans.size() != n; ++x) {

if (x * 2 > kMax || m[x * 2] < m[x]) return {};

ans.insert(end(ans), m[x], x);

m[x * 2] -= m[x];

}

return ans;

}

};

花花酱 LeetCode 2006. Count Number of Pairs With Absolute Difference K

By zxi on November 25, 2021

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]

Example 2:

Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.

Example 3:

Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
- [3,2,1,5,4]
- [3,2,1,5,4]
- [3,2,1,5,4]

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99

Solution: Hashtable
|y – x| = k
y = x + k or y = x – k

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

C++

// Author: Huahua

class Solution {

public:

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

unordered_map<int, int> m;

int ans = 0;

for (int x : nums) {

ans += m[x - k];

ans += m[x + k];

++m[x];

}

return ans;

}

};

花花酱 LeetCode 2081. Sum of k-Mirror Numbers

By zxi on November 21, 2021

A k-mirror number is a positive integer without leading zeros that reads the same both forward and backward in base-10 as well as in base-k.

For example, 9 is a 2-mirror number. The representation of 9 in base-10 and base-2 are 9 and 1001 respectively, which read the same both forward and backward.
On the contrary, 4 is not a 2-mirror number. The representation of 4 in base-2 is 100, which does not read the same both forward and backward.

Given the base k and the number n, return the sum of the n smallest k-mirror numbers.

Example 1:

Input: k = 2, n = 5
Output: 25
Explanation:
The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:
  base-10    base-2
    1          1
    3          11
    5          101
    7          111
    9          1001
Their sum = 1 + 3 + 5 + 7 + 9 = 25.

Example 2:

Input: k = 3, n = 7
Output: 499
Explanation:
The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:
  base-10    base-3
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
Their sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.

Example 3:

Input: k = 7, n = 17
Output: 20379000
Explanation: The 17 smallest 7-mirror numbers are:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

Constraints:

2 <= k <= 9
1 <= n <= 30

Solution: Generate palindromes in base-k.

Python

# Author: Huahua

class Solution:

def kMirror(self, k: int, n: int) -> int:

def getNext(x: str) -> str:

s = list(x)

l = len(s)

for i in range(l // 2, l):

if int(s[i]) + 1 >= k: continue

s[i] = s[~i] = str(int(s[i]) + 1)

for j in range(l // 2, i): s[j] = s[~j] = "0"

return "".join(s)

return "1" + "0" * (l - 1) + "1"

ans = 0

x = "0"

for _ in range(n):

while True:

x = getNext(x)

val = int(x, k)

if str(val) == str(val)[::-1]: break

ans += val

return ans

花花酱 LeetCode 2080. Range Frequency Queries

By zxi on November 21, 2021

Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:

RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:

Input
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
Output

[null, 1, 2]

Explanation RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4] rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.

Constraints:

1 <= arr.length <= 10⁵
1 <= arr[i], value <= 10⁴
0 <= left <= right < arr.length
At most 10⁵ calls will be made to query

Solution: Hashtable + Binary Search

Time complexity: Init: O(max(arr) + n), query: O(logn)
Space complexity: O(max(arr) + n)

C++

// Author: Huahua

class RangeFreqQuery {

public:

RangeFreqQuery(vector<int>& arr) : s_(10001) {

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

s_[arr[i]].push_back(i);

}

int query(int left, int right, int value) {

const auto& m = s_[value];

if (m.empty()) return 0;

auto r = prev(upper_bound(begin(m), end(m), right));

auto l = lower_bound(begin(m), end(m), left);

return r - l + 1;

}

private:

vector<vector<int>> s_;

};

/**

* Your RangeFreqQuery object will be instantiated and called as such:

* RangeFreqQuery* obj = new RangeFreqQuery(arr);

* int param_1 = obj->query(left,right,value);

花花酱 LeetCode 2079. Watering Plants

By zxi on November 20, 2021

You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the i^th plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

Water the plants in order from left to right.
After watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.
You cannot refill the watering can early.

You are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the i^th plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

Example 1:

Input: plants = [2,2,3,3], capacity = 5
Output: 14
Explanation: Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2:

Input: plants = [1,1,1,4,2,3], capacity = 4
Output: 30
Explanation: Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

Example 3:

Input: plants = [7,7,7,7,7,7,7], capacity = 8
Output: 49
Explanation: You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

Constraints:

n == plants.length
1 <= n <= 1000
1 <= plants[i] <= 10⁶
max(plants[i]) <= capacity <= 10⁹

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int wateringPlants(vector<int>& plants, int capacity) {

const int n = plants.size();

int ans = 0;

for (int i = 0, c = capacity; i < n; c -= plants[i++], ++ans) {

if (c >= plants[i]) continue;

ans += i * 2;

c = capacity;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2007. Find Original Array From Doubled Array

Solution 1: Multiset

C++/Multiset

Solution 2: Hashtable

C++/Hashtable

花花酱 LeetCode 2006. Count Number of Pairs With Absolute Difference K

Solution: Hashtable|y – x| = ky = x + k or y = x – k

C++

花花酱 LeetCode 2081. Sum of k-Mirror Numbers

Solution: Generate palindromes in base-k.

Python

花花酱 LeetCode 2080. Range Frequency Queries

C++

花花酱 LeetCode 2079. Watering Plants

Solution: Simulation

C++

Solution: Hashtable
|y – x| = k
y = x + k or y = x – k