Huahua’s Tech Road

花花酱 LeetCode 2049. Count Nodes With the Highest Score

By zxi on October 26, 2021

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

Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees.

Return the number of nodes that have the highest score.

Example 1:

Input: parents = [-1,2,0,2,0]
Output: 3
Explanation:
- The score of node 0 is: 3 * 1 = 3
- The score of node 1 is: 4 = 4
- The score of node 2 is: 1 * 1 * 2 = 2
- The score of node 3 is: 4 = 4
- The score of node 4 is: 4 = 4
The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.

Example 2:

Input: parents = [-1,2,0]
Output: 2
Explanation:
- The score of node 0 is: 2 = 2
- The score of node 1 is: 2 = 2
- The score of node 2 is: 1 * 1 = 1
The highest score is 2, and two nodes (node 0 and node 1) have the highest score.

Constraints:

n == parents.length
2 <= n <= 10⁵
parents[0] == -1
0 <= parents[i] <= n - 1 for i != 0
parents represents a valid binary tree.

Solution: Recursion

Write a function that returns the element of a subtree rooted at node.

We can compute the score based on:
1. size of the subtree(s)
2. # of children

Root is a special case whose score is max(c[0], 1) * max(c[1], 1).

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

C++

// Author: Huahua

class Solution {

public:

int countHighestScoreNodes(vector<int>& parents) {

const int n = parents.size();

long high = 0;

int ans = 0;

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

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

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

function<int(int)> dfs = [&](int node) -> int {

long c[2] = {0, 0};

for (int i = 0; i < tree[node].size(); ++i)

c[i] = dfs(tree[node][i]);

long score = 0;

if (node == 0) // case #1: root

score = max(c[0], 1l) * max(c[1], 1l);

else if (tree[node].size() == 0) // case #2: leaf

score = n - 1;

else if (tree[node].size() == 1) // case #3: one child

score = c[0] * (n - c[0] - 1);

else // case #4: two children

score = c[0] * c[1] * (n - c[0] - c[1] - 1);

if (score > high) {

high = score;

ans = 1;

} else if (score == high) {

++ans;

}

return 1 + c[0] + c[1];

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 2048. Next Greater Numerically Balanced Number

By zxi on October 25, 2021

An integer x is numerically balanced if for every digit d in the number x, there are exactly d occurrences of that digit in x.

Given an integer n, return the smallest numerically balanced number strictly greater than n.

Example 1:

Input: n = 1
Output: 22
Explanation: 
22 is numerically balanced since:
- The digit 2 occurs 2 times. 
It is also the smallest numerically balanced number strictly greater than 1.

Example 2:

Input: n = 1000
Output: 1333
Explanation: 
1333 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times. 
It is also the smallest numerically balanced number strictly greater than 1000.
Note that 1022 cannot be the answer because 0 appeared more than 0 times.

Example 3:

Input: n = 3000
Output: 3133
Explanation: 
3133 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times.
It is also the smallest numerically balanced number strictly greater than 3000.

Constraints:

0 <= n <= 10⁶

Solution: Permutation

Time complexity: O(log(n)!)
Space complexity: O(log(n)) ?

C++

// Author: Huahua

class Solution {

public:

int nextBeautifulNumber(int n) {

const string t = to_string(n);

vector<int> nums{1,

22,

122, 333,

1333, 4444,

14444, 22333, 55555,

122333, 155555, 224444, 666666};

int ans = 1224444;

for (int num : nums) {

string s = to_string(num);

if (s.size() < t.size()) continue;

else if (s.size() > t.size()) {

ans = min(ans, num);

} else { // same length

do {

if (s > t) ans = min(ans, stoi(s));

} while (next_permutation(begin(s), end(s)));

}

return ans;

}

};

花花酱 LeetCode 2047. Number of Valid Words in a Sentence

By zxi on October 24, 2021

A sentence consists of lowercase letters ('a' to 'z'), digits ('0' to '9'), hyphens ('-'), punctuation marks ('!', '.', and ','), and spaces (' ') only. Each sentence can be broken down into one or more tokens separated by one or more spaces ' '.

A token is a valid word if:

It only contains lowercase letters, hyphens, and/or punctuation (no digits).
There is at most one hyphen '-'. If present, it should be surrounded by lowercase characters ("a-b" is valid, but "-ab" and "ab-" are not valid).
There is at most one punctuation mark. If present, it should be at the end of the token.

Examples of valid words include "a-b.", "afad", "ba-c", "a!", and "!".

Given a string sentence, return the number of valid words in sentence.

Example 1:

Input: sentence = "cat and  dog"
Output: 3
Explanation: The valid words in the sentence are "cat", "and", and "dog".

Example 2:

Input: sentence = "!this  1-s b8d!"
Output: 0
Explanation: There are no valid words in the sentence.
"!this" is invalid because it starts with a punctuation mark.
"1-s" and "b8d" are invalid because they contain digits.

Example 3:

Input: sentence = "alice and  bob are playing stone-game10"
Output: 5
Explanation: The valid words in the sentence are "alice", "and", "bob", "are", and "playing".
"stone-game10" is invalid because it contains digits.

Example 4:

Input: sentence = "he bought 2 pencils, 3 erasers, and 1  pencil-sharpener."
Output: 6
Explanation: The valid words in the sentence are "he", "bought", "pencils,", "erasers,", "and", and "pencil-sharpener.".

Constraints:

1 <= sentence.length <= 1000
sentence only contains lowercase English letters, digits, ' ', '-', '!', '.', and ','.
There will be at least 1 token.

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countValidWords(string sentence) {

stringstream ss(sentence);

string word;

int ans = 0;

while (ss >> word) {

bool valid = true;

int hyphen = 0;

int punctuation = 0;

char p = ' ';

for (char c : word) {

if (c == '-') {

if (++hyphen > 1 || !isalpha(p)) {

valid = false;

break;

}

} else if (c == '!' || c == '.' || c == ',') {

if (++punctuation > 1 || p == '-') {

valid = false;

break;

}

} else if (isalpha(c)) {

if (punctuation) {

valid = false;

break;

}

} else {

valid = false;

break;

}

p = c;

}

if (word.back() == '-')

valid = false;

if (valid) ++ans;

}

return ans;

}

};

Solution 2: Regex

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

Python

# Author: Huahua

class Solution:

def countValidWords(self, sentence: str) -> int:

ans = 0

for word in sentence.split():

if word.strip() and re.fullmatch('^([a-z]+(-?[a-z]+)?)?[\.,!]?$', word.strip()):

ans += 1

return ans

花花酱 LeetCode 2022. Convert 1D Array Into 2D Array

By zxi on October 23, 2021

You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.

The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.

Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.

Example 1:

Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2],[3,4]]
Explanation:
The constructed 2D array should contain 2 rows and 2 columns.
The first group of n=2 elements in original, [1,2], becomes the first row in the constructed 2D array.
The second group of n=2 elements in original, [3,4], becomes the second row in the constructed 2D array.

Example 2:

Input: original = [1,2,3], m = 1, n = 3
Output: [[1,2,3]]
Explanation:
The constructed 2D array should contain 1 row and 3 columns.
Put all three elements in original into the first row of the constructed 2D array.

Example 3:

Input: original = [1,2], m = 1, n = 1
Output: []
Explanation:
There are 2 elements in original.
It is impossible to fit 2 elements in a 1x1 2D array, so return an empty 2D array.

Example 4:

Input: original = [3], m = 1, n = 2
Output: []
Explanation:
There is 1 element in original.
It is impossible to make 1 element fill all the spots in a 1x2 2D array, so return an empty 2D array.

Constraints:

1 <= original.length <= 5 * 10⁴
1 <= original[i] <= 10⁵
1 <= m, n <= 4 * 10⁴

Solution: Brute Force

the i-th element in original array will have index (i//n, i % n) in the 2D array.

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

C++

class Solution {

public:

vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {

if (original.size() != m * n) return {};

vector<vector<int>> ans(m, vector<int>(n));

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

ans[i / n][i % n] = original[i];

return ans;

}

};

LeetCode 2033. Minimum Operations to Make a Uni-Value Grid

By zxi on October 21, 2021

You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid.

A uni-value grid is a grid where all the elements of it are equal.

Return the minimum number of operations to make the grid uni-value. If it is not possible, return -1.

Example 1:

Input: grid = [[2,4],[6,8]], x = 2
Output: 4
Explanation: We can make every element equal to 4 by doing the following: 
- Add x to 2 once.
- Subtract x from 6 once.
- Subtract x from 8 twice.
A total of 4 operations were used.

Example 2:

Input: grid = [[1,5],[2,3]], x = 1
Output: 5
Explanation: We can make every element equal to 3.

Example 3:

Input: grid = [[1,2],[3,4]], x = 2
Output: -1
Explanation: It is impossible to make every element equal.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
1 <= x, grid[i][j] <= 10⁴

Solution: Median

To achieve minimum operations, the uni-value must be the median of the array.

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

C++

// Author; Huahua

class Solution {

public:

int minOperations(vector<vector<int>>& grid, int x) {

const int mn = grid.size() * grid[0].size();

vector<int> nums;

nums.reserve(mn);

for (const auto& row : grid)

nums.insert(end(nums), begin(row), end(row));

nth_element(begin(nums), begin(nums) + mn / 2, end(nums));

const int median = nums[mn / 2];

int ans = 0;

for (int v : nums) {

if (abs(v - median) % x) return -1;

ans += abs(v - median) / x;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2049. Count Nodes With the Highest Score

Solution: Recursion

C++

花花酱 LeetCode 2048. Next Greater Numerically Balanced Number

Solution: Permutation

C++

花花酱 LeetCode 2047. Number of Valid Words in a Sentence

Solution 1: Brute Force

C++

Solution 2: Regex

Python

花花酱 LeetCode 2022. Convert 1D Array Into 2D Array

Solution: Brute Force

C++

LeetCode 2033. Minimum Operations to Make a Uni-Value Grid

Solution: Median

C++