1. 首页
  2. 文章中心
  3. 算法

【算法学习】框架记录动态规划框架回溯算法解题套路BFS广度优先搜索双指针技巧滑动窗口带权并查集

96 阅读 0 评论
我是靠谱客的博主 曾经芹菜，这篇文章主要介绍【算法学习】框架记录动态规划框架回溯算法解题套路BFS广度优先搜索双指针技巧滑动窗口带权并查集，现在分享给大家，希望可以做个参考。

动态规划框架

以斐波那契数列为例
带备忘录的递归解法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int fib(int N) {
	if (N == 0) return 0;
	//将备忘录全初始化0
	vector<int> memo(N + 1, 0);
	//进行带备忘录的递归
	return helper(memo, N);
}

int helper(vector<int>& memo, int n) {
	//base case
	if (n == 1 || n == 2) return 1;
	//已经计算过
	if (memo[n] != 0) return memo[0];
	memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
	return memo[n];
}

dp数组的迭代解法

复制代码
1
2
3
4
5
6
7
8
9
10
11
int fib(int N) {
	if (N == 0) return 0;
	if (N == 1 || N == 2) return 1;
	vector<int> dp(N + 1, 0);
	//base case
	dp[1] = dp[2] = 1;
	for (int i = 3; i <= N; i++)
		dp[i] = dp[i - 1] + dp[i - 2];
	return dp[N];
}

凑零钱问题的迭代解法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int coinChange(vector<int>$ coins, int amount) {
	//数组大小为amount+1，初始值也为amount+1
	vector<int> dp(amount + 1, amount + 1);
	//base case
	dp[0] = [0];
	//外层for循环遍历所有状态的所有取值
	for (int i = 0; i < dp.size(); i++) {
		//内层for循环求所有选择的最小值
		for (int coin : coins) {
			//子问题无解，跳过
			if (i - coin < 0) continue;
			dp[i] = min(dp[i], 1 + dp[i - coin]);
		}
	}
	return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

回溯算法解题套路

复制代码
1
2
3
4
5
6
7
8
9
10
11
result = []
def backtrack(路径，选择列表):
	if 满足判断条件:
		result.add(路径)
		return
	
	for 选择 in 选择列表:
		做选择
		backtrack(路径，选择列表)
		撤销选择

List是stl实现的双向链表，与向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢。使用时需要添加头文件。要用list，需要

复制代码
1
2
#include <list>

全排列的代码示例

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len) {
	// 所有数都填完了
	if (first == len) {
		res.emplace_back(output);
		return;
	}
	for (int i = first; i < len; ++i) {
		// 动态维护数组
		swap(output[i], output[first]);
		// 继续递归填下一个数
		backtrack(res, output, first + 1, len);
		// 撤销操作
		swap(output[i], output[first]);
	}
}
vector<vector<int>> permute(vector<int>& nums) {
	vector<vector<int> > res;
	backtrack(res, nums, 0, (int)nums.size());
	return res;
}

有关emplace_back()，其实和push_back用处一样，实现原理不同
emplace_back理解

N皇后问题

复制代码
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
vector<vector<string>> res;

/*输入棋盘边长n，返回所有的合法放置方式*/
vector<vector<string>> splveNQueens(int n) {
	// "."表示空，'Q'表示皇后，初始化空棋盘
	vector<string> board(n, string(n, '''''.''''');
	backtrack(board, 0);
	return res;
}

//路径：board中小于row的那些行都已经成功放置皇后
//选择列表：弟row行的所有列都是放置皇后的选择
//结束条件：row超过board的最后一行，说明棋盘放满了
void backtrack(vector<string>& board, int row) {
	//触发结束条件
	if (row == board.size()) {
		res.push_back(board);
		return;
	}
	int n = board[row].size();
	for (int col = 0; col < n; col++) {
		//排除不合法选择
		if (isValid(board, row, col))
			continue;
		//做选择
		board[row][col] = 'Q';
		//进行下一行决策
		backtrack(board, row + 1);
		//撤销选择
		board[row][col] = '.';
	}
}

BFS广度优先搜索

复制代码
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
int BFS(Node start,Node target){
	/*
		这是一个BFS算法的代码框架
		return：返回从start到target的最短步数
		start：起始点
		target：终点
	*/
	
	Queue<Node> q;
	Set<Node> visited;	//避免走回头路
	
	q.offer(start);	//将起点加入队列
	visited.add(start);
	int step = 0;	//纪录扩散的步数

	while(q not empty){
		int sz = q.size();
		for(int i = 0; i<sz; i++){
			Node cur = q.poll();

			//判断是否到终点
			if(cur is target)
				return step;
			
			//将cur相邻节点加入队列
			for(Node x: cur.adj())	//cur.adj()泛指与cur相邻的节点
				if(x not in visited){
					q.offer(x);
					visited.add(x);
				}
		}	
		step++;	//更新步数
	}
}

求二叉树的最小高度

复制代码
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
int minDepth(TreeNode root){
	/*
		这是一个求二叉树最小高度的函数
		return：二叉树的最小高度
		root：根节点
	*/
	if(root == NULL) return 0;
	
	Queue<TreeNode> q;

	q.offer(root);	//将起点加入队列
	int depth = 1;	

	while(!q.isEmpty()){
		int sz = q.size();
		for(int i = 0; i<sz; i++){
			TreeNode cur = q.poll();

			//判断是否到终点
			if(cur.left == NULL && cur.right == NULL)
				return depth;
			
			//将cur相邻节点加入队列
			if(cur.left != NULL)
				q.offer(cur.left);
			if(cur.right != NULL)
				q.offer(cur.right);
		}	
		depth++;	//更新步数
	}
	return depth;
}

解开密码锁的最少次数

复制代码
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
int openLock(String[] deadends,String target){
	//纪录需要跳过的死亡密码
	Set<String> deads = new HashSet<>();
	
	for(String s:deadends) 
		dead.add(s);

	//纪录已经穷举过的密码
	set<String> visited = new HashSet<>();
	
	Queue<String> q = new LinkedList<>();
	
	//从起点开始启动广度优先搜索
	int step = 0;
	q.offer("0000");
	visited.add("0000");

	while(!q.isEmpty){
		int sz = q.size();
		for(int i = 0;i<sz;i++){
			string cur = q.poll();
				
			//判断密码是否合法
			if(deads.contains(cur)
				continue;
			if(cur.equals(target))
				return step;
		}

		//将一个节点的未遍历相邻节点加入队列
		for(int j=0;j<4;j++){
			String up = plusOne(cur,j);
			if(!visited.contains(up){
				q.offer(up);
				visited.add(up);
			}
			String down = minusOne(cur,j);
			if(!visited.contains(down){
				q.offer(down);
				visited.add(down);
			}
		}
		step++;
	}
	return -1;
}

其它代码：

复制代码
1
2
3
4
5
6
7
8
9
String plusOne(String s,int j){
	char[] ch = s.toCharArray();
	if(ch[j] == '9')
		ch[j] = '0';
	else
		ch[j] += 1;
	return new String(ch);
}
复制代码
1
2
3
4
5
6
7
8
9
String downOne(String s,int j){
	char[] ch = s.toCharArray();
	if(ch[j] == '0')
		ch[j] = '9';
	else
		ch[j] -= 1;
	return new String(ch);
}

双指针技巧

C++ List使用方法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//判断链表是否有环
bool hasCycle(ListNode head) {
	ListNode fast, slow;
	//初始化快慢指针指向头节点
	fast = slow = head;
	while (fast != NULL && fast.next != NULL) {
		//快指针每次前进两步
		fast = fast.next.next;
		//满指针每次前进一步
		slow = slow.next;
		//如果存在环，快慢指针必定相遇
		if (fast == slow) 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
//已知链表有环，返回环的起始位置
bool detectCycle(ListNode head) {
	ListNode fast, slow;
	fast = slow = head;
	while (fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
		if (fast == slow) break;
	}
	//上面代码类似于hasCycle函数
	//先把一个指针重新指向head
	slow = head;
	while (slow != fast) {
		//两个指针以相同的速度前进
		fast = fast.next;
		slow = slow.next;
	}
	//两个指针相遇的单链表结点就是环的起点
	return slow;
}
复制代码
1
2
3
4
5
6
7
8
//寻找无环单链表的中点
while (fast != NULL && fast.next != NULL) {
	fast = fast.next.next;
	slow = slow.next;
}
//slow就已经在中间了
return slow;
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//寻找单链表的倒数第k个元素
ListNode slow, fast;
slow = fast = head;

while (k-- > 0)
	fast = fast.next;

while (fast != null) {
	slow = slow.next;
	fast = fast.next;
}

return slow;
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//二分搜索
int binarySearch(int[] nums, int target) {
	//左右指针在数组两端初始化
	int left = 0;
	int right = nums.length - 1;
	while (left <= right) {
		int mid = (right + left) / 2;
		if (nums[mid] == target)
			return mid;
		else if (nums[mid] < target)
			left = mid + 1;
		else if (nums[mid] > target)
			right = mid - 1;
	}
	return -1;
}

C++使用new创建数组并初始化
注意C++中求数组的大小，如果将数组作为参数传递给函数来计算的话，计算出来的是错的。所以应该先算出来再当作参数传进去比较合适。

可以设置用一个模板来求数组大小，如下

复制代码
1
2
3
4
5
6
7
8
9
template<class T>

int length(T& arr)
{
	//cout << sizeof(arr[0]) << endl;
	//cout << sizeof(arr) << endl;
	return sizeof(arr) / sizeof(arr[0]);
}

求两数之和的完整程序：

复制代码
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
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include<unordered_set>
#include<queue>
#include <list>
#include<stack>
#include<set>
using namespace std;

template<class T>

int length(T& arr)
{
	//cout << sizeof(arr[0]) << endl;
	//cout << sizeof(arr) << endl;
	return sizeof(arr) / sizeof(arr[0]);
}


//两数之和
int* twoSum (int nums[], int target, int le) {
	//左右指针在数组的两端初始化
	int left = 0, right = le - 1;
	while (left < right) {
		int sum = nums[left] + nums[right];
		if (sum == target) {
			//题目的要求索引是从1开始的
			return new int[2] {left + 1, right + 1 };
		}
		else if (sum < target) {
			left++; //让sum大一点
		}
		else if (sum > target) {
			right--;//让sum小一点
		}
	}
	return new int[2] {-1, -1};
}

int main() {
	int a;
	int b[7] = { 1, 2, 3, 4, 5, 6, 7 };
	printf("%d", length(b));
	scanf_s("%d", &a);
	int *c = twoSum(b, a, length(b));
	printf("%d%d", c[0], c[1]);
}

反转数组

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
//反转数组
void reverse(int nums[]) {
	int left = 0;
	int right = nums.length - 1;
	while (left < right) {
		//交换两指针结点处的值
		int temp = nums[left];
		nums[left] = nums[right];
		nums[right] = temp;
		left++; right--;
	}
}

滑动窗口

框架代码

复制代码
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
void slideingWindow(string s, string t) {
	unordered_map<char, int> need, window;
	for (char c : t) need[c]++;

	int left = 0, right = 0;
	int valid = 0;
	while (right < s.size) {
		//c是将要移入窗口的字符
		char c = s[right];
		//右移窗口
		right++;
		//进行窗口内数据的一系列更新
		//···
		//debug输出
		printf("windo[%d,%d]n", left, right);

		//判断左侧窗口是否要收紧
		while (window needs shrink) {
			//d是将要移除的字符
			char d = s[left];
			//左移窗口
			left++;
			//进行窗口内的一系列更新
			//···
		}
	}
}

最小覆盖字串问题

复制代码
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
string minWindow(string s, string t) {
	unordered_map<char, int> need, window;
	for (char c : t) need[c]++;

	int left = 0, right = 0;
	int valid = 0;
	//记录最小覆盖子串的起始索引及长度
	int start = 0, len = INT_MAX;
	while (right < s.size()) {
		//c是将要移入窗口的字符
		char c = s[right];
		//右移窗口
		right++;
		//进行窗口内数据更新等操作
		if (need.count(c)) {
			window[c]++;
			if (window[c] == need[c])
				valid++;
		}
		//判断左侧窗口是否要收紧
		while (valid == need.size()) {
			//在这里更新最小覆盖子串
			if (right - left < len) {
				start = left;
				len = right - left;
			}
			//d是将移出窗口的字符
			char d = s[left];
			//左移窗口
			left++;
			//进行窗口内数据更新
			if (need.count(d)) {
				if (window[d] == need[d])
					valid--;
				window[d]--;
			}
		}
	}
	//返回最小覆盖子串
	return len == INT_MAX ? "" : s.substr(start, len);
}

最长无重复子串问题

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int lengthOfLongestSubstring(string s) {
	unordered_map<char, int> window;
	int left = 0, right = 0;
	int res = 0; //记录结果
	while (right < s.size()) {
		char c = s[right];
		right++;
		//进行窗口内数据更新
		window[c]++;
		//判断左侧窗口是否要收缩
		while (window[c] > 1) {
			char d = s[left];
			left++;
			//进行窗口内数据更新
			window[d]--;
		}
		//在这里更新答案
		res = max(res, right - left);
	}
	return res;
}

# 并查集框架
1.初始化:初始的时候每个结点各自为一个集合,father[i]表示结点 i 的父亲结点,如果 father[i]=i,我们认为这个结点是当前集合根结点。

复制代码
1
2
3
4
5
6
void init() {
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
    }
}

2.查找:查找结点所在集合的根结点，结点 x 的根结点必然也是其父亲结点的根结点。

复制代码
1
2
3
4
5
6
7
int get(int x) {
    if (father[x] == x) { // x 结点就是根结点
        return x; 
    }
    return get(father[x]); // 返回父结点的根结点
}

升级版，顺带优化树结构

复制代码
1
2
3
4
5
6
7
int get(int x) {
    if (father[x] == x) { // x 结点就是根结点
        return x; 
    }
    return father[x] = get(father[x]); // 返回父结点的根结点，并另当前结点父结点直接为根结点
}

3.合并:将两个元素所在的集合合并在一起,通常来说,合并之前先判断两个元素是否属于同一集合。

复制代码
1
2
3
4
5
6
7
8
void merge(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) { // 不在同一个集合
        father[y] = x;
    }
}

带权并查集

所谓带权并查集，是指结点存有权值信息的并查集。并查集以森林的形式存在，而结点的权值，大多是记录该结点与祖先关系的信息。比如权值可以记录该结点到根节点的距离。

例题
在排队过程中，初始时，一人一列。一共有如下两种操作。

  • 合并：令其中的两个队列 A，B 合并，也就是将队列 A 排在队列 B 的后面。
  • 查询：询问某个人在其所在队列中排在第几位。

例题解析
我们不妨设 size[]为集合中的元素个数，dist[]为元素到队首的距离，合并时，dist[A.root]需要加上size[B.root] (每个元素到队首的距离应该是到根路径上所有点的dist[]求和)，size[B.root]需要加上size[A.root] (每个元素所在集合的元素个数只需查询该集合中根的size[x.root])。

1)初始化：

复制代码
1
2
3
4
5
6
void init() {
    for(int i = 1; i <= n; i++)  {
        father[i] = i, dist[i] = 0, size[i] = 1;
    }
}

2)查找：查找元素所在的集合，即根节点:

复制代码
1
2
3
4
5
6
7
8
9
10
int get(int x) {
    if(father[x] == x) {
        return x;        
    }
    int y = father[x];
    father[x] = get(y);
    dist[x] += dist[y];  // x 到根结点的距离等于 x 到之前父亲结点距离加上之前父亲结点到根结点的距离
    return father[x];
}

3)合并
将两个元素所在的集合合并为一个集合。
通常来说，合并之前，应先判断两个元素是否属于同一个集合，这可用上面的“查找”操作实现。

复制代码
1
2
3
4
5
6
7
8
9
10
void merge(int a, int b) {
    a = get(a);
    b = get(b);
    if(a != b) {  // 判断两个元素是否属于同一集合
        father[a] = b;
        dist[a] = size[b];
        size[b] += size[a];
    }
}

最后

以上就是曾经芹菜最近收集整理的关于【算法学习】框架记录动态规划框架回溯算法解题套路BFS广度优先搜索双指针技巧滑动窗口带权并查集的全部内容，更多相关【算法学习】框架记录动态规划框架回溯算法解题套路BFS广度优先搜索双指针技巧滑动窗口带权并查集内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(64)

相关文章

（最长重复子数组）（两个数组）（动态规划）（dp[i][j] =dp[i-1][j-1]）questioncode
（最长重复子数组）（两个数组）（动态规划）（dp[i][j] =dp[i-1][j-1]）questioncode
每日一题：零钱兑换
每日一题：零钱兑换
LeetCode 10 正则表达式匹配 二维dp
LeetCode 10 正则表达式匹配 二维dp
322. Coin Change
322. Coin Change
【算法学习】框架记录动态规划框架回溯算法解题套路BFS广度优先搜索双指针技巧滑动窗口带权并查集
【算法学习】框架记录动态规划框架回溯算法解题套路BFS广度优先搜索双指针技巧滑动窗口带权并查集
【LeetCode刷题笔记-86 322:零钱兑换（动态规划）】
【LeetCode刷题笔记-86 322:零钱兑换（动态规划）】
【LeetCode】322. 零钱兑换 结题报告 (C++)
【LeetCode】322. 零钱兑换 结题报告 (C++)
零钱兑换问题--探索动态规划的基本思想0x01.问题0x02.分析问题0x03.解决办法1--暴力递归0x04.解决办法2--记忆化搜索0x05.解决办法3--动态规划（自下而上）0x06.探索动态规划的基本思想
零钱兑换问题--探索动态规划的基本思想0x01.问题0x02.分析问题0x03.解决办法1--暴力递归0x04.解决办法2--记忆化搜索0x05.解决办法3--动态规划（自下而上）0x06.探索动态规划的基本思想

评论列表共有 0 条评论

立即
投稿
返回
顶部