『面接アルゴリズム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)
重複数を含まない集合を与えて、すべての重複しないサブセットを求めます
LeetCode 90求サブセット2(M)
重複数を含む集合を与えて、すべての重複しないサブセットset()とsort()を求める
LeetCode 40の組合せ数の和2(M)
LeetCode 22は括弧(M)を生成する
n対の括弧が与えられ、まず、可能なすべての合法的な括弧の組合せが再帰的に生成される.コードは次のとおりです.
これに基づいて法則スクリーニングを行う.
LeetCode 51 Nクイーンズ(H)
LeetCode 315逆シーケンス数(H)
予備知識、2つの配列の集計ソート:
予備知識、配列の集計ソート(nlogn):
分治は,N規模の問題をK規模の小さいサブ問題に分解し,これらの問題は互いに独立して元の問題と性質が同じである.求めてからマージします.
質問:
4.再帰、遡及、分治
文書ディレクトリ
重複数を含まない集合を与えて、すべての重複しないサブセットを求めます
class Solution {
public:
vector> subsets(vector& nums) {
vector> result;
vector item;
result.push_back(item);
generate(0,nums,item,result);
return result;
}
void generate(int i, vector & nums, vector &item, vector> &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()とsort()を求める
class Solution {
public:
vector> subsetsWithDup(vector& nums) {
vector> result;
vector item;
result.push_back(item);
set> res_set;
sort(nums.begin(), nums.end());
generate(0, nums, item, result,res_set);
return result;
}
void generate(int i, vector & nums, vector &item, vector> &result, set> &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> combinationSum2(vector& nums, int target) {
vector> result;
vector item;
set> res_set;
sort(nums.begin(), nums.end());
generate(0, nums, item, 0,target,result, res_set);
return result;
}
void generate(int i, vector & nums, vector &item,int sum, int target,vector> &result, set> &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 generateParenthesis(int n) {
vector result;
string item="";
generate(item, n, n,result);
return result;
}
void generate(string item, int left,int right, vector &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> solveNQueens(int n) {
vector> result;
vector> mark;
vector location;
for (int i = 0; i < n; i++) // nxn ，n
{
mark.push_back(vector()); // 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> &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=0 && new_y>=0 && new_y &location,vector> &result, vector> &mark) {
if (k==n)
{
result.push_back(location);
return;
}
for (int i = 0; i < n; i++) {
if (mark[k][i] == 0) // 0
{
vector> 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)
予備知識、2つの配列の集計ソート:
class Solution {
public:
void merge_sort_two_vec(vector &sub_vec1, vector &sub_vec2, vector &vec) {
int i = 0;
int j = 0;
while (i 予備知識、配列の集計ソート(nlogn):
分治は,N規模の問題をK規模の小さいサブ問題に分解し,これらの問題は互いに独立して元の問題と性質が同じである.求めてからマージします.
class Solution {
public:
void merge_sort_two_vec(vector &sub_vec1, vector &sub_vec2, vector &vec) {
int i = 0;
int j = 0;
while (i &vec) { //
if (vec.size()<2)
{
return;
}
int mid = vec.size() / 2;
vector sub_vec1;
vector 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 countSmaller(vector &nums)
{
vector> vec;
vector 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> &sub_vec1, vector> &sub_vec2, vector> &vec,vector&count) {
int i = 0;
int j = 0;
while (i> &vec, vector & count) {
if (vec.size()<2)
{
return;
}
int mid = vec.size() / 2;
vector> sub_vec1;
vector> 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);
}
};