递归，回溯，分治（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("
");
    }
    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("
");
    }
    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;
                }

            }

        }

    }
};