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.

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers Return True if its possible otherwise return False.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4 Output: true Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6]. Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 Output: true Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11]. Example 3:

Input: nums = [3,3,2,2,1,1], k = 3 Output: true Example 4:

Input: nums = [1,2,3,4], k = 3 Output: false Explanation: Each array should be divided in subarrays of size 3.

classSolution { public: boolisPossibleDivide(vector<int>& nums, int k){ map<int,int> maps; for (int num : nums) maps[num]++; for (auto m : maps) { int count = m.second; if (count > 0) { for (int i = 0; i < k; i++) { int key = m.first + i; if (maps[key] < count) returnfalse; maps[key] -= count; } } } returntrue; } };

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Given a string s and an array of integers cost where cost[i] is the cost of deleting the ith character in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.

Example 1:

Input: s = “abaac”, cost = [1,2,3,4,5] Output: 3 Explanation: Delete the letter “a” with cost 3 to get “abac” (String without two identical letters next to each other). Example 2:

Input: s = “abc”, cost = [1,2,3] Output: 0 Explanation: You don’t need to delete any character because there are no identical letters next to each other. Example 3:

Input: s = “aabaa”, cost = [1,2,3,4,1] Output: 2 Explanation: Delete the first and the last character, getting the string (“aba”).

Constraints:

s.length == cost.length 1 <= s.length, cost.length <= 10^5 1 <= cost[i] <= 10^4 s contains only lowercase English letters.

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 Output: 16 Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

classSolution { public: vector<int> leader; vector<int> total; intlargestIsland(vector<vector<int>>& grid){ int row = grid.size(), col = grid[0].size(); int size = row * col; leader.resize(size); total.resize(size, 1); for (int i = 0; i < size; i++) { leader[i] = i; } vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; for (int r = 0; r < row; r++) { for (int c = 0; c < col; c++) { if (grid[r][c] == 1) { for (auto d : dirs) { int rr = r + d[0]; int cc = c + d[1]; if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0) continue; Union(find(r*row + c), find(rr*row + cc)); } } } } int max_island = 0; for (int r = 0; r < row; r++) { for (int c = 0; c < col; c++) { if (grid[r][c] == 0) { unordered_set<int> set; for (auto d : dirs) { int rr = r + d[0]; int cc = c + d[1]; if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0) continue; set.insert(find(rr * row + cc)); } int cnt = 1; for (auto i : set) cnt += total[i]; max_island = max(max_island, cnt); } } } return max_island == 0 ? size : max_island; } intfind(int i){ if (leader[i] != i) leader[i] = find(leader[i]); return leader[i]; } voidUnion(int i, int j){ int x = leader[i]; int y = leader[j]; if (x == y) return; leader[x] = y; total[y] += total[x]; } };

classSolution2 { public: intlargestIsland(vector<vector<int>>& grid){ int row = grid.size(), col = grid[0].size();

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also it’s guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the employees of the company of an urgent piece of news. He will inform his direct subordinates and they will inform their subordinates and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0] Output: 0 Explanation: The head of the company is the only employee in the company. Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0] Output: 1 Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all. The tree structure of the employees in the company is shown. Example 3:

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1] Output: 21 Explanation: The head has id = 6. He will inform employee with id = 5 in 1 minute. The employee with id = 5 will inform the employee with id = 4 in 2 minutes. The employee with id = 4 will inform the employee with id = 3 in 3 minutes. The employee with id = 3 will inform the employee with id = 2 in 4 minutes. The employee with id = 2 will inform the employee with id = 1 in 5 minutes. The employee with id = 1 will inform the employee with id = 0 in 6 minutes. Needed time = 1 + 2 + 3 + 4 + 5 + 6 = 21. Example 4:

Input: n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0] Output: 3 Explanation: The first minute the head will inform employees 1 and 2. The second minute they will inform employees 3, 4, 5 and 6. The third minute they will inform the rest of employees. Example 5:

1 <= n <= 10^5 0 <= headID < n manager.length == n 0 <= manager[i] < n manager[headID] == -1 informTime.length == n 0 <= informTime[i] <= 1000 informTime[i] == 0 if employee i has no subordinates. It is guaranteed that all the employees can be informed.

classSolution { public: intnumOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime){ vector<vector<int>> tree(n); int size = manager.size(); for (int i = 0; i < size; i++) { if (manager[i] == -1) continue; tree[manager[i]].push_back(i); } return recursive(tree, headID, informTime); } intrecursive(vector<vector<int>> &tree, int i, vector<int>& informTime){ int time = 0; for (int k : tree[i]) { time = max(time, recursive(tree, k, informTime)); } return time + informTime[i]; } };

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0], [0,0,1], [1,0,0]] Output: 1 Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0. Example 2:

Input: mat = [[1,0,0], [0,1,0], [0,0,1]] Output: 3 Explanation: (0,0), (1,1) and (2,2) are special positions. Example 3:

Input: mat = [[0,0,0,1], [1,0,0,0], [0,1,1,0], [0,0,0,0]] Output: 2 Example 4:

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

Constraints:

rows == mat.length cols == mat[i].length 1 <= rows, cols <= 100 mat[i][j] is 0 or 1.