Posts published in “Uncategorized”

花花酱 LeetCode 1609. Even Odd Tree

By zxi on October 4, 2020

A binary tree is named Even-Odd if it meets the following conditions:

The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing, and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in the level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.

Example 4:

Input: root = [1]
Output: true

Example 5:

Input: root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
Output: true

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁶

Solution 1: DFS

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

C++

class Solution {

public:

bool isEvenOddTree(TreeNode* root) {

vector<int> vals;

function<bool(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {

if (!root) return true;

if (vals.size() <= d)

vals.push_back(d % 2 == 0 ? -1 : INT_MAX);

int& val = vals[d];

if (d % 2 == 0)

if (root->val % 2 == 0 || root->val <= val) return false;

if (d % 2 == 1)

if (root->val % 2 == 1 || root->val >= val) return false;

val = root->val;

return dfs(root->left, d + 1) && dfs(root->right, d + 1);

};

return dfs(root, 0);

}

};

Python3

# Author: Huahua

class Solution:

def isEvenOddTree(self, root: TreeNode) -> bool:

vals = {}

def dfs(root: TreeNode, d: int) -> bool:

if not root: return True

if d not in vals: vals[d] = 0 if d % 2 == 0 else 10**7

comp = int.__ge__ if d % 2 else int.__le__

if root.val % 2 == d % 2 or comp(root.val, vals[d]): return False

vals[d] = root.val

return dfs(root.left, d + 1) and dfs(root.right, d + 1)

return dfs(root, 0)

Solution 2: BFS

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

Python3

# Author: Huahua

class Solution:

def isEvenOddTree(self, root: TreeNode) -> bool:

q = collections.deque([root])

odd = 1

while q:

prev = 0 if odd else 10**7

for _ in range(len(q)):

root = q.popleft()

if not root: continue

comp = int.__le__ if odd else int.__ge__

if root.val % 2 != odd or comp(root.val, prev): return False

prev = root.val

q += (root.left, root.right)

odd = 1 - odd

return True

花花酱 LeetCode 1536. Minimum Swaps to Arrange a Binary Grid

By zxi on August 2, 2020

Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3

Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] is 0 or 1

Solution: Bubble Sort

Counting how many tailing zeros each row has.
Then input
[0, 0, 1]
[1, 1, 0]
[1, 0, 0]
becomes [0, 1, 2]
For i-th row, it needs n – i – 1 tailing zeros.
We need to find the first row that has at least n – i – 1 tailing zeros and bubbling it up to the i-th row. This process is very similar to bubble sort.
[0, 1, 2] -> [0, 2, 1] -> [2, 0, 1]
[2, 0, 1] -> [2, 1, 0]
Total 3 swaps.

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

C++

class Solution {

public:

int minSwaps(vector<vector<int>>& grid) {

const int n = grid.size();

vector<int> zeros;

for (const auto& row : grid) {

int zero = 0;

for (int i = n - 1; i >= 0 && row[i] == 0; --i)

++zero;

zeros.push_back(zero);

}

int ans = 0;

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

int j = i;

int z = n - i - 1; // the i-th needs n - i - 1 zeros

// Find first row with at least z tailing zeros.

while (j < n && zeros[j] < z) ++j;

if (j == n) return -1;

while (j > i) {

zeros[j] = zeros[j - 1];

--j;

++ans;

}

return ans;

}

};

花花酱 LeetCode 1457. Pseudo-Palindromic Paths in a Binary Tree

By zxi on May 24, 2020

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3:

Input: root = [9]
Output: 1

Constraints:

The given binary tree will have between 1 and 10^5 nodes.
Node values are digits from 1 to 9.

Solution: Counting

At most one number can occur odd times.

Time complexity: O(n)
Space complexity: O(n) / stack size

C++

// Author: Huahua

class Solution {

public:

int pseudoPalindromicPaths (TreeNode* root) {

vector<int> counts(10);

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

if (!node) return 0;

++counts[node->val];

int c = 0;

if (!node->left && !node->right) {

int odds = 0;

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

if (counts[i] & 1) ++odds;

if (odds <= 1) c = 1;

}

int l = dfs(node->left);

int r = dfs(node->right);

--counts[node->val];

return c + l + r;

};

return dfs(root);

}

};

Use a binary string to represent occurrences of each number (even: 0 / odd: 1), we can use xor to flip the bit.

C++

// Author: Huahua

class Solution {

public:

int pseudoPalindromicPaths(TreeNode* root, int s = 0) {

if (!root) return 0;

s ^= (1 << root->val);

if (!root->left && !root->right)

return __builtin_popcount(s) <= 1;

return pseudoPalindromicPaths(root->left, s)

+ pseudoPalindromicPaths(root->right, s);

}

};

花花酱 LeetCode 1443. Minimum Time to Collect All Apples in a Tree

By zxi on May 10, 2020

Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend in order to collect all apples in the tree starting at vertex 0 and coming back to this vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [from_i, to_i] means that exists an edge connecting the vertices from_i and to_i. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple, otherwise, it does not have any apple.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8 
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

Example 2:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Output: 6
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

Example 3:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
Output: 0

Constraints:

1 <= n <= 10^5
edges.length == n-1
edges[i].length == 2
0 <= from_i, to_i <= n-1
from_i < to_i
hasApple.length == n

Solution: DFS

Build the graph (tree) and DFS.

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

C++

// Author: Huahua

class Solution {

public:

int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {

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

for (const auto& e : edges)

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

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

int total = 0;

for (int nxt : g[cur]) {

int cost = dfs(nxt);

if (cost > 0 || hasApple[nxt]) total += 2 + cost;

}

return total;

};

return dfs(0);

}

};

if edge is not ordered

C++

// Author: Huahua

class Solution {

public:

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

vector<bool>& hasApple) {

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);

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

seen[cur] = 1;

int total = 0;

for (int child : g[cur]) {

if (seen[child]) continue;

int cost = dfs(child);

if (cost > 0 || hasApple[child])

total += 2 + cost;

}

return total;

};

return dfs(0);

}

};

花花酱 LeetCode 1281. Subtract the Product and Sum of Digits of an Integer

By zxi on December 8, 2019

Given an integer number n, return the difference between the product of its digits and the sum of its digits.

Example 1:

Input: n = 234

Output: 15

Explanation:

Product of digits = 2 * 3 * 4 = 24

Sum of digits = 2 + 3 + 4 = 9

Result = 24 - 9 = 15

Example 2:

Input: n = 4421

Output: 21

Explanation:

Product of digits = 4 * 4 * 2 * 1 = 32

Sum of digits = 4 + 4 + 2 + 1 = 11

Result = 32 - 11 = 21

Constraints:

1 <= n <= 10^5

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int subtractProductAndSum(int n) {

int p = 1;

int s = 0;

while (n) {

const int d = n % 10;

p *= d;

s += d;

n /= 10;

}

return p - s;

}

};