数据结构与算法

以下题目均来自leetcode、poj

回溯法又称为试探法，但当探索到某一步时，发现选择达不到目标，就回退一步重新选择。

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

//放一个递归，不放一个递归

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;
    }
public:
    void generate(int i,vector<int>& nums,vector<vector<int>>& result){
        if(i >= nums.size()){
            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);
    }
};

位运算

运算符	含义	举例	十进制形式
&	按位与	0011&0101=0001	3&5=1
︳	按位或	0011 ︳ 0101=0111	3︳ 5=7
^	按位异或	0011^0101=0110	3^5=6
~	取反	~0011=1100	~3=12
«	左移	0011«2=1100	3«2 = 3X2X2=12
»	右移	0101»2=0001	5»2 = 5/2/2=1

组合

集合	数	A	B	C
{}	000=0	100&000=0	010&000=0	001&000=0
{C}	001=1	100&001=0	010&001=0	001&001=1
{B}	010=2	0	1	0
{BC}	011=3	0	1	1
{A}	100=4	1	0	0
{AC}	101=5	1	0	1
{AB}	110=6	1	1	0
{ABC}	111=7	1	1	1

位运算：A&0=0，A&1=A。A

0=A，A

1=1

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;

        //1<<n=2的n次方

        int all_set = 1 << nums.size();
        
        for(int i = 0;i < all_set;i++){
            vector<int> item;
            for(int j = 0;j < nums.size();j++){
                if(i &( 1 << j)){ 

                    //1 << 0 = 2的0次方 = 001

                    //1 << 1 = 2的1次方 = 010

                    //1 << 2 = 2的2次方 = 100

                    item.push_back(nums[j]);
                }
            }
            result.push_back(item);
        }
        return result;
    }

};

子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

//先排序，再用set去重

class Solution {
public:
     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> item;
        set<vector<int>> res_set;
        std::sort(nums.begin(),nums.end());
        result.push_back(item);
        generate(0,nums,item,result,res_set);
        return result;
    }
public:
    void generate(int i,vector<int>& nums,vector<vector<int>>& result，set<vector<int>>& res_set){
        if(i >= nums.size()){
            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);
    }
};

组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]

//搜索回溯过程中进行剪枝操作

class Solution {
public:
     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> item;
        set<vector<int>> res_set;
        std::sort(candidates.begin(),candidates.end());
        result.push_back(item);
        generate(0,candidates,item,result,res_set,0,target);
        return result;
    }
public:
    void generate(int i,vector<int>& candidates,vector<vector<int>>& result，set<vector<int>>& res_set,
    int sum,int target){
        if(sum > target || i >= candidates.size()){
            return;
        }
        sum+=candidates[i];
        item.push_back(candidates[i]);

        if(sum == target && res_set.find(item) == res_set.end()){
            result.push_back(item);
            res_set.insert(item);
        }

        generate(i+1,candidates,item,result,res_set,sum,target);
        sum -= candidates[i];
        item.pop_back();
        generate(i+1,candidates,item,result,res_set,num,target);
    }
};

括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

//左括号和右括号的数量 最多放置n个
//左括号的数量<=右括号数量，不可进行放置右括号的递归 

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        generate("",n,n,result);
        return result;
    }
private:
    void generate(string item,int left,int right,vector<string>& result){
        if(left == 0 && right == 0){
            result.push_back(item);
        }
        if(left > 0){
            generate(item+"(",left-1,right,result);
        }
        if(left > right){ //剪枝
        
            generate(item+")",left,right-1,result);
        }
};

n 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

输入: 4 输出: [ [“.Q..”, // 解法 1 “…Q”, “Q…”, “..Q.”],

[”..Q.”, // 解法 2 “Q…”, “…Q”, “.Q..”] ] 解释: 4 皇后问题存在两个不同的解法。

//每行只能放一个皇后， 递归行，找能放置列 ，该行所有列都无法放就回溯

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++){
            mark.push_back(vector<int>());
            for(int j = 0;j < n;j++){
                mark[i].push_back(0);
            }
            location.push_back("");
            location[i].append(n,".");
        }
        generate(0,n,location,result,mark);
        return result;
    }

private:
    //row代表完成了几次皇后放置 行数

    void generate(int row,int n,
    vector<string>& location,
    vector<vector<string>>& result,
    vector<vector<int>>& mark
    ){
        if(row == n){
            result.push_back(location);
            return;
        }
        for(int col = 0; col < n;col++){//尝试0到n-1列

            if(mark[row][col] == 0){
                vector<vector<int>> tempMark = mark;//回溯用

                location[row][col] = "Q";
                putDownTheQueen(row,col,mark);   
                generate(row+1,n,location,result,mark);
                mark = tempMark;//回溯

                location[row][col] = ".";
            }
        }
    }

    void putDownTheQueen(int row,int col,vector<vector<int>>& mark){
        static const int dRow[] = {-1,1,0,0,-1,-1,1,1};
        static const int dCol[] = {0,0,-1,1,-1,1,-1,1};
        mark[row][col] = 1;
        int wh = mark.size();
        for(int i = 1;i < wh;i++){
            for(int j = 0;j < 8;j++){
                int newRow = row + i*dRow[j];
                int newCol = col + i*dCol[j];
                if(newRow >= 0 && newRow < wh &&
                newCol >= 0 && newCol < wh &&)
                mark[newRow][newCol] = 1;
            }
        }
    }
};

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

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1] 输出: [2,1,1,0] 解释: 5 的右侧有 2 个更小的元素 (2 和 1). 2 的右侧仅有 1 个更小的元素 (1). 6 的右侧有 1 个更小的元素 (1). 1 的右侧有 0 个更小的元素.

//在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
//10 5 4 2 6 1 7 3 9 14 12 15 13 11 8
//数一数它的逆序数：9+4+3+1+2+0+1+0+1+4+2+3+2+1+0=33

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);
        }
        mergeSort(vec,count);
        return count;
    }

private:
    void meregeSortTwoVec( vector<pair<int,int>> &sub_vec1,
        vector<pair<int,int>> &sub_vect2,
        vector<pair<int,int>> &vec,
        vector<int> &count){
       int i = 0;
       int j = 0;
       while(i < sub_vec1.size() && j< sub_vec2.size()){
           //前数组第i个元素小或等后面数组j个元素，要插入时，其count值为后一个数组的j
           
           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 mergeSort(vector<pair<int,int>> &vec,
        vector<int> &count)){
        if(vect.size()< 2){
            return;
        }
        int middle = vec.size()/2;
        vector<pair<int,int>> &sub_vec1;
        vector<pair<int,int>> &sub_vect2;
        for(int i = 0;i < middle;i++){
            sub_vec1.push_back(vec[i]);
        }
        for(int i = middle;i < vec.size();i++){
            sub_vec2.push_back(vec[i]);
        }
        mergeSort(sub_vec1,count);
        mergeSort(sub_vec2,count);
        vec.clear();
        meregeSortTwoVec(sub_vec1,sub_vec2,vec,count);
    }
};

递归、回溯、分治

子集

子集 II

组合总和 II

括号生成

n 皇后

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

CATALOG

FEATURED TAGS

FRIENDS