LeetCode 47 Permutations II
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.Example 1:
Input: nums = [1,1,2]Output:[[1,1,2], [1,2,1], [2,1,1]]Example 2:
Input: nums = [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8-10 <= nums[i] <= 10
题目链接
这道题在全排列1上添加了重复的元素,所以剪枝的情况要多考虑一种。比如1,2,2’2,2’与2’,2其实是一种情况,所以要舍去。而对于重复的元素,一开始先排序是一个不错的选择。再排序完之后,如果当前元素和上一个元素相等并且上一个元素还没有被用过(但是后面一定会被用到造成重复),这样的时候就要考虑剪枝
i ...
LeetCode 46. Permutations
Given a collection of distinct integers, return all possible permutations.Example:
Input: [1,2,3]Output:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
题目链接
看了看大佬们的讲解,终于自己做出来一道回溯的题。回溯大致分为三步:
终止条件:回溯到什么情况就可以加入答案列表
剪枝条件:什么情况下就可以停止回溯直接continue
回溯范围:如何将当前层和下一层联系起来继续递归下去
对于这道全排列的题,我们需要一个res保存答案,一个temp参与回溯,当达到终于条件也就是temp的大小与nums的相等时便把temp加入res中;然后需要一个check数组来标记使用过的元素,当一个数已经被使用过便把对应的位置的值设为1,这样避免了一个数重复使用多次。由于这道题是要列出所有的排列结果,所以需要全部遍历
代码如下:
class Solution {public: vector<vector&l ...
2021版王道数据结构课后代码题全部实现
历时2个多月,把21版王道数据结构的课后代码题全部实现了一遍,一共96道题
文件目录结构:
编程环境:Visual Studio 2019
编程语言:C/C++
其中,每道题都是一个独立的cpp文件,可以独立运行。在树和图的章节,会有输入样例和对应的示例图。
cpp文件结构
建立要求的数据结构
题目说明
题目要求的代码
运行示例
以树章节的题目示例:
#include <iostream>#include <stack>#include <queue>using namespace std;#pragma region 构造链式存储的表达式二叉树#define MaxSize 100#define ElemType char#define _for(i,a,b) for(int i=(a);i<(b);i++)typedef struct node { //树的结点 ElemType data[10]; node* left; node* right;}Node, * BiTree;void ...
