《面试算法 LeetCode 刷题班》——4. 递归，回溯，分治

本文主要是介绍《面试算法 LeetCode 刷题班》——4. 递归，回溯，分治，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本文内容是基于小象学院——林沐 《面试算法 LeetCode 刷题班》，后期仍将对相关内容进行不定期更新！

4. 递归，回溯，分治

文章目录

• • • 4. 递归，回溯，分治
    • • LeetCode 78 求子级（M）
      • LeetCode 90 求子集2（M）
      • LeetCode 40 组合数之和2（M）
      • LeetCode 22 生成括号（M）
      • LeetCode 51 N 皇后（H）
      • LeetCode 315 逆序数（H）

LeetCode 78 求子级（M）

给定一个不含重复数的集合，求所有不重复的子集

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    	vector<int> item;
    result.push_back(item);
    generate(0,nums,item,result);
    return result;
       
    }

    void generate(int i, vector<int> & nums, vector<int> &item, vector<vector<int>> &result) {
    	if (nums.size()==i)
    	{
    		return;
    	}
    	item.push_back(nums[i]);
    	result.push_back(item);
    	generate(i + 1, nums, item, result);
    	item.pop_back();
    	generate(i + 1, nums, item, result);
    }
};

LeetCode 90 求子集2（M）

给定一个含重复数的集合，求所有不重复的子集
set（<set>） 和 sort（<algorithm>）

class Solution {
public:
	vector<vector<int>> subsetsWithDup(vector<int>& nums) {
		vector<vector<int>> result;
		vector<int> item;
result.push_back(item);
		set<vector<int>> res_set;
		sort(nums.begin(), nums.end());
generate(0, nums, item, result,res_set);
return result;

	}

void generate(int i, vector<int> & nums, vector<int> &item, vector<vector<int>> &result, set<vector<int>> &res_set) {
	if (nums.size() == i)
	{
		return;
	}
	item.push_back(nums[i]);
	if (res_set.find(item) == res_set.end())
	{		result.push_back(item);
			res_set.insert(item);
	}
	generate(i + 1, nums, item, result,res_set);
	item.pop_back();
	generate(i + 1, nums, item, result,res_set);
}
};

LeetCode 40 组合数之和2（M）

class Solution {
public:
	vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
		vector<vector<int>> result;
		vector<int> item;
		set<vector<int>> res_set;
		sort(nums.begin(), nums.end());
		generate(0, nums, item, 0,target,result, res_set);
		return result;

	}

	void generate(int i, vector<int> & nums, vector<int> &item,int sum, int target,vector<vector<int>> &result, set<vector<int>> &res_set) {
		if (nums.size() == i || sum>target)
		{
			return;
		}
		sum += nums[i];
		item.push_back(nums[i]);
		if ( sum == target && res_set.find(item) == res_set.end())
		{
			result.push_back(item);
			res_set.insert(item);
		}
		generate(i + 1, nums, item, sum,target,result, res_set);
		item.pop_back();
		sum -= nums[i];
		generate(i + 1, nums, item, sum,target,result, res_set);
	}
};

LeetCode 22 生成括号（M）

给定n对括号，首先递归生成所有可能的合法的括号组合。代码如下：

class Solution {
public:
	vector<string> generateParenthesis(int n) {
		vector<string> result;
		string item="";
		generate(item, n, n,result);
		return result;

	}

	void generate(string item, int left,int right, vector<string> &result)
	{
		if (left==0 && right ==0)
		{
			result.push_back(item);
			return;
		}
		if (left>0)
		{
			generate(item + "(", left-1, right, result);
		}
		if (right>left)
		{
			generate(item + ")", left, right-1, result);
		}
	}
};

在这个的基础上进行规律筛选。

LeetCode 51 N 皇后（H）

class Solution {
public:
	vector<vector<string>> solveNQueens(int n) {
		vector<vector<string>> result;
		vector<vector<int>> mark;
		vector<string> location;
		for (int i = 0; i < n; i++)  // 创建nxn的矩阵，n列
		{
			mark.push_back(vector<int>()); // 先压入一个空vector，相当于行，然后在其基础上添加内容 
			for (int j = 0; j < n; j++) { // 每一行有n个元素
				mark[i].push_back(0); // 均初始化为 0 
			}
			location.push_back(""); // 先压入一个空字符串，然后在其基础上添加内容 
			location[i].append(n, '.'); // 初始化 location 为 "...." x 4
		}  // 初始化完毕
		generate(0, n, location, result, mark); // 进入递归
		return result; 
	}

	void put_down_the_queen(int x, int y, vector<vector<int>> &mark) {
		static const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};  // 方向数组，x部分
		static const int dy[] = {0,0,-1,1,-1,1,-1,1}; // 方向数组，y部分
		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];
				int new_y = y + i*dy[j];
				if (new_x<mark.size() && new_x>=0 && new_y>=0 && new_y<mark.size())
				{
					mark[new_x][new_y] = 1;
				}
			}
		}
	}

	void generate(int k, int n, vector<string> &location,vector<vector<string>> &result, vector<vector<int>> &mark) {
		if (k==n)
		{
			result.push_back(location);
			return;
		}

		for (int i = 0; i < n; i++) { 
			if (mark[k][i] == 0) // 只找每一行为0的位置
			{
				vector<vector<int>> tmp_mark = mark; // 保留放置此皇后时的状态，留作回溯用
				location[k][i] = 'Q'; // 将是0的位置放入皇后'Q'
				put_down_the_queen(k, i, mark);  // 依次向外延伸，将满足条件的皇后延长线的数字都变为1
				generate(k + 1, n, location, result, mark); // 然后递归进入下一行，进行皇后放置和修改整个数组状态，如果找不到直接返回到上一个状态，继续运行下面的语句
				mark = tmp_mark; // 返回上一个状态
				location[k][i] = '.';  //位置也返回上一个状态
			}
		}
	}
};

LeetCode 315 逆序数（H）

预备知识，两个数组的归并排序：

class Solution {
public:
	void merge_sort_two_vec(vector<int> &sub_vec1, vector<int> &sub_vec2, 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++)
			vec.push_back(sub_vec1[i]);
		for(;j<sub_vec2.size();j++)
			vec.push_back(sub_vec2[j]);
	}
};

预备知识，一个数组的归并排序（nlogn）：

分治，将一个规模为N的问题，分解为K个规模较小的子问题，这些问题相互独立与原问题性质相同。求出后再进行合并。

class Solution {
public:
	void merge_sort_two_vec(vector<int> &sub_vec1, vector<int> &sub_vec2, 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++)
			vec.push_back(sub_vec1[i]);
		for(;j<sub_vec2.size();j++)
			vec.push_back(sub_vec2[j]);
	}

	void merge_sort(vector<int> &vec) { // 分治函数
		if (vec.size()<2)
		{
			return;
		}
		int mid = vec.size() / 2;
		vector<int> sub_vec1;
		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);
	}
};

问题：

class Solution {
public:
	vector<int> countSmaller(vector<int> &nums)
	{
		vector<pair<int, int>> vec;
		vector<int> count;
		for (int i = 0; i < nums.size(); i++)
		{
			vec.push_back(make_pair(nums[i], i));
			count.push_back(0);
		}
		merge_sort(vec, count);
		return count;
	}

	void merge_sort_two_vec(vector<pair<int,int>> &sub_vec1, vector<pair<int,int>> &sub_vec2, vector<pair<int,int>> &vec,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(vector<pair<int,int>> &vec, vector<int> & count) {
		if (vec.size()<2)
		{
			return;
		}
		int mid = vec.size() / 2;
		vector<pair<int,int>> sub_vec1;
		vector<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);
	}
};

这篇关于《面试算法 LeetCode 刷题班》——4. 递归，回溯，分治的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！