December 17, 2021
Given the root of a binary tree, each node has a value from 0 to 25representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.
Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.
(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba". A leaf of a node is a node that has no children.)
Example 1:
Input: [0,1,2,3,4,3,4] Output: "dba"
Example 2:
Input: [25,1,3,1,3,0,2] Output: "adz"
Example 3:
Input: [2,2,1,null,1,0,null,0] Output: "abc"
Note:
1 and 1000.0 and 25.Time complexity: O(n^2)
Space complexity: O(n^2)
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua, running time: 0 ms class Solution { public: string smallestFromLeaf(TreeNode* root) { if (!root) return "|"; // '|' > 'z' const char v = static_cast<char>('a' + root->val); if (!root->left && !root->right) return string(1, v); string l = smallestFromLeaf(root->left); string r = smallestFromLeaf(root->right); return min(l, r) + v; } }; |
|
1 2 3 4 5 6 7 |
class Solution: def smallestFromLeaf(self, root: 'TreeNode') -> 'str': if not root: return '~' c = chr(root.val + ord('a')) if not root.left and not root.right: return c return min(self.smallestFromLeaf(root.left), self.smallestFromLeaf(root.right)) + c |
Given a binary tree, return the vertical order traversal of its nodes values.
For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).
Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).
If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.
Example 1:
Input: [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] Explanation: Without loss of generality, we can assume the root node is at position (0, 0): Then, the node with value 9 occurs at position (-1, -1); The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2); The node with value 20 occurs at position (1, -1); The node with value 7 occurs at position (2, -2).
Example 2:
Input: [1,2,3,4,5,6,7] Output: [[4],[2],[1,5,6],[3],[7]] Explanation: The node with value 5 and the node with value 6 have the same position according to the given scheme. However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.
Note:
1000 nodes.0 and 1000.Time complexity: O(nlogn)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua, running time: 0 ms, 921.6 KB class Solution { public: vector<vector<int>> verticalTraversal(TreeNode* root) { if (!root) return {}; int min_x = INT_MAX; int max_x = INT_MIN; map<pair<int, int>, multiset<int>> h; // {y, x} -> {vals} traverse(root, 0, 0, h, min_x, max_x); vector<vector<int>> ans(max_x - min_x + 1); for (const auto& m : h) { int x = m.first.second - min_x; ans[x].insert(end(ans[x]), begin(m.second), end(m.second)); } return ans; } private: void traverse(TreeNode* root, int x, int y, map<pair<int, int>, multiset<int>>& h, int& min_x, int& max_x) { if (!root) return; min_x = min(min_x, x); max_x = max(max_x, x); h[{y, x}].insert(root->val); traverse(root->left, x - 1, y + 1, h, min_x, max_x); traverse(root->right, x + 1, y + 1, h, min_x, max_x); } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Author: Huahua, 36 ms, 6.8 MB class Solution: def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]': if not root: return [] vals = [] def preorder(root, x, y): if not root: return vals.append((x, y, root.val)) preorder(root.left, x - 1, y + 1) preorder(root.right, x + 1, y + 1) preorder(root, 0, 0) ans = [] last_x = -1000 for x, y, val in sorted(vals): if x != last_x: ans.append([]) last_x = x ans[-1].append(val) return ans |
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)
Example 1:
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.
Note:
0 <= A.length < 10000 <= B.length < 10000 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9Time complexity: O(m + n)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, running time: 36 ms, 925.7 KB class Solution { public: vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) { size_t i = 0; size_t j = 0; vector<Interval> ans; while (i < A.size() && j < B.size()) { const int s = max(A[i].start, B[j].start); const int e = min(A[i].end, B[j].end); if (s <= e) ans.emplace_back(s, e); if (A[i].end < B[j].end) ++i; else ++j; } return ans; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Author: Huahua, running time: 96 ms, 7.6 MB class Solution: def intervalIntersection(self, A: 'List[Interval]', B: 'List[Interval]') -> 'List[Interval]': i, j, ans = 0, 0, [] while i < len(A) and j < len(B): s = max(A[i].start, B[j].start) e = min(A[i].end, B[j].end) if s <= e: ans.append(Interval(s, e)) if A[i].end < B[j].end: i += 1 else: j += 1 return ans |
We have an array A of integers, and an array queries of queries.
For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.
(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)
Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.
Example 1:
Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]] Output: [8,6,2,4] Explanation: At the beginning, the array is [1,2,3,4]. After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8. After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6. After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2. After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.
Note:
1 <= A.length <= 10000-10000 <= A[i] <= 100001 <= queries.length <= 10000-10000 <= queries[i][0] <= 100000 <= queries[i][1] < A.lengthTime complexity: O(n + |Q|)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, Running time: 100 ms / 6.5 MB class Solution { public: vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) { int sum = 0; for (int i = 0; i < A.size(); ++i) if (A[i] % 2 == 0) sum += A[i]; vector<int> ans; for (const auto& query : queries) { int& a = A[query[1]]; if (a % 2 == 0) sum -= a; a += query[0]; if (a % 2 == 0) sum += a; ans.push_back(sum); } return ans; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 |
# Author: Huahua, running time: 188 ms / 16.4MB class Solution: def sumEvenAfterQueries(self, A: 'List[int]', queries: 'List[List[int]]') -> 'List[int]': s = sum(x for x in A if x % 2 == 0) ans = [] for val, index in queries: if A[index] % 2 == 0: s -= A[index] A[index] += val if A[index] % 2 == 0: s += A[index] ans.append(s) return ans |