算法笔记

字数统计: 3.4k   |   阅读时长≈ 17 分钟

链表

判断回文

1.和出栈比较

2.快慢指针（右边进栈和左边比较）

3.空间O(1)快慢指针把中赋为null右边指针反转，头尾比较等于null退出，把链表复原

栈方法简单（笔试用）

改原链表的方法就需要注意边界了（面试用）

判断是否有环

快慢指针相遇有环（在环上相遇）

快指针为null无环

快指针从头再来慢指针还在原地快慢指针每次走一步，最终会在第一个入环节点处相遇

布隆过滤器

样本量

失误率

判断一个32位的数是否为2的幂（用位运算）

x&（x-1）==0

判断一个32位的数是否为4的幂（用位运算）

1.是2的幂

2.x&(0x55555555)!=0 //0x55555555==(010101…01)

计划搜索缓存

跳过重复条件

二叉树序列化和反序列化

层次遍历序列化
层次遍历反序列化
二叉树的宽度优先遍历（用队列）
最大宽度
最大宽度不用Map
给二叉树中的某个节点，返回该节点的后继节点

二叉树的结构

二叉树的递归套路

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。给定一个输入参数N，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。例如:N=1时，打印: down N=2时，打印: down down up

思路：用递归模拟了树（树没有建出来）

左右高度相差大于1

给定一颗二叉树的头节点head，任何两个节点之间都存在距离，返回整颗二叉树的最大距离
给定一颗二叉树的头节点head，返回这颗二叉树中最大的二叉树搜索子树的头节点
派对的最大快乐值

打表找规律（暴力找规则）

牛羊吃草

规律解法

连续正数和的数

规律解法

矩阵处理技巧

1.zigzag打印矩阵

1 2 3

4 5 6 –> 打印输出 124753689

7 8 9

2.转圈打印矩阵
原地旋转正方形矩阵

贪心算法求解的标准过程

解题套路
宣讲次数最多

结构

暴力解

第二种

排序（根据谁的时间短排序）

最少灯

暴力法

贪心

分金条

贪心

最大盈利
并查集

简写if

分类用户（代码与上面的通用）

图

基本结构
宽度优先遍历
深度优先遍历
拓扑排序
最小生成树（Kruskal）利用并查集
Prim
Dijkstra（迪特拉）

改进

源码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
public class Dijkstra {

	public static HashMap<Node, Integer> dijkstra1(Node from) {
		HashMap<Node, Integer> distanceMap = new HashMap<>();
		distanceMap.put(from, 0);
		// 打过对号的点
		HashSet<Node> selectedNodes = new HashSet<>();
		Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
		while (minNode != null) {
			//  原始点  ->  minNode(跳转点)   最小距离distance
			int distance = distanceMap.get(minNode);
			for (Edge edge : minNode.edges) {
				Node toNode = edge.to;
				if (!distanceMap.containsKey(toNode)) {
					distanceMap.put(toNode, distance + edge.weight);
				} else { // toNode 
					distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
				}
			}
			selectedNodes.add(minNode);
			minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
		}
		return distanceMap;
	}

	public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
		Node minNode = null;
		int minDistance = Integer.MAX_VALUE;
		for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
			Node node = entry.getKey();
			int distance = entry.getValue();
			if (!touchedNodes.contains(node) && distance < minDistance) {
				minNode = node;
				minDistance = distance;
			}
		}
		return minNode;
	}

	public static class NodeRecord {
		public Node node;
		public int distance;

		public NodeRecord(Node node, int distance) {
			this.node = node;
			this.distance = distance;
		}
	}

	public static class NodeHeap {
		private Node[] nodes; // 实际的堆结构
		// key 某一个node， value 上面堆中的位置
		private HashMap<Node, Integer> heapIndexMap;
		// key 某一个节点， value 从源节点出发到该节点的目前最小距离
		private HashMap<Node, Integer> distanceMap;
		private int size; // 堆上有多少个点

		public NodeHeap(int size) {
			nodes = new Node[size];
			heapIndexMap = new HashMap<>();
			distanceMap = new HashMap<>();
			size = 0;
		}

		public boolean isEmpty() {
			return size == 0;
		}

		// 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
		// 判断要不要更新，如果需要的话，就更新
		public void addOrUpdateOrIgnore(Node node, int distance) {
			if (inHeap(node)) {
				distanceMap.put(node, Math.min(distanceMap.get(node), distance));
				insertHeapify(heapIndexMap.get(node));
			}
			if (!isEntered(node)) {
				nodes[size] = node;
				heapIndexMap.put(node, size);
				distanceMap.put(node, distance);
				insertHeapify(size++);
			}
		}

		public NodeRecord pop() {
			NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
			swap(0, size - 1);
			heapIndexMap.put(nodes[size - 1], -1);
			distanceMap.remove(nodes[size - 1]);
			// free C++同学还要把原本堆顶节点析构，对java同学不必
			nodes[size - 1] = null;
			heapify(0, --size);
			return nodeRecord;
		}

		private void insertHeapify(int index) {
			while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
				swap(index, (index - 1) / 2);
				index = (index - 1) / 2;
			}
		}

		private void heapify(int index, int size) {
			int left = index * 2 + 1;
			while (left < size) {
				int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
						? left + 1
						: left;
				smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
				if (smallest == index) {
					break;
				}
				swap(smallest, index);
				index = smallest;
				left = index * 2 + 1;
			}
		}

		private boolean isEntered(Node node) {
			return heapIndexMap.containsKey(node);
		}

		private boolean inHeap(Node node) {
			return isEntered(node) && heapIndexMap.get(node) != -1;
		}

		private void swap(int index1, int index2) {
			heapIndexMap.put(nodes[index1], index2);
			heapIndexMap.put(nodes[index2], index1);
			Node tmp = nodes[index1];
			nodes[index1] = nodes[index2];
			nodes[index2] = tmp;
		}
	}

	// 改进后的dijkstra算法
	// 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
	public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
		NodeHeap nodeHeap = new NodeHeap(size);
		nodeHeap.addOrUpdateOrIgnore(head, 0);
		HashMap<Node, Integer> result = new HashMap<>();
		while (!nodeHeap.isEmpty()) {
			NodeRecord record = nodeHeap.pop();
			Node cur = record.node;
			int distance = record.distance;
			for (Edge edge : cur.edges) {
				nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
			}
			result.put(cur, distance);
		}
		return result;
	}

}

暴力递归

什么暴力递归可以继续优化
汉诺塔

递归

非递归

逆序栈
字符串的子序列
无重复子序列
字符串全排列
无重复全排列（分支限界）
数字字符转化
背包问题

另一种

选牌
n皇后

利用位移

货币凑整
1
2
3
4
5
6
7
8
9
10
11
// arr[index....] 所有的面值，每一个面值都可以任意选择张数，组成正好rest这么多钱，方法数多少？
public static int process(int[] arr, int index, int rest) {
	if (index == arr.length) { // 没钱了
		return rest == 0 ? 1 : 0;
	}
	int ways = 0;
	for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
		ways += process(arr, index + 1, rest - (zhang * arr[index]));
	}
	return ways;
}

递归改动态规划（题目同上面相同）

步骤：暴力递归（重复解）->可变参数（不讲究组织）->记忆化搜索（精细化组织）->经典动态规划
回到原始位置

2

背包问题

2

数字字符转化
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 从右往左的动态规划
// 就是上面方法的动态规划版本
// dp[i]表示：str[i...]有多少种转化方式
public static int dp1(String s) {
	if (s == null || s.length() == 0) {
		return 0;
	}
	char[] str = s.toCharArray();
	int N = str.length;
	int[] dp = new int[N + 1];
	dp[N] = 1;
	for (int i = N - 1; i >= 0; i--) {
		if (str[i] != '0') {
			int ways = dp[i + 1];
			if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
				ways += dp[i + 2];
			}
			dp[i] = ways;
		}
	}
	return dp[0];
}

// 从左往右的动态规划
// dp[i]表示：str[0...i]有多少种转化方式
public static int dp2(String s) {
	if (s == null || s.length() == 0) {
		return 0;
	}
	char[] str = s.toCharArray();
	int N = str.length;
	if (str[0] == '0') {
		return 0;
	}
	int[] dp = new int[N];
	dp[0] = 1;
	for (int i = 1; i < N; i++) {
		if (str[i] == '0') {
			// 如果此时str[i]=='0'，那么他是一定要拉前一个字符(i-1的字符)一起拼的，
			// 那么就要求前一个字符，不能也是‘0’，否则拼不了。
			// 前一个字符不是‘0’就够了嘛？不够，还得要求拼完了要么是10，要么是20，如果更大的话，拼不了。
			// 这就够了嘛？还不够，你们拼完了，还得要求str[0...i-2]真的可以被分解！
			// 如果str[0...i-2]都不存在分解方案，那i和i-1拼成了也不行，因为之前的搞定不了。
			if (str[i - 1] == '0' || str[i - 1] > '2' || (i - 2 >= 0 && dp[i - 2] == 0)) {
				return 0;
			} else {
				dp[i] = i - 2 >= 0 ? dp[i - 2] : 1;
			}
		} else {
			dp[i] = dp[i - 1];
			if (str[i - 1] != '0' && (str[i - 1] - '0') * 10 + str[i] - '0' <= 26) {
				dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
			}
		}
	}
	return dp[N - 1];
}
选牌
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int win(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] fmap = new int[N][N];
		int[][] gmap = new int[N][N];
		for (int i = 0; i < N; i++) {
			fmap[i][i] = arr[i];
		}
		for (int startCol = 1; startCol < N; startCol++) {
			int L = 0;
			int R = startCol;
			while (R < N) {
				fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
				gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
				L++;
				R++;
			}
		}
		return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
}
货币凑整
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
35
36
37
// arr[index....] 所有的面值，每一个面值都可以任意选择张数，组成正好rest这么多钱，方法数多少？
public static int dp1(int[] arr, int aim) {
	if (arr == null || arr.length == 0 || aim < 0) {
		return 0;
	}
	int N = arr.length;
	int[][] dp = new int[N + 1][aim + 1];
	dp[N][0] = 1;
	for (int index = N - 1; index >= 0; index--) {
		for (int rest = 0; rest <= aim; rest++) {
			int ways = 0;
			for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
				ways += dp[index + 1][rest - (zhang * arr[index])];
			}
			dp[index][rest] = ways;
		}
	}
	return dp[0][aim];
}

public static int dp2(int[] arr, int aim) {
	if (arr == null || arr.length == 0 || aim < 0) {
		return 0;
	}
	int N = arr.length;
	int[][] dp = new int[N + 1][aim + 1];
	dp[N][0] = 1;
	for (int index = N - 1; index >= 0; index--) {
		for (int rest = 0; rest <= aim; rest++) {
			dp[index][rest] = dp[index + 1][rest];
			if (rest - arr[index] >= 0) {
				dp[index][rest] += dp[index][rest - arr[index]];
			}
		}
	}
	return dp[0][aim];
}
贴纸字符串
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
public static int minStickers2(String[] stickers, String target) {
	int N = stickers.length;
	// 关键优化(用词频表替代贴纸数组)
	int[][] counts = new int[N][26];
	for (int i = 0; i < N; i++) {
		char[] str = stickers[i].toCharArray();
		for (char cha : str) {
			counts[i][cha - 'a']++;
		}
	}
	int ans = process2(counts, target);
	return ans == Integer.MAX_VALUE ? -1 : ans;
}

// stickers[i] 数组，当初i号贴纸的字符统计 int[][] stickers -> 所有的贴纸
// 每一种贴纸都有无穷张
// 返回搞定target的最少张数
// 最少张数
public static int process2(int[][] stickers, String t) {
	if (t.length() == 0) {
		return 0;
	}
	// target做出词频统计
	// target  aabbc  2 2 1..
	//                0 1 2..
	char[] target = t.toCharArray();
	int[] tcounts = new int[26];
	for (char cha : target) {
		tcounts[cha - 'a']++;
	}
	int N = stickers.length;
	int min = Integer.MAX_VALUE;
	for (int i = 0; i < N; i++) {
		// 尝试第一张贴纸是谁
		int[] sticker = stickers[i];
		// 最关键的优化(重要的剪枝!这一步也是贪心!)
		if (sticker[target[0] - 'a'] > 0) {
			StringBuilder builder = new StringBuilder();
			for (int j = 0; j < 26; j++) {
				if (tcounts[j] > 0) {
					int nums = tcounts[j] - sticker[j];
					for (int k = 0; k < nums; k++) {
						builder.append((char) (j + 'a'));
					}
				}
			}
			String rest = builder.toString();
			min = Math.min(min, process2(stickers, rest));
		}
	}
	return min + (min == Integer.MAX_VALUE ? 0 : 1);
}

public static int minStickers3(String[] stickers, String target) {
	int N = stickers.length;
	int[][] counts = new int[N][26];
	for (int i = 0; i < N; i++) {
		char[] str = stickers[i].toCharArray();
		for (char cha : str) {
			counts[i][cha - 'a']++;
		}
	}
	HashMap<String, Integer> dp = new HashMap<>();
	dp.put("", 0);
	int ans = process3(counts, target, dp);
	return ans == Integer.MAX_VALUE ? -1 : ans;
}

public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp) {
	if (dp.containsKey(t)) {
		return dp.get(t);
	}
	char[] target = t.toCharArray();
	int[] tcounts = new int[26];
	for (char cha : target) {
		tcounts[cha - 'a']++;
	}
	int N = stickers.length;
	int min = Integer.MAX_VALUE;
	for (int i = 0; i < N; i++) {
		int[] sticker = stickers[i];
		if (sticker[target[0] - 'a'] > 0) {
			StringBuilder builder = new StringBuilder();
			for (int j = 0; j < 26; j++) {
				if (tcounts[j] > 0) {
					int nums = tcounts[j] - sticker[j];
					for (int k = 0; k < nums; k++) {
						builder.append((char) (j + 'a'));
					}
				}
			}
			String rest = builder.toString();
			min = Math.min(min, process3(stickers, rest, dp));
		}
	}
	int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
	dp.put(t, ans);
	return ans;
}
两个字符串的最长公共子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int longestCommonSubsequence(char[] str1, char[] str2) {
	int N = str1.length;
	int M = str2.length;
	int[][] dp = new int[N][M];
	dp[0][0] = str1[0] == str2[0] ? 1 : 0;
	for (int i = 1; i < N; i++) {
		dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
	}
	for (int j = 1; j < M; j++) {
		dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
	}
	for (int i = 1; i < N; i++) {
		for (int j = 1; j < M; j++) {
			dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
			if (str1[i] == str2[j]) {
				dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
			}
		}
	}
	return dp[N - 1][M - 1];
}
洗咖啡杯机
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
35
36
37
38
39
40
// 贪心+优良尝试改成动态规划
public static int minTime2(int[] arr, int n, int a, int b) {
	PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
	for (int i = 0; i < arr.length; i++) {
		heap.add(new Machine(0, arr[i]));
	}
	int[] drinks = new int[n];
	for (int i = 0; i < n; i++) {
		Machine cur = heap.poll();
		cur.timePoint += cur.workTime;
		drinks[i] = cur.timePoint;
		heap.add(cur);
	}
	return bestTimeDp(drinks, a, b);
}
public static int bestTimeDp(int[] drinks, int wash, int air) {
	int N = drinks.length;
	int maxFree = 0;
	for (int i = 0; i < drinks.length; i++) {
		maxFree = Math.max(maxFree, drinks[i]) + wash;
	}
	int[][] dp = new int[N + 1][maxFree + 1];
	for (int index = N - 1; index >= 0; index--) {
		for (int free = 0; free <= maxFree; free++) {
			int selfClean1 = Math.max(drinks[index], free) + wash;
			if (selfClean1 > maxFree) {
				break; // 因为后面的也都不用填了
			}
			// index号杯子 决定洗
			int restClean1 = dp[index + 1][selfClean1];
			int p1 = Math.max(selfClean1, restClean1);
			// index号杯子 决定挥发
			int selfClean2 = drinks[index] + air;
			int restClean2 = dp[index + 1][free];
			int p2 = Math.max(selfClean2, restClean2);
			dp[index][free] = Math.min(p1, p2);
		}
	}
	return dp[0][0];
}

设计暴力递归过程的原则

打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2015-2025 Immanuel
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

微信