LC 904, 929, 482, 975, 399, 844, 857
904. Fruit Into Baskets / 159. Longest Substring with At Most Two Distinct Characters
- Sliding window + HashMap
929. Unique Email Addresses
- Simple String operations including split, replace, indexOf, substring
- String
482. License Key Formatting
- Iterate from the end; skip all the “-“; Check K first, then append current character.
- String
975. Odd Even Jump
- Two index arrays to store next index after an even/odd skip, use TreeMap.ceilingKey and floorKey.
-
Two dp boolean arrays, start from the end
evenDp[i] = oddDp[even[i]]; oddDp[i] = evenDp[odd[i]]; -
DP, TreeMap
399. Evaluate Division
- Equation result is the edge weight, equation variables are the two vertices. Just search the graph.
- Graph, DFS, HashMap
844. Backspace String Compare
- O(n) space complexity is easy
- O(1) need to iterate from the end and add +1/-1 to back until back is 0, i moves at the same time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1;
int j = T.length() - 1;
while (true) {
for (int back = 0; i >= 0 && (back > 0 || S.charAt(i) == '#'); i--) {
back += (S.charAt(i) == '#') ? 1 : -1;
}
for (int back = 0; j >= 0 && (back > 0 || T.charAt(j) == '#'); j--) {
back += (T.charAt(j) == '#') ? 1 : -1;
}
if (i < 0 || j < 0 || S.charAt(i) != T.charAt(j)) {
return i == -1 && j == -1;
} else {
i--;
j--;
}
}
}
857. Minimum Cost to Hire K Workers
-
Start from the smallest ratio, and then keep add new worker and remove old worker; Use a maximum heap to store worker qualities
ratio = max(wage / quality) in K workers, cost = ratio * wage_sum -
Priority Queue, Array, Math
近期评论