Huahua's Tech Road

花花酱 LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label

By zxi on July 18, 2020

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [a_i, b_i], which means there is an edge between nodes a_i and b_i in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the i^th node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

Example 4:

1 2	<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa" <strong>Output:</strong> [1,2,1,1,2,1]

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]

Constraints:

1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
labels.length == n
labels is consisting of only of lower-case English letters.

Solution: Post order traversal + hashtable

For each label, record the count. When visiting a node, we first record the current count of its label as before, and traverse its children, when done, increment the current count, ans[i] = current – before.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> countSubTrees(int n, vector<vector<int>>& edges,

string_view labels) {

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

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n);

vector<int> count(26);

vector<int> ans(n);

function<void(int)> postOrder = [&](int i) {

if (seen[i]++) return;

int before = count[labels[i] - 'a'];

for (int j : g[i]) postOrder(j);

ans[i] = ++count[labels[i] - 'a'] - before;

};

postOrder(0);

return ans;

}

};

Java

// Author: Huahua

class Solution {

private List<List<Integer>> g;

private String labels;

private int[] ans;

private int[] seen;

private int[] count;

public int[] countSubTrees(int n, int[][] edges, String labels) {

this.g = new ArrayList<List<Integer>>(n);

this.labels = labels;

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

this.g.add(new ArrayList<Integer>());

for (int[] e : edges) {

this.g.get(e[0]).add(e[1]);

this.g.get(e[1]).add(e[0]);

}

this.ans = new int[n];

this.seen = new int[n];

this.count = new int[26];

this.postOrder(0);

return ans;

}

private void postOrder(int i) {

if (this.seen[i]++ > 0) return;

int before = this.count[this.labels.charAt(i) - 'a'];

for (int j : this.g.get(i)) this.postOrder(j);

this.ans[i] = ++this.count[this.labels.charAt(i) - 'a'] - before;

}

Python3

# Author: Huahua

class Solution:

def countSubTrees(self, n: int, edges: List[List[int]],

labels: str) -> List[int]:

g = [[] for _ in range(n)]

for u, v in edges:

g[u].append(v)

g[v].append(u)

seen = [False] * n

count = [0] * 26

ans = [0] * n

def postOrder(i):

if seen[i]: return

seen[i] = True

before = count[ord(labels[i]) - ord('a')]

for j in g[i]: postOrder(j)

count[ord(labels[i]) - ord('a')] += 1

ans[i] = count[ord(labels[i]) - ord('a')] - before

postOrder(0)

return ans

花花酱 LeetCode 1518. Water Bottles

By zxi on July 18, 2020

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink.

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.

Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6

Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2

Constraints:

1 <= numBottles <= 100
2 <= numExchange <= 100

Solution: Simulation

Time complexity: O(logb/loge)?
Space complexity: O(1)

C++

class Solution {

public:

int numWaterBottles(int numBottles, int numExchange) {

int ans = 0;

while (numBottles <= numExchange) {

const int r = numBottles % numExchange;

ans += numBottles - r;

numBottles = r + numBottles / numExchange;

}

ans += numBottles;

return ans;

}

};

Java

class Solution {

public int numWaterBottles(int numBottles, int numExchange) {

int ans = 0;

while (numBottles <= numExchange) {

final int r = numBottles % numExchange;

ans += numBottles - r;

numBottles = r + numBottles / numExchange;

}

ans += numBottles;

return ans;

}

Python3

class Solution:

def numWaterBottles(self, numBottles: int, numExchange: int) ->; int:

ans = 0

while numBottles <= numExchange:

r = numBottles % numExchange

ans += numBottles - r

numBottles = r + numBottles // numExchange

ans += numBottles

return ans

Why grid[y][x] instead of grid[x][y]?

By zxi on July 17, 2020

If you don’t like grid[y][x], you can use grid[r][c] instead.

C++

#include <iostream>

using namespace std;

int main(int argc, char** argv) {

constexpr int kRows = 2;

constexpr int kCols = 3;

int arr[kRows][kCols] = {{1,2,3},{4,5,6}};

for (int r = 0; r < kRows; ++r) {

for (int c = 0; c < kCols; ++c)

cout << arr[r][c] << " ";

cout << endl;

}

for (int r = 0; r < kRows; ++r)

for (int c = 0; c < kCols; ++c)

cout << &(arr[r][c]) - &(arr[0][0]) << " ";

return 0;

}

// Output:

// 1 2 3

// 4 5 6

// 0 1 2 3 4 5

花花酱 LeetCode 1510. Stone Game IV

By zxi on July 17, 2020

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

Constraints:

1 <= n <= 10^5

Solution: Recursion w/ Memoization / DP

Let win(n) denotes whether the current play will win or not.
Try all possible square numbers and see whether the other player will lose or not.
win(n) = any(win(n – i*i) == False) ? True : False
base case: win(0) = False

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

C++

class Solution {

public:

bool winnerSquareGame(int n) {

vector<int> cache(n + 1, 0); // 0:Unknown, 1:Win, -1:Lose

function<int(int)> win = [&](int n) -> int {

if (n == 0) return -1;

if (cache[n]) return cache[n];

for (int i = sqrt(n); i >= 1; --i)

if (win(n - i * i) < 0) return cache[n] = 1;

return cache[n] = -1;

};

return win(n) > 0;

}

};

Java

class Solution {

private int[] cache;

public boolean winnerSquareGame(int n) {

this.cache = new int[n + 1];

return this.win(n) > 0;

}

private int win(int n) {

if (n == 0) return -1;

if (this.cache[n] != 0) return this.cache[n];

for (int i = (int)Math.sqrt(n); i >= 1; --i)

if (win(n - i * i) < 0)

return this.cache[n] = 1;

return this.cache[n] = -1;

}

Python3

class Solution:

def winnerSquareGame(self, n: int) -> bool:

dp = [None] * (n + 1)

dp[0] = False

for i in range(0, n):

if dp[i]: continue

for j in range(1, n + 1):

if i + j * j > n: break

dp[i + j * j] = True

return dp[n]

花花酱 LeetCode 1512. Number of Good Pairs

By zxi on July 16, 2020

Given an array of integers nums.

A pair (i,j) is called good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Example 3:

Input: nums = [1,2,3]
Output: 0

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution 1: Brute Force

Enumerate all the pairs.

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

C++

class Solution {

public:

int numIdenticalPairs(vector<int>& nums) {

int ans = 0;

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

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

ans += nums[i] == nums[j];

return ans;

}

};

Java

class Solution {

public int numIdenticalPairs(int[] nums) {

int ans = 0;

for (int i = 0; i < nums.length; ++i)

for (int j = i + 1; j < nums.length; ++j)

if (nums[i] == nums[j]) ++ans;

return ans;

}

Python3

class Solution:

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

n = len(nums)

ans = 0

for i in range(n):

for j in range(i + 1, n):

if nums[i] == nums[j]: ans += 1

return ans

Solution 2: Hashtable

Store the frequency of each number so far, when we have a number x at pos j, and it appears k times before. Then we can form additional k pairs.

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

C++

// Author: Huahua

class Solution {

public:

int numIdenticalPairs(vector<int>& nums) {

int ans = 0;

vector<int> f(101);

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

ans += f[nums[i]]++;

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int numIdenticalPairs(int[] nums) {

int ans = 0;

int[] f = new int[101];

for (int i = 0; i < nums.length; ++i)

ans += f[nums[i]]++;

return ans;

}

Python3

# Author: Huahua

class Solution:

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

f = defaultdict(int)

ans = 0

for x in nums:

ans += f[x]

f[x] += 1

return ans