起晚了起晚了，又玩了会儿炉石，堕落啊堕落。。
今天得把两个String的lec看完，把里面的题做完。
Top K Frequent Elements
这题思路很简单 就是先存hashMap 再用heap来sort求top frequent
但是implementation十分蛋疼，首先是要把map里的pair存入heap
for(Map.Entry<Integer, Integer> entry : map.entrySet())
在heap中比较时，还得用到lambda
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> a.getValue()-b.getValue());
反正很蛋疼，有缘学下lambda和再写一遍吧。。✘✘！Missing Number
way1 hashset way2 sum way3 binary search way4 XOR
Common Numbers Of Two Sorted Arrays
way1 hashset O(m + n) space O(min(m, n))
way2 2pointer 谁小移谁 O(m + n) space O(1)
way3 binary search 如果两个array 大小相差悬殊 O(mlogn)
type 1 char removal
Remove Certain Characters
两个pointer来做 （not include）
remove需要inplace 不用交换直接覆盖即可
最后生成新的string可以用String(arr, 0, i)来完成
String(char[] value, int offset, int count)
Allocates a new String that contains characters from a subarray of the character array argument.
Remove Spaces
两个pointer来做
先将leading 和 duplicate去掉
分情况讨论： case1： if arr[j] != ' ', arr[i] = arr[j], i++,j++
case2 : if arr[j] == ' ',
case2.1: if j == 0, ignore
case2.2: if arr[j - 1] != ' ', retain
case2.3: if arr[j - 1] == ' ', ignore
做完上述操作后再加上处理最后trailing space的一步
for (int j = 0; j < arr.length; j++) {
// ignore space 2.1 2.3
if (arr[j] == ' ' && (j == 0 || arr[j - 1] == ' ')) {
continue;
}
// case1, 2.2
arr[i] = arr[j];
i++;
}
// post- processing: if have trailing sapce
if (i > 0 && arr[i - 1] == ' ') {
return new String(arr, 0, i - 1);
}
return new String(arr, 0, i);
Type2 char de-duplication
Remove Adjacent Repeated Characters I
两个pointer
Remove Adjacent Repeated Characters IV
用一个stack来记录并比较是否重复
但其实可以直接用两个指针来做
// arr[i] as the top of a stack
for (int j = 1; j < arr.length; j++) {
if (i == -1 || arr[j] != arr[i]) {
arr[++i] = arr[j];
} else {
// pop and ignore all the consecutive duplicates
i--;
while (j + 1 < arr.length && arr[j] == arr[j + 1]) {
j++;
}
Type3 sub str
Determine If One String Is Another's Substring
int n = large.length();
int m = small.length();
for (int i = 0; i <= n - m; i++) {
int j = 0;
while (j < m) {
if (large.charAt(i + j) != small.charAt(j)) {
break;
}
j++;
}
if (j == m) {
return i;
}
}
return -1;
