The height of the binary tree is less than or equal to 20
The total number of nodes is between [1, 10^4]
Total calls of find() is between [1, 10^4]
0 <= target <= 10^6
Solutoin 1: Recursion and HashSet
Time complexity: Recover O(n), find O(1) Space complexity: O(n)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Author: Huahua
classFindElements{
public:
FindElements(TreeNode*root){
recover(root,0);
}
boolfind(inttarget){
returns_.count(target);
}
private:
unordered_set<int>s_;
voidrecover(TreeNode*root,intval){
if(!root)return;
root->val=val;
s_.insert(val);
recover(root->left,val*2+1);
recover(root->right,val*2+2);
}
};
Solution 2: Recursion and Binary format
The binary format of t = (target + 1) (from high bit to low bit, e.g. in reverse order) decides where to go at each node. t % 2 == 1, go right, otherwise go left t = t / 2 or t >>= 1
1
2
3
4
5
6
7
8
9
10
11
12
e.g.target=13,t=13+1=14
t=14,t%1=0,t/2=7,left
t=7,t%1=1,t/2=3,right
t=3,t%1=1,t/2=1,right
13=>right,right,left
0
\
2
\
6
/
13
Time complexity: Recover O(n), find O(log|target|) Space complexity: O(1)
Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.
Example 1:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Example 2:
Input: s = "a)b(c)d"
Output: "ab(c)d"
Example 3:
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.
Example 4:
Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"
Constraints:
1 <= s.length <= 10^5
s[i] is one of '(' , ')' and lowercase English letters.
Solution: Couting
Count how many “(” are open and how many “)” left.
Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix
Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.
Example 1:
Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:
Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:
Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Given a string s, a kduplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made.
It is guaranteed that the answer is unique.
Example 1:
Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.
Example 2:
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
Example 3:
Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"
