Huahua’s Tech Road

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

}

};

花花酱 LeetCode 2078. Two Furthest Houses With Different Colors

By zxi on November 20, 2021

There are n houses evenly lined up on the street, and each house is beautifully painted. You are given a 0-indexed integer array colors of length n, where colors[i] represents the color of the i^th house.

Return the maximum distance between two houses with different colors.

The distance between the i^th and j^th houses is abs(i - j), where abs(x) is the absolute value of x.

Example 1:

Input: colors = [1,1,1,6,1,1,1]
Output: 3
Explanation: In the above image, color 1 is blue, and color 6 is red.
The furthest two houses with different colors are house 0 and house 3.
House 0 has color 1, and house 3 has color 6. The distance between them is abs(0 - 3) = 3.
Note that houses 3 and 6 can also produce the optimal answer.

Example 2:

Input: colors = [1,8,3,8,3]
Output: 4
Explanation: In the above image, color 1 is blue, color 8 is yellow, and color 3 is green.
The furthest two houses with different colors are house 0 and house 4.
House 0 has color 1, and house 4 has color 3. The distance between them is abs(0 - 4) = 4.

Example 3:

Input: colors = [0,1]
Output: 1
Explanation: The furthest two houses with different colors are house 0 and house 1.
House 0 has color 0, and house 1 has color 1. The distance between them is abs(0 - 1) = 1.

Constraints:

n == colors.length
2 <= n <= 100
0 <= colors[i] <= 100
Test data are generated such that at least two houses have different colors.

Solution 1: Brute Force

Try all pairs.
Time complexity: O(n²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxDistance(vector<int>& colors) {

const int n = colors.size();

for (int d = n - 1; d > 0; --d)

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

if (colors[i] != colors[i + d])

return d;

return 0;

}

};

Solution 2: Greedy / One pass

First house or last house must be involved in the ans.

Scan the house and check with first and last house.

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

C++

// Author: Huahua

class Solution {

public:

int maxDistance(vector<int>& colors) {

int ans = 0;

const int n = colors.size();

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

ans = max({ans,

i * (colors[i] != colors[0]),

(n - i - 1) * (colors[i] != colors[n - 1])});

return ans;

}

};

花花酱 LeetCode 2003. Smallest Missing Genetic Value in Each Subtree

By zxi on November 20, 2021

There is a family tree rooted at 0 consisting of n nodes numbered 0 to n - 1. You are given a 0-indexed integer array parents, where parents[i] is the parent for node i. Since node 0 is the root, parents[0] == -1.

There are 10⁵ genetic values, each represented by an integer in the inclusive range [1, 10⁵]. You are given a 0-indexed integer array nums, where nums[i] is a distinct genetic value for node i.

Return an array ans of length n where ans[i] is the smallest genetic value that is missing from the subtree rooted at node i.

The subtree rooted at a node x contains node x and all of its descendant nodes.

Example 1:

Input: parents = [-1,0,0,2], nums = [1,2,3,4]
Output: [5,1,1,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.
- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
- 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.
- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.

Example 2:

Input: parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
Output: [7,1,1,4,2,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3,4,5] with values [5,4,6,2,1,3]. 7 is the smallest missing value.
- 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.
- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
- 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.
- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.

Example 3:

Input: parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
Output: [1,1,1,1,1,1,1]
Explanation: The value 1 is missing from all the subtrees.

Constraints:

Solution: DFS on a single path

One ancestors of node with value of 1 will have missing values greater than 1. We do a dfs on the path that from node with value 1 to the root.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {

const int n = parents.size();

vector<int> ans(n, 1);

vector<int> seen(100002);

vector<vector<int>> g(n);

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

g[parents[i]].push_back(i);

function<void(int)> dfs = [&](int u) {

if (seen[nums[u]]++) return;

for (int v : g[u]) dfs(v);

};

int u = find(begin(nums), end(nums), 1) - begin(nums);

for (int l = 1; u < n && u != -1; u = parents[u]) {

dfs(u);

while (seen[l]) ++l;

ans[u] = l;

}

return ans;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 2078. Two Furthest Houses With Different Colors

Solution 1: Brute Force

C++

Solution 2: Greedy / One pass

C++

花花酱 LeetCode 2003. Smallest Missing Genetic Value in Each Subtree

Solution: DFS on a single path

C++