1. 数组
1.1. 不用中间变量交换两个数
1.2. 找到出现奇数次的数
https://www.bilibili.com/video/BV1zu411X744?p=8&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204
1.3. 找到 2 个出现奇数次的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static int bit1counts(int N) {
int count = 0;
// 011011010000
// 000000010000 1 // 011011000000
//
while(N != 0) {
int rightOne = N & ((~N) + 1);
count++;
N ^= rightOne;
// N -= rightOne
}
return count;
}
|
1.4. 数字中 1 的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static int bit1counts(int N) {
int count = 0;
// 011011010000
// 000000010000 1 // 011011000000
//
while(N != 0) {
int rightOne = N & ((~N) + 1);
count++;
N ^= rightOne;
// N -= rightOne
}
return count;
}
|
1.5. 合并两个有序数组 -L88
https://www.bilibili.com/video/BV1ya4y1H7gH/?spm_id_from=333.337.search-card.all.click&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204
1.5.1. 双指针倒序复制
1.5.2. 有剩余情况
1.5.3. 无剩余情况
动图中有个小错误，在最后一步，p1 指针应该没动，只有 p 和 p2 向左移动了一步，p 和 p1 都指向 1 所在的位置。p2 越界了跳出 while 循环，此时 p2=-1，走到下面一句：System.arraycopy(nums2,0,num1,0,0)，相当于没有变化，即 nums2 已经全部转移到了 nums1 中，最后的扫尾动作相当于没有变化。
1.5.4. 代码实现
1
2
3
4
5
6
7
8
9
10
11
| public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1;
int p2 = n - 1;
int p = m + n - 1;
while ((p1 >= 0) && (p2 >= 0))
nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}
|
2. 链表
2.1. 反转链表
3. 树
3.1. 层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static void levelOrder(TreeNode root, int index, List result) {
if (root == null) return;
int length = result.size();
if (length <= index) {
for (int j = 0; j <= index - length; j++) {
result.add(length + j, null);
}
}
result.set(index, root.val);
levelOrder(root.left, 2*index, result);
levelOrder(root.right, 2*index + 1, result);
}
|
3.2. 树的最大宽度
3.2.1. 使用 map
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
30
31
32
33
34
| public static int maxWidthUseMap(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
HashMap<Node, Integer> levelMap = new HashMap<>();
levelMap.put(head, 1);
int curLevel = 1;
int curLevelNodes = 0;
int max = 0;
while (!queue.isEmpty()) {
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);
if (cur.left != null) {
levelMap.put(cur.left, curNodeLevel + 1);
queue.add(cur.left);
}
if (cur.right != null) {
levelMap.put(cur.right, curNodeLevel + 1);
queue.add(cur.right);
}
if (curNodeLevel == curLevel) {
curLevelNodes++;
} else {
max = Math.max(max, curLevelNodes);
curLevel++;
curLevelNodes = 1;
}
}
max = Math.max(max, curLevelNodes);
return max;
}
|
3.2.2. 不用 map
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
| public static int maxWidthNoMap(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
Node curEnd = head;
Node nextEnd = null;
int max = 0;
int curLevelNodes = 0;
while (!queue.isEmpty()) {
Node cur = queue.poll();
if (cur.left != null) {
queue.add(cur.left);
nextEnd = cur.left;
}
if (cur.right != null) {
queue.add(cur.right);
nextEnd = cur.right;
}
curLevelNodes++;
if (cur == curEnd) {
max = Math.max(max, curLevelNodes);
curLevelNodes = 0;
curEnd = nextEnd;
}
}
return max;
}
|
3.3. 序列化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static Queue<String> preSerial(Node head) {
Queue<String> ans = new LinkedList<>();
pres(head, ans);
return ans;
}
public static void pres(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ans.add(String.valueOf(head.value));
pres(head.left, ans);
pres(head.right, ans);
}
}
|
4. 图
5. ForkJoin
分而治之思想
https://www.bilibili.com/video/BV11A411H7Xh?p=7&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204
6. 等概率生成器
https://www.bilibili.com/video/BV1qd4y1B7XC?p=12&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204
7. 快慢指针
/Users/taylor/Nutstore Files/Obsidian_data/pages/002-schdule/001-Arch/001-Subject/001- 基础知识专题/000- 数据结构与算法/黑马 - 数据结构与算法资料/文档/04_ 线性表.pdf
8. 从后往前节省空间
https://www.bilibili.com/video/BV1iE411s7Gi/?spm_id_from=333.337.search-card.all.click&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204
9. 参考
https://space.bilibili.com/390775036
9.1. 左程云算法
https://www.bilibili.com/video/BV1qd4y1B7XC/?p=13&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204
/Users/taylor/Nutstore Files/Obsidian_data/pages/002-schdule/001-Arch/001-Subject/001- 基础知识专题/000- 数据结构与算法/左神算法资料
微信
支付宝
