数据结构第四章-递归
递归函数基础
求子集
#medium
78. 子集 - 力扣（LeetCode）
已知一组数（无重复元素），求这组数字可以组成的所有子集
局部思考：只生成[1],[1,2],[1,2,3]
利用递归
方法1：回溯法
回溯试探法
用递归树来看
暴力破解法的一种
本题的解决方法
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::vector<std::vector<int>> result;//存储最终结果的result
std::vector<int> item;//回溯时候产生各子集的数组
result.push_back(item);//把空集push进result
generate(0,nums,item,result);//计算各个子集
return result;
}
private:
void generate(int i,std::vector<int>&nums,std::vector<int>&item,std::vector<std::vector<int> >&result){
if(i >= nums.size()){//递归结束条件，当i大于nums.size
return ;
}
item.push_back(nums[i]);//当前生成子集加入result
result.push_back(item);
generate(i+1,nums,item,result);//第一次递归
item.pop_back();
generate(i+1,nums,item,result);//回溯的第二次递归
}
};
BTW,由于是引用调用，所以，在pop不仅仅是用于选择该点是否进入item，还保证了回到该层级的时候item能够回复，以这个图为例子，在第三次递归调用之后会经历第四次递归return，然后在回溯后的第五层递归里面把[1,2,3]里面的3pop掉，然后再依次回溯到第三次和第二次，然后再第6次递归的时候把2弹出
方法二：位运算法
解决方法如下
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::vector<std::vector<int> >result;
int all_set = 1<<nums.size();// 把1左移num.size()个单位
//设置全部集合的最大值+1
for(int i =0;i<all_set ;i++){
std::vector<int> item;
for(int j = 0;j<nums.size();j++){
if(i&(1<<j)){//构造数字i代表的集合，各元素存储进item
item.push_back(nums[j]);
}
}
result.push_back(item);
}
return result;
}
};
其中 1<< n 就是$2^n$ 相当于把1右移了n个单位变成 100……0 整数i代表从0到$2^n-1$ 这$2^n$个集合 1<<j 即为构造nums数组的第j个元素 若i&（1<<j)为真则nums[j] 放入数组
如果你没看懂的话，以下是工作示例 : 感谢必应
- 当i=0时，二进制表示为000，所以不会有任何元素被添加到子集中，得到的子集为空集，即`[]`。
- 当i=1时，二进制表示为001，所以只有第0位为1，因此只有`nums[0] = 1`被添加到子集中，得到的子集为`[1]`。
- 当i=2时，二进制表示为010，所以只有第1位为1，因此只有`nums[1] = 2`被添加到子集中，得到的子集为`[2]`。
- 当i=3时，二进制表示为011，所以第0位和第1位都为1，因此`nums[0] = 1`和`nums[1] = 2`都被添加到子集中，得到的子集为`[1, 2]`。
- 当i=4时，二进制表示为100，所以只有第2位为1，因此只有`nums[2] = 3`被添加到子集中，得到的子集为`[3]`。
- 当i=5时，二进制表示为101，所以第0位和第2位都为1，因此`nums[0] = 1`和`nums[2] = 3`都被添加到子集中，得到的子集为`[1, 3]`。
- 当i=6时，二进制表示为110，所以第1位和第2位都为1，因此`nums[1] = 2`和`nums[2] = 3`都被添加到子集中，得到的子集为`[2, 3]`。
- 当i=7时，二进制表示为111，所以第0位、第1位和第2位都为1，因此`nums[0] = 1`、`nums[1] = 2`和`nums[2] = 3`都被添加到子集中，得到的子集为`[1, 2, 3]`。
最终，该方法返回的结果向量为：`[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]`。
求子集 II
#medium 90. 子集 II - 力扣（LeetCode） 已知一组数(其中有重复元素)，求这组数可以组成的所有子集 结果中无重复子集 注：集合没有顺序
排序的目的是为了防止[1,2,2] 和[2,1,2]的情况出现，当使用全部从小到大进行排序之后，所有的结果全部变为相同的子集都会是[1,2,2]
解决方法如下
class Solution{
public:
void generate(int i,std::vector<int>&nums,std::vector<std::vector<int>>&result,std::set<std::vector<int>>&res_set);
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
std::vector<std::vector<int> > result;
std::vector<int> item ;
std::set<std::vector<int>>res_set;//去重用的集合set
std::sort(nums.begin(),nums.end());//对num数组进行排序
result.push_back(item);
generate(0,nums,result,item,res_set);
return result;
}
private:
void generate(int i,std::vector<int>&nums,std::vector<std::vector<int>>&result,std::vector<int>&item,std::set<std::vector<int>>&res_set){
if(i >= nums.size()){
return ;
}
item.push_back(nums[i]);
if(res_set.find(item)==res_set.end()){//如果在集合中没有找到
result.push_back(item);//item 放进result里面
res_set.insert(item);//item放进res_set里面
}
generate(i+1,nums,result,item,res_set);
item.pop_back();
generate(i+1,nums,result,item,res_set);
}
};
组合数之和 II
#medium 40. 组合总和 II - 力扣（LeetCode） 已知一组数（有重复）求这组数的所有子集里面，子集中各个元素和整数位target的子集，结果中无重复的子集
方法1
用[[第四章：递归，回溯和分治#求子集 II|求子集II]]的方法求出全部子集然后再处理就行
非常草率
甚至不需要额外的再写一遍代码，再加一段遍历result，然后判断target并加入新result的代码就行 别说你不会
然而。。。。。
提交之后会有出现Time Limit Exceed
无论是回溯法还是位运算法，整体的时间复杂度位O($2^n$) 所以求出全部子集在一些情况下会爆掉
方法2
在搜索回溯的过程中进行剪枝操作 在DFS的时候还会用上的
解决方法如下
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
std::vector<std::vector<int>>result;
std::vector<int> item;
std::set<std::vector<int>>res_set;
std::sort(candidates.begin(),candidates.end());
generate(0,candidates,result,item,res_set,0,target);
return result;
}
private:
void generate(int i,std::vector<int>&nums,std::vector<vector<int>>&result,std::vector<int>&item,std::set<std::vector<int>>&res_set,int sum,int target){ //sum是当前子集item中的元素和
if(sum>target||i>=nums.size()){//当元素已经选完或者sum超过target,剪枝操作
return;
}
sum = sum+nums[i];
item.push_back(nums[i]);
if(sum == target&&res_set.find(item)==res_set.end()){//当item的元素和即为target且该结果未添加时
result.push_back(item);
res_set.insert(item);
}
generate(i+1,nums,result,item,res_set,sum,target);
sum = sum-nums[i];
item.pop_back();//回溯时候删除nums[i]和sum
generate(i+1,nums,result,item,res_set,sum,target);
}
};
然而
这个代码在leetcode跑仍然会超时，开课的时候有172个样例，现在有176个
byd乐扣往tmd样例里面加了100个1，直接把tmd时间堆爆掉
所以这里采用zen-feistel2js 的思路与方法
我对代码进行了写修改，加了注释改了写法，但思路还是一样的 然而修改之后比他之前速度反而更慢了
class Solution {
public:
vector<vector<int>> result; // 存储最终结果
vector<int> path; // 存储当前路径
void backtracking(vector<int> candidates, int target, int sum, int startindex, int i) {
if (i >= candidates.size()) return; // 如果 i 超出数组范围，则返回
if (candidates[i] + sum > target) return; // 如果当前元素加上当前路径的和超过目标和，则返回
if (i > startindex && candidates[i] == candidates[i - 1]) { // 跳过重复元素,如果这个元素与上一个元素相同，说明这个元素已经处理过了，不需要再额外处理，直接进入下一次递归，且不需要回溯
backtracking(candidates, target, sum, startindex, i + 1);
return;
}
sum += candidates[i]; // 更新 sum 的值
path.push_back(candidates[i]); // 将当前元素添加到路径中
if (sum == target) { // 如果当前路径的和等于目标和
result.push_back(path); // 将当前路径添加到结果集中
}
backtracking(candidates, target, sum, i + 1, i + 1); // 递归搜索剩余元素
sum -= candidates[i]; // 回溯时撤销选择
path.pop_back(); // 回溯时撤销选择
backtracking(candidates, target, sum, startindex, i + 1); // 不选择当前元素，继续搜索
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end()); // 对候选数组进行排序
backtracking(candidates, target, 0, 0, 0); // 开始搜索
return result; // 返回结果
}
};
zen-feistel2js的思路除了基本的对和判断和叶节点判断之外，还删除了重复数据的影响
if (i > startindex && candidates[i] == candidates[i - 1]) { // 跳过重复元素,如果这个元素与上一个元素相同，说明这个元素已经处理过了，不需要再额外处理，直接进入下一次递归，且不需要回溯
backtracking(candidates, target, sum, startindex, i + 1);
return;
}
解决了byd乐扣给你塞100个1的问题
生成括号
#medium
22. 括号生成 - 力扣（LeetCode）
已知n组括号，生成n组括号所有合法的可能性
找出全部可能性的实现
BTW 在C++里面，string是值传递，不需要显式的修改字符，每一次递归都会建立新的item副本
接下来是剪枝
解决方法如下
class Solution {
public:
vector<string> generateParenthesis(int n) {
std::vector<std::string> result;
generate("",n,n,result);
return result;
}
private:
void generate(std::string item,int left,int right,std::vector<std::string>&result){//left和right是分别还剩下几个左右括号
if(left == 0&&right == 0){//如果左右括号全部用完
result.push_back(item);//到递归树的叶节点才开始收入进result
return;
}
if(left>0){//还可以放左括号
generate(item+'(',left-1,right,result);
}
if(left < right){//如果）的剩余数量比（大，说明left先放置了
generate(item+')',left,right-1,result);
}
}
};
N皇后问题
#hard
51. N 皇后 - 力扣（LeetCode）
最早追溯到1848年，马克思 贝瑟尔提出了8皇后问题
此题是该题的升级版
将$N$个皇后摆放在$NN$ 的棋盘中，互相*不可攻击，有多少种摆放方式，每种摆放的具体方式是什么
放置皇后的初步实现
回溯算法，启动！！
解决思路如下
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
std::vector<std::vector<std::string> >result;//存储最终结果的数组
std::vector<std::vector<int> > mark; //标记棋盘是否可以放置皇后的二维数组,皇后的攻击范围
std::vector<std::string>location;//存储某一次的摆放结果，皇后的摆放位置
for(int i = 0;i<n;i++){
mark.push_back(std::vector<int>());//mark每行push进一个空数组
for(int j = 0;j<n; j++){
mark[i].push_back(0);//把mark初始化为全0
}
location.push_back(""); //location全部初始化为.
location[i].append(n,'.');
}
generate(0,n,location,result,mark);
return result;
}
private:
void generate(int k, int n,//k代表完成了几个皇后的放置，正在放置第，看k个皇后
std::vector<std::string>& location,//某次的结果
std::vector<std::vector<std::string>>& result,//最终结果
std::vector<std::vector<int>>&mark){//标记数组
if(k == n){ //当k== n代表完成了皇后的放置
result.push_back(location);
return ;
}
for(int i = 0;i < n;i++){//尝试0到n-1列
if(mark[k][i] == 0){//如果该点为0，可以放置皇后
std::vector<std::vector<int> > temp_mark = mark;//回溯前的mark镜像
location[k][i] = 'Q';//记录当前皇后位置
put_down_the_queen(k,i,mark);//放置皇后
generate(k+1,n,location,result,mark);//递归下一行皇后的位置
mark = temp_mark;//mark回溯回赋值前状态
location[k][i] = '.';//当前皇后的位置重新赋值
}
}
return ;
}
};
put_down_the_queem代码
void put_down_the_queen(int x, int y,std::vector<std::vector<int> > &mark){
static const int dx[] = {-1,1,0,0,-1,-1,1,1};
static const int dy[] = {0,0,-1,1,-1,1,-1,1};//方向数组
mark[x][y] = 1;//放置皇后
for(int i = 1;i<mark.size();i++){
for(int j=0 ;j<8;j++){//八个方向
int new_x = x+i*dx[j];//x和y的新位置
int new_y = y+i*dy[j];//组成新点
if(new_x >= 0 &&new_x< mark.size() && new_y>=0 && new_y<mark.size()){//检查新位置在不在循环内
mark[new_x][new_y] = 1; //将该点设置为1
}
}
}
}
关于递归的具体思路
在递归过程中，函数到正常递归，直到找到某一结果（返回结果）或这某一行全都是1，无法插入皇后，在无法插入皇后的时候，函数在这一层递归里面不进入if，自动到最后return回上一层递归，执行generate之后的代码，比如本层递归是1111，上一层递归是1Q10(此时i= 1)，他会回到上一层递归，从i = 1的循环里的generate函数的下一行开始执行，直到循环到i=3 进行下一层递归，完成回溯
这算是递归基础知识把
分治法与归并排序
普通归并排序
代码如下
void merge_sort_two_vec(std::vector<int>&sub_vec1,std::vector<int>&sub_vec2,std::vector<int>&vec){
int i = 0;
int j = 0;
while(i<sub_vec1.size()&&j<sub_vec2.size()){
if(sub_vec1[i]<=sub_vec2[j]){
vec.push_back(sub_vec1[i]);
i++;
}
else{
vec.push_back(sub_vec2[j]);
j++;
}
}
for(;i<sub_vec1.size();i++){ //push进剩余元素
vec.push_back(sub_vec1[i]);
}
for(;j<sub_vec2.size();j++){
vec.push_back(sub_vec2[j]);
}
}
分治算法的归并排序
在[[第一章：链表#排序链表的合并（下）#方法3——分治后相连 分治思想|链表分治归并]]出现过
归并排序实现
void merge_sort(std::vector<int>&vec){
if(vec.size()<=2 ){
return ;//当子问题最够小直接求解
}
int mid = vec.size()/2;
std::vector<int>sub_vec1;
std::vector<int>sub_vec2;
for(int i = 0 ;i<mid;i++){
sub_vec1.push_back(vec[i]);
}
for(int i = mid;i<vec.size();i++ ){
sub_vec2.push_back(vec[i]);
}
merge_sort(sub_vec1);
merge_sort(sub_vec2);
vec.clear();
merge_sort_two_vec(sub_vec1,sub_vec2,vec);
}
很容易理解吧：）接下来给你整个大的
逆序数
#hard 315. 计算右侧小于当前元素的个数 - 力扣（LeetCode） 本题还可以用[[第六章：二分查找与二叉排序树#逆序数|二叉排序树]]来写 已知数组nums，求新数组count，count[i] 代表nums[i]右侧且比nums[i]小的数字 示例
nums = [5,2,6,1],counts = [2,1,1,0]
nums = [6,6,6,1,1,1] counts = [3,3,3,0,0,0]
复杂度O($N^2$) N的规模是 1< N< $10^{5}$ 必然超时
利用归并排序
解决思路如下
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
std::vector<std::pair<int,int> > vec;
std::vector<int> count ;
for(int i =0;i<nums.size();i++){
vec.push_back(std::make_pair(nums[i],i));//绑定nums和i，来记忆数组一开始的位置
count.push_back(0);
}
merge_sort(vec,count);
return count;
}
private:
void merge_sort_two_vec(std::vector<std::pair<int,int> > &sub_vec1,
std::vector<std::pair<int,int> >&sub_vec2,
std::vector<std::pair<int,int> > &vec,
std:: vector<int>&count){
int i =0;
int j = 0;
while(i<sub_vec1.size()&&j<sub_vec2.size()){
if(sub_vec1[i].first <= sub_vec2[j].first){
count[sub_vec1[i].second] += j;
vec.push_back(sub_vec1[i]);
i++;
}
else{
vec.push_back(sub_vec2[j]);
j++;
}
}
for(;i<sub_vec1.size();i++){
count[sub_vec1[i].second] += j;
vec.push_back(sub_vec1[i]);
}
for(;j<sub_vec2.size();j++){
vec.push_back(sub_vec2[j]);
}
}
void merge_sort(std::vector<std::pair<int,int> > &vec,std::vector<int>&count){
if(vec.size() <2){
return ; //子问题足够小直接求解
}
int mid = vec.size()/2;
std::vector<std::pair<int,int> >sub_vec1;
std::vector<std::pair<int,int> >sub_vec2;
for(int i=0;i<mid;i++){ //分解并排序，与上一题一样
sub_vec1.push_back(vec[i]);
}
for(int i = mid;i<vec.size();i++){
sub_vec2.push_back(vec[i]);
}
merge_sort(sub_vec1,count);
merge_sort(sub_vec2,count);
vec.clear();
merge_sort_two_vec(sub_vec1,sub_vec2,vec,count);
}
};
后半部分由于是升序所以他的count一直为0，这也是可以利用j来处理count的原因
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 name1110
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果