《数据结构与算法之美》学习指导手册
复杂度分析
1：复杂度分为：时间复杂度、空间复杂度。
2：时间复杂度的计算和代码的结构，代码的执行次数有关系。
3：空间复杂度的计算和数据结构，存储资源有关系。
4：复杂度和常系数无关如：O(n)、O(2n)、O(n/2)都表示O(n)复杂度
5：多个复杂度相加，取高次项复杂度为最终结果，如：O(n^3+n^2+n)那么这个复杂度就是O(n^3)
6：常见的一些时间复杂度有：（1）对一个数组遍历循环，若数组长度为n，那么时间复杂度为O(n)。（2）嵌套遍历，若外层遍历n次，内层遍历m次，则时间复杂度为O(m*n)。（3）若两个遍历不是嵌套的，还是顺序的，那么时间复杂度依然是O(n)+O(n) = O(2n) = O(n)，最终依然为O(n)。（4）若n和程序执行的次数无关，那么时间复杂度始终为O(1)；
数组、栈、队列
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
寻址公式：a[i]_address = base_address + i * data_type_size
为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？
从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：a[k]_address = base_address + k * type_size但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：a[k]_address = base_address + (k-1)*type_size对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。
链表
常见的三种缓存淘汰策略：
- 先进先出策略 FIFO（First In，First Out）
- 最少使用策略 LFU（Least Frequently Used）
- 最近最少使用策略 LRU（Least Recently Used）
单链表反转
1
2
3
4
5
6
7
8
9
10
11
12
13
| public ListNode reverseList(ListNode head) {
ListNode next = null;
ListNode prev = null;
ListNode curr = head;
while(curr!=null){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
|
链表中环的检测
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public ListNode detectCycle(ListNode head) {
ListNode fast= head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast){
fast = head;
while(slow!=fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
|
两个有序的链表合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode temp = l1.val<l2.val?l1:l2;
temp.next = mergeTwoLists(temp.next,l1.val>=l2.val?l1:l2);
return temp;
}
private ListNode mergeTwoLists(ListNode l1,ListNode l2){
if( l1==null)return l2;
if( l2==null)return l1;
ListNode res = l1.val<l2.val?l1:l2;
res.next = mergeTwoLists(res.next,l1.val>=l2.val?l1:l2);
return res;
}
|
删除链表倒数第 n 个结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public int kthToLast(ListNode head, int k) {
ListNode fast = head;
for(int i = 0; i <= k; i++){
fast = fast.next;
}
ListNode slow = head;
while(fast!=null){
fast = fast.next;
slow = slow.next;
}
return slow.val;
}
|
删除给定的节点
1
2
| node.val = node.next.val;
node.next = node.next.next;
|
求链表的中间结点
1
2
3
4
5
6
7
8
9
10
| public int middle(NodeList head){
NodeList fast = head;
NodeList slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
return slow.val;
}
|
删除链表中等于给定值 *val* 的所有节点
1
2
3
4
5
6
7
| public ListNode delete(NodeList head , int val){
if(head==null){
return head;
}
head.next = delete(head.next,val);
return head.val==val?head.next:head;
}
|
两数相加
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
| Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int sum = carry;
sum += stack1.isEmpty()? 0: stack1.pop();
sum += stack2.isEmpty()? 0: stack2.pop();
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
carry = sum / 10;
}
return head;
|
递归
排序、二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int binarySearch(int[] nums, int target, int low, int high) {
if (low > high) {
return -1;
}
int middle = low + (high - low) / 2;
if (nums[middle] == target) {
return middle;
}
if (target < nums[middle]) {
return binarySearch(nums, target, low, middle - 1);
} else {
return binarySearch(nums, target, middle + 1, high);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int binarySearch(int[] nums, int target, int low, int high) {
while (low <= high) {
int middle = low + (high - low) / 2;
if (nums[middle] == target) {
return middle;
}
if (target < nums[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
|
颜色分类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public void sortColors(int[] nums){
int numsLength = nums.length;
int ptr = 0;
for(int i=0; i<numsLength;i++){
if(nums[i]==0){
int temp = nums[i];
nums[i]=nums[ptr];
nums[ptr]=temp;
++ptr;
}
}
for(int i=0; i<numsLength;i++){
if(nums[i]==1){
int temp = nums[i];
nums[i]=nums[ptr];
nums[ptr]=temp;
++ptr;
}
}
}
|
散列表
二叉树
堆和堆排序
BF/RK字符串匹配算法
Trie树
图的表示
深度广度优先搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| boolean dfs(int maze[][], int x, int y) {
if (x == B[0] && y == B[1]) {
return true;
}
maze[x][y] = -1;
for (int d = 0; d < 4; d++) {
int i = x + dx[d], j = y + dy[d];
if (isSafe(maze, i, j) && dfs(maze, i, j)) {
return true;
}
}
return false;
}
|
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
| boolean dfs(int maze[][], int x, int y) {
Stack<Integer[]> stack = new Stack<>();
stack.push(new Integer[] {x, y});
maze[x][y] = -1;
while (!stack.isEmpty()) {
Integer[] pos = stack.pop();
x = pos[0]; y = pos[1];
if (x == B[0] && y == B[1]) {
return true;
}
for (int d = 0; d < 4; d++) {
int i = x + dx[d], j = y + dy[d];
if (isSafe(maze, i, j)) {
stack.push(new Integer[] {i, j});
maze[i][j] = -1;
}
}
}
return false;
}
|
四种算法原理
跳表
拓扑排序、最短路径、A* 算法
B+树
位图
BM、KMP、AC自动机
红黑树
哈希算法
高级篇、实战等其他内容
