递归，回溯，分治（C++刷题笔记）

递归，回溯，分治（C++刷题笔记）

78. 子集

力扣

预备知识

nums[]=[1,2,3],先将子集[1],[1,2],[1,2,3]打印

#include <bits/stdc++.h>using namespace std;int main() {vector<int>nums;for (int i=1;i<=3;i++){nums.push_back(i);}vector<int>item;//生成各个子集vector< vector<int> >res;//结果数组for (int i = 0; i < nums.size(); ++i){item.push_back(nums[i]);res.push_back(item);}for (int i = 0; i < res.size(); ++i){for (int j = 0; j < res[i].size(); ++j){printf("[%d]",res[i][j]);}printf("\n");}return 0;}

[1]      
[1][2]   
[1][2][3]

递归写法

#include <bits/stdc++.h>using namespace std;void recur(int i, vector<int> &nums, vector<int> &item, vector<vector<int> > &res) {if (i >= nums.size()) {return;}item.push_back(nums[i]);res.push_back(item);recur(i + 1, nums, item, res);}int main() {vector<int> nums;for (int i = 1; i <= 3; i++) {nums.push_back(i);}vector<int> item;//生成各个子集vector<vector<int> > res;//结果数组recur(0, nums, item, res);for (int i = 0; i < res.size(); ++i) {for (int j = 0; j < res[i].size(); ++j) {printf("[%d]", res[i][j]);}printf("\n");}return 0;}

题目代码

子集问题，变量数组，每次有两种选择，选或者不选，逐层递归

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<int>item;vector<vector<int> >res;res.push_back(item);recur(0,nums,item,res);return res;}void recur(int i,vector<int>&nums,vector<int>&item,vector<vector<int> >&res){if(i>=nums.size()){return;}item.push_back(nums[i]);//选择nums[i]res.push_back(item);recur(i+1,nums,item,res);item.pop_back();//不选择nums[i]recur(i+1,nums,item,res);}
};

90. 子集 II

力扣

题目代码

//使用set去重 最后几个样例过不去
class Solution {
public:vector<vector<int>> subsetsWithDup(vector<int> &nums) {vector<vector<int> > res;vector<int> item;set<vector<int> > res_set;sort(nums.begin(), nums.end());res.push_back(item);//首先把空集放进去recur(0, nums, item, res, res_set);return res;}//函数参数注意引用 尤其是set 否则无法完成去重void recur(int i, vector<int> &nums, vector<int> &item, vector<vector<int> > &res, set<vector<int> > &res_set) {if (i >= nums.size())return;item.push_back(nums[i]);if (res_set.find(item) == res_set.end()) { //如果不在集合里可以放入res.push_back(item);res_set.insert(item);}recur(i + 1, nums, item, res, res_set);item.pop_back();recur(i + 1, nums, item, res, res_set);}
};

40. 组合总和 II

力扣

题目代码

class Solution {
public:vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {vector<vector<int> > res;vector<int> item;set<vector<int> > res_set;sort(candidates.begin(), candidates.end());recur(0, candidates, res, item, res_set, 0, target);return res;}void recur(int i, vector<int> &nums, vector<vector<int> > &res,vector<int> &item, set<vector<int> >&res_set, int sum,int target) {if (i >= nums.size() || sum > target) {return;}sum += nums[i];item.push_back(nums[i]);if (target == sum && res_set.find(item) == res_set.end()) {res.push_back(item);res_set.insert(item);}recur(i + 1, nums, res, item, res_set, sum, target);sum -= nums[i];item.pop_back();recur(i + 1, nums, res, item, res_set, sum, target);}
};

22. 括号生成

力扣

预备知识

首先递归生成所有可能

#include <bits/stdc++.h>using namespace std;
void dfs(string item,int n,vector<string>&res){if(item.size()==2*n){res.push_back(item);return;}dfs(item+'(',n,res);dfs(item+')',n,res);}int main() {vector<string >res;dfs("",2,res);for (int i = 0; i < res.size(); ++i){cout<<res[i]<<endl;}return 0;}

((((
((()
(()(
(())
()((
()()
())(
()))
)(((
)(()
)()(
)())
))((
))()
)))(
))))

然后判断合法括号组合

左括号右括号数量不超过n

先有左括号才能放右括号

题目代码

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string>res;dfs("",n,n,res);return res;}void dfs(string item,int left,int right,vector<string>&res){if(left==0&&right==0){res.push_back(item);return;}if(left>0){dfs(item+'(',left-1,right,res);}if(left<right){dfs(item+')',left,right-1,res);}}
};

315. 计算右侧小于当前元素的个数

力扣

预备知识

已知两个有序数组，归并这两个数组

#include <bits/stdc++.h>using namespace std;void merge_sort(vector<int> &a1, vector<int> &a2, vector<int> &merge_a) {int i = 0;int j = 0;while (i < a1.size() && j < a2.size()) {if (a1[i] <= a2[j]) {merge_a.push_back(a1[i]);i++;} else {merge_a.push_back(a2[j]);j++;}}for (; i < a1.size(); i++) {merge_a.push_back(a1[i]);}for (; j < a2.size(); j++) {merge_a.push_back(a2[i]);}}int main() {vector<int> res;vector<int>a1;vector<int>a2;int t1[]={2,5,8,20};int t2[]={1,3,5,7,30,50};for (int i = 0; i <4 ; ++i) {a1.push_back(t1[i]);}for (int i = 0; i <6 ; ++i) {a2.push_back(t2[i]);}merge_sort(a1,a2,res);for (int i = 0; i < res.size(); ++i) {printf("%d ",res[i]);}return 0;}

1 2 3 5 5 7 8 20 30 30 

题目代码

暴力方法，对于每个元素，从左向右遍历，扫描右侧比它小的个数，累加求和

考虑归并两个有序数组，i，j为两个数组的指针，需要将指针i指向的元素插入时，对应的count[i]就是j的值，count[i]为右侧比它小的数

排序后，使用pair绑定<num[i],index>排序后它们的右侧比它本身小的个数就得到了

class Solution {public:vector<int> countSmaller(vector<int> &nums) {vector<pair<int,int> > vec;vector<int> cnt;//这里注意下是nums的大小 不是vec的大小 vec初始为0一开始没注意始终没有输出for (int i = 0; i < nums.size(); ++i) {vec.push_back(make_pair(nums[i], i));cnt.push_back(0);}merge_sort(vec, cnt);return cnt;}void merge_sort_cnt(vector<pair<int,int>  > &vec1, vector<pair<int,int> > &vec2, vector<pair<int,int> > &vec,vector<int> &cnt) {int i = 0;int j = 0;while (i < vec1.size() && j < vec2.size()) {if (vec1[i].first <= vec2[j].first) {cnt[vec1[i].second] += j;vec.push_back(vec1[i]);i++;} else {vec.push_back(vec2[j]);j++;}}for (; i < vec1.size(); i++) {cnt[vec1[i].second] += j;vec.push_back(vec1[i]);}for (; j < vec2.size(); j++) {vec.push_back(vec2[j]);}}//归并排序void merge_sort(vector<pair<int,int> > &vec, vector<int> &cnt) {if (vec.size() < 2) {return;}int mid = vec.size() / 2;vector<pair<int,int> > vec1;vector<pair<int,int> > vec2;for (int i = 0; i < mid; ++i) {vec1.push_back(vec[i]);}for (int i = mid; i < vec.size(); ++i) {vec2.push_back(vec[i]);}merge_sort(vec1, cnt);merge_sort(vec2, cnt);vec.clear();merge_sort_cnt(vec1, vec2, vec, cnt);}};

51. N 皇后

力扣

void put_down_the_queen(int x, int y, vector<vector<int> > &mark) {//8个方向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 = 0; i < mark.size(); ++i) {for (int j = 0; j < 8; ++j) {int newx = x + i*dx[j];//向8个方向延长int newy = y + i*dy[j];if (newx >= 0 && newx < mark.size() && newy >= 0 && newy < mark.size()) {mark[newx][newy] = 1;}}}}

对于n*n棋盘，每行都有且只能放一个皇后，对每行放置，放置按照列顺序放置，更新mark数组，递归进行下一行皇后放置。

题目代码

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string> > res;//存储最终结果vector<vector<int> > mark;//标记期盼是否可以放置皇后二维数组vector<string> location;//记录结果for (int i = 0; i < n; ++i) {mark.push_back(vector<int>());for (int j = 0; j < n; ++j) {mark[i].push_back(0);}location.push_back("");location[i].append(n, '.');}solve(0,n,location,res,mark);return res;}void solve(int k, int n, vector<string> &location, vector<vector<string> > &res, vector<vector<int> > &mark) {//如果放置完n个皇后if (k == n) {res.push_back(location);return;}for (int i = 0; i < n; ++i) {if (mark[k][i] == 0) {vector<vector<int> > tmp = mark;location[k][i] = 'Q';put_down_the_queen(k, i, mark);solve(k + 1, n, location, res, mark);mark = tmp;//回溯location[k][i] = '.';}}}
//放皇后 放皇后的时候顺便把它8个方向给标记一下void put_down_the_queen(int x, int y, vector<vector<int> > &mark) {//8个方向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 = 0; i < mark.size(); ++i) {for (int j = 0; j < 8; ++j) {int newx = x + i*dx[j];int newy = y + i*dy[j];if (newx >= 0 && newx < mark.size() && newy >= 0 && newy < mark.size()) {mark[newx][newy] = 1;}}}}
};