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

2021/7/17 22:35:47

本文主要是介绍《面试算法 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&lt;vector&lt;int&gt;&gt; subsetsWithDup(vector&lt;int&gt;&amp; nums) {
		vector&lt;vector&lt;int&gt;&gt; result;
		vector&lt;int&gt; item;
result.push_back(item);
		set&lt;vector&lt;int&gt;&gt; res_set;
		sort(nums.begin(), nums.end());
generate(0, nums, item, result,res_set);
return result;

	}

void generate(int i, vector&lt;int&gt; &amp; nums, vector&lt;int&gt; &amp;item, vector&lt;vector&lt;int&gt;&gt; &amp;result, set&lt;vector&lt;int&gt;&gt; &amp;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&lt;vector&lt;int&gt;&gt; combinationSum2(vector&lt;int&gt;&amp; nums, int target) {
		vector&lt;vector&lt;int&gt;&gt; result;
		vector&lt;int&gt; item;
		set&lt;vector&lt;int&gt;&gt; res_set;
		sort(nums.begin(), nums.end());
		generate(0, nums, item, 0,target,result, res_set);
		return result;

	}

	void generate(int i, vector&lt;int&gt; &amp; nums, vector&lt;int&gt; &amp;item,int sum, int target,vector&lt;vector&lt;int&gt;&gt; &amp;result, set&lt;vector&lt;int&gt;&gt; &amp;res_set) {
		if (nums.size() == i || sum&gt;target)
		{
			return;
		}
		sum += nums[i];
		item.push_back(nums[i]);
		if ( sum == target &amp;&amp; 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&lt;string&gt; generateParenthesis(int n) {
		vector&lt;string&gt; result;
		string item="";
		generate(item, n, n,result);
		return result;

	}

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

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

LeetCode 51 N 皇后(H)

class Solution {
public:
	vector&lt;vector&lt;string&gt;&gt; solveNQueens(int n) {
		vector&lt;vector&lt;string&gt;&gt; result;
		vector&lt;vector&lt;int&gt;&gt; mark;
		vector&lt;string&gt; location;
		for (int i = 0; i &lt; n; i++)  // 创建nxn的矩阵,n列
		{
			mark.push_back(vector&lt;int&gt;()); // 先压入一个空vector,相当于行,然后在其基础上添加内容 
			for (int j = 0; j &lt; 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&lt;vector&lt;int&gt;&gt; &amp;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 &lt; mark.size(); i++) {
			for (int j = 0; j &lt; 8; j++) {
				int new_x = x + i*dx[j];
				int new_y = y + i*dy[j];
				if (new_x&lt;mark.size() &amp;&amp; new_x&gt;=0 &amp;&amp; new_y&gt;=0 &amp;&amp; new_y&lt;mark.size())
				{
					mark[new_x][new_y] = 1;
				}
			}
		}
	}

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

		for (int i = 0; i &lt; n; i++) { 
			if (mark[k][i] == 0) // 只找每一行为0的位置
			{
				vector&lt;vector&lt;int&gt;&gt; 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&lt;int&gt; &amp;sub_vec1, vector&lt;int&gt; &amp;sub_vec2, vector&lt;int&gt; &amp;vec) {
		int i = 0;
		int j = 0;
		while (i&lt;sub_vec1.size() &amp;&amp; j&lt; sub_vec2.size())
		{
			if (sub_vec1[i] &lt; sub_vec2[j])
			{
				vec.push_back(sub_vec1[i]);
				i++;
			}
			else
			{
				vec.push_back(sub_vec2[j]);
				j++;
			}
		}
		for(;i&lt;sub_vec1.size();i++)
			vec.push_back(sub_vec1[i]);
		for(;j&lt;sub_vec2.size();j++)
			vec.push_back(sub_vec2[j]);
	}
};

预备知识,一个数组的归并排序(nlogn):

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

class Solution {
public:
	void merge_sort_two_vec(vector&lt;int&gt; &amp;sub_vec1, vector&lt;int&gt; &amp;sub_vec2, vector&lt;int&gt; &amp;vec) {
		int i = 0;
		int j = 0;
		while (i&lt;sub_vec1.size() &amp;&amp; j&lt; sub_vec2.size())
		{
			if (sub_vec1[i] &lt; sub_vec2[j])
			{
				vec.push_back(sub_vec1[i]);
				i++;
			}
			else
			{
				vec.push_back(sub_vec2[j]);
				j++;
			}
		}
		for(;i&lt;sub_vec1.size();i++)
			vec.push_back(sub_vec1[i]);
		for(;j&lt;sub_vec2.size();j++)
			vec.push_back(sub_vec2[j]);
	}

	void merge_sort(vector&lt;int&gt; &amp;vec) { // 分治函数
		if (vec.size()&lt;2)
		{
			return;
		}
		int mid = vec.size() / 2;
		vector&lt;int&gt; sub_vec1;
		vector&lt;int&gt; sub_vec2;
		for (int i = 0; i &lt; mid;i++) {
			sub_vec1.push_back(vec[i]);
		}
		for (int i = mid; i &lt; 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&lt;int&gt; countSmaller(vector&lt;int&gt; &amp;nums)
	{
		vector&lt;pair&lt;int, int&gt;&gt; vec;
		vector&lt;int&gt; count;
		for (int i = 0; i &lt; 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&lt;pair&lt;int,int&gt;&gt; &amp;sub_vec1, vector&lt;pair&lt;int,int&gt;&gt; &amp;sub_vec2, vector&lt;pair&lt;int,int&gt;&gt; &amp;vec,vector&lt;int&gt;&amp;count) {
		int i = 0;
		int j = 0;
		while (i&lt;sub_vec1.size() &amp;&amp; j&lt; sub_vec2.size())
		{
			if (sub_vec1[i].first &lt;= 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&lt;sub_vec1.size();i++)
{
			count[sub_vec1[i].second]+=j;
			vec.push_back(sub_vec1[i]);
}
		for(;j&lt;sub_vec2.size();j++)
			vec.push_back(sub_vec2[j]);
	}

	void merge_sort(vector&lt;pair&lt;int,int&gt;&gt; &amp;vec, vector&lt;int&gt; &amp; count) {
		if (vec.size()&lt;2)
		{
			return;
		}
		int mid = vec.size() / 2;
		vector&lt;pair&lt;int,int&gt;&gt; sub_vec1;
		vector&lt;pair&lt;int, int&gt;&gt; sub_vec2;
		for (int i = 0; i &lt; mid;i++) {
			sub_vec1.push_back(vec[i]);
		}
		for (int i = mid; i &lt; 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. 递归,回溯,分治的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程