算法笔记

标签：std current 笔记问题算法 vector result 回溯

1.回溯法 (Backtracking)

应用：组合、排列、子集等组合型问题，0/1背包问题、图的着色问题等。

时空复杂度：时空复杂度较高，指数级别。时间复杂度：O(2^n) 或更高，其中 n 是问题规模。空间复杂度：O(n) 或更高，取决于递归深度。

特性：

通过深度优先搜索遍历解空间。
需要撤销选择，回溯到上一步，尝试其他选择。
通常用于解决组合型问题。

1.1 总述

回溯是一种经典的搜索算法，通常用于解决组合、排列、子集等问题。

回溯法既不属于动态规划也不属于贪心算法。回溯法是一种搜索算法，它通过不断尝试各种可能的选择，然后回溯（撤销选择）来找到问题的解。回溯算法通常用于求解组合、排列、子集等问题。回溯法是一种通用的搜索算法，适用于一些组合、排列、子集等问题，而不限于最优化问题。

虽然回溯法与动态规划和贪心算法都属于求解最优化问题的算法范畴，但它们有很大的区别：

动态规划：动态规划通常通过保存子问题的解来避免重复计算，具有最优子结构。典型的动态规划问题有斐波那契数列、背包问题等。

贪心算法：贪心算法则通过每一步的局部最优选择来期望达到全局最优解，不进行回溯。典型的贪心算法问题有霍夫曼编码、最小生成树算法等。

回溯法更注重搜索整个解空间，通过深度优先搜索的方式，逐步尝试各种选择，遇到无效选择时回溯撤销选择，直到找到问题的解或遍历完整个解空间。

回溯算法基本思想：

递归：使用递归实现对解空间的深度优先搜索。
选择：在每一步根据问题的要求做出选择，尝试不同的可能性。
撤销选择：在递归完成后，撤销当前选择，进行回溯，继续尝试其他可能性。

关键点和优化：

剪枝：在递归的过程中，通过一些条件判断提前终止不符合条件的搜索路径，减少搜索空间，提高效率。
状态重置：在递归完成后，需要将当前选择撤销，进行回溯，保持状态的一致性。
选择列表：在每一步的递归中，需要考虑当前可以做的选择，通常使用循环遍历选择列表。
记录路径：如果需要记录路径或结果，需要使用合适的数据结构进行记录。

典型问题类型：

组合问题：如组合总和、子集、电话号码的字母组合等。
排列问题：如全排列、字符串的全排列等。
N 皇后问题：在 n×n 棋盘上放置 n 个皇后，使其不能相互攻击。

总体思路：

确定问题的解空间和选择列表。
编写回溯函数，实现对解空间的深度优先搜索。
在递归中做出选择、递归到下一层、撤销选择，实现回溯。

1.2 LeetCode实战

全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

#include <vector>
class Solution {
public:
	std::vector<std::vector<int>> permute(std::vector<int>& nums) {
		std::vector<std::vector<int>> result;
		if (nums.empty()) {
			return result;
		}

		std::vector<int> current;  // 用于存储当前排列
		std::vector<bool> used(nums.size(), false);  // 记录数字是否被使用过
		backtrack(nums, current, used, result);

		return result;
	}

private:
	void backtrack(const std::vector<int>& nums, std::vector<int>& current,
					std::vector<bool>& used, std::vector<std::vector<int>>& result) {
		// 终止条件：当前排列长度达到数组长度
		if (current.size() == nums.size()) {
			result.push_back(current);  // 将当前排列加入结果集
			return;
		}

		for (int i = 0; i < nums.size(); ++i) {
			if (!used[i]) {
				// 选择当前数字，递归到下一层
				current.push_back(nums[i]);
				used[i] = true;
				backtrack(nums, current, used, result);
				// 撤销选择，进行回溯
				current.pop_back();
				used[i] = false;
			}
		}
	}
};

在这个实现中，used 数组用于记录数字是否被使用过，防止重复选择。回溯函数 backtrack 中，在每一层递归中选择当前数字，递归到下一层，然后撤销选择进行回溯。

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

#include <vector>
#include <string>

class Solution {
public:
	std::vector<std::string> letterCombinations(std::string digits) {
		std::vector<std::string> result;
		if (digits.empty()) {
			return result;
		}

		std::vector<std::string> mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
		std::string current;
		backtrack(digits, 0, current, mapping, result);

		return result;
	}

private:
	void backtrack(const std::string& digits, int index, std::string& current,
					const std::vector<std::string>& mapping, std::vector<std::string>& result) {
		if (index == digits.size()) {
			// 当递归到字符串末尾时，将当前组合加入结果集
			result.push_back(current);
			return;
		}

		int digit = digits[index] - '0';
		const std::string& letters = mapping[digit];

		for (char letter : letters) {
			// 选择当前字母，递归到下一层
			current.push_back(letter);
			backtrack(digits, index + 1, current, mapping, result);
			// 撤销选择，进行回溯
			current.pop_back();
		}
	}
};

实现中，mapping 数组存储了数字和字母的映射关系。回溯函数 backtrack 通过递归地选择当前字母，构建可能的组合，并在递归完成后撤销选择进行回溯。

组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution {
public:
	std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
		std::vector<std::vector<int>> result;
		std::vector<int> current;
		backtrack(candidates, target, 0, current, result);
		return result;
	}

private:
	void backtrack(const std::vector<int>& candidates, int target, int start,
					std::vector<int>& current, std::vector<std::vector<int>>& result) {
		if (target == 0) {
			// 当目标值为0时，将当前组合加入结果集
			result.push_back(current);
			return;
		}

		for (int i = start; i < candidates.size(); ++i) {
			if (target - candidates[i] >= 0) {
				// 选择当前数字，并递归下一层
				current.push_back(candidates[i]);
				backtrack(candidates, target - candidates[i], i, current, result);
				// 撤销选择，进行回溯
				current.pop_back();
			}
		}
	}
};

N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

#include <vector>
#include <string>

class Solution {
public:
	std::vector<std::vector<std::string>> solveNQueens(int n) {
		std::vector<std::vector<std::string>> result;
		if (n <= 0) {
			return result;
		}

		std::vector<std::string> board(n, std::string(n, '.'));  // 初始化棋盘
		backtrack(n, 0, board, result);

		return result;
	}

private:
	void backtrack(int n, int row, std::vector<std::string>& board,
					std::vector<std::vector<std::string>>& result) {
		// 终止条件：已经放置完所有皇后
		if (row == n) {
			result.push_back(board);  // 将当前棋盘加入结果集
			return;
		}

		for (int col = 0; col < n; ++col) {
			if (isValid(board, row, col, n)) {
				// 在当前位置放置皇后，递归到下一层
				board[row][col] = 'Q';
				backtrack(n, row + 1, board, result);
				// 撤销选择，进行回溯
				board[row][col] = '.';
			}
		}
	}

	bool isValid(const std::vector<std::string>& board, int row, int col, int n) {
		// 检查同一列是否有皇后
		for (int i = 0; i < row; ++i) {
			if (board[i][col] == 'Q') {
				return false;
			}
		}

		// 检查左上到右下斜线是否有皇后
		for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
			if (board[i][j] == 'Q') {
				return false;
			}
		}

		// 检查左下到右上斜线是否有皇后
		for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
			if (board[i][j] == 'Q') {
				return false;
			}
		}

		return true;
	}
};

实现中，使用回溯算法递归地尝试在每一行放置皇后，检查是否满足国际象棋的规则。通过不断递归和回溯，生成所有不同的 N 皇后问题的解决方案。

1.3 模板

基本模板：

class Solution {
public:
	// 主函数，入口点
	void solve(/*其他参数*/) {
		// 初始化结果集等必要的数据结构
		// ...

		// 调用回溯函数
		backtrack(/*参数列表*/);

		// 打印结果或其他操作
		printResult();
	}

private:
	// 回溯函数
	void backtrack(/*参数列表*/) {
		// 终止条件
		if (/*满足条件*/) {
			// 处理当前解
			processSolution();
			return;
		}

		// 递归处理每一步的选择
		for (/*每个选择*/) {
			// 做出选择
			makeChoice();

			// 递归到下一层
			backtrack(/*参数列表*/);

			// 撤销选择，进行回溯
			undoChoice();
		}
	}
}

2.动态规划 (Dynamic Programming)

应用：最优子结构性质的问题，问题可以被分解为重叠的子问题，具有递归关系，子问题的解可以被重复利用，例如最长公共子序列、背包问题等。

时空复杂度：时空复杂度较低，多项式级别。时间复杂度：O(n^2) 或更低，其中 n 是问题规模。空间复杂度：O(n) 或更低，取决于状态表格的大小。

特性：

自底向上或自顶向下的求解过程。
使用状态表格保存子问题的解，避免重复计算。
通常用于求解最优化问题。

3.贪心算法 (Greedy Algorithm)

应用：每一步的选择不会影响后续步骤，局部最优选择期望导致全局最优解，问题具有贪心选择性质，不需要回溯。

时空复杂度：时空复杂度较低，线性或对数级别。时间复杂度：O(n log n) 或更低，其中 n 是问题规模。空间复杂度：O(1) 或常数级别。

特性：

每一步都做出局部最优选择。
不进行回溯，通常无需保存状态。

4.分治法 (Divide and Conquer)

应用：问题可以分解为互不相交的子问题，具有递归结构，子问题独立求解，子问题的解合并得到原问题的解。

时空复杂度：时空复杂度较低，多项式级别。时间复杂度：O(n log n) 或更低，其中 n 是问题规模。空间复杂度：O(log n) 或更低，取决于递归深度。

特性：

通过递归地将问题分解为子问题。
子问题独立求解，不涉及状态的回溯。
典型的应用如归并排序、快速排序等。

异同点总结：

回溯法：主要用于解决组合、排列、子集等组合型问题，时空复杂度高，需要回溯选择。
动态规划：用于求解最优子结构性质的问题，通过保存子问题的解避免重复计算，时空复杂度较低。
贪心算法：适用于每一步的选择不会影响后续步骤、且期望通过局部最优选择得到全局最优解的问题。
分治法：将问题分解为互不相交的子问题，子问题独立求解，通过合并子问题的解得到原问题的解。适用于具有递归结构的问题。

5 算法思想的使用及举例

是否具有最优子结构性质？

如果问题可以被分解为子问题，且子问题的最优解可以组合成原问题的最优解，可能适合使用动态规划。

是否可以通过贪心选择策略得到全局最优解？

如果每一步的选择都是局部最优的，并且这些选择期望能够得到全局最优解，可能适合使用贪心算法。

是否可以通过深度优先搜索来穷尽所有可能的解空间？

如果问题的解空间是一个树状结构，可以通过深度优先搜索来穷尽所有可能的解空间，可能适合使用回溯法。

是否可以通过分治法将问题分解为互不相交的子问题？

如果问题可以被分解为互不相交的子问题，且通过合并子问题的解得到原问题的解，可能适合使用分治法。

是否需要遍历图的结构？

如果问题可以被建模成图的结构，可能需要使用图论算法，例如深度优先搜索、广度优先搜索等。

是否可以通过状态压缩来优化解空间搜索？

如果问题的状态空间非常大，可以考虑使用位运算等方法进行状态压缩，例如在动态规划或搜索问题中。

举例

组合、排列、子集问题通常涉及在给定集合中选择若干元素，满足某些条件。回溯法通过深度优先搜索的方式遍历解空间，逐步选择元素，撤销选择，寻找问题的解。
最短路径问题通常涉及在图中找到从一个节点到另一个节点的最短路径。图论算法如Dijkstra、Bellman-Ford等天然适用于解决这类问题。
背包问题涉及在给定容量的背包中选择一些物品，使得价值最大或者总重量最小。动态规划适合解决这类问题，因为它可以通过保存子问题的解来避免重复计算。
排序问题通常涉及将一组元素按照一定的规则进行排序。贪心算法适合解决这类问题，因为每一步都可以通过选择当前最优的元素来期望得到全局最优解。
分治法适合解决问题可以分解为互不相交的子问题，子问题独立求解，最后合并得到原问题解的情况。归并排序和快速排序是分治法的经典应用。
动态规划适合解决具有最优子结构性质的问题，其中问题的最优解可以由其子问题的最优解推导得到。例如，最长公共子序列问题。
图的遍历问题，如寻找连通分量、拓扑排序等，通常可以通过深度优先搜索和广度优先搜索解决。

标签：std,current,笔记,问题,算法,vector,result,回溯
From： https://www.cnblogs.com/stuBoo/p/17971330