本文章记录贪心法的一些 LeetCode 题目，是我学习b站小象学院视频教程所做笔记，文末注明教程出处。侵删 ¯\_( ͡° ͜ʖ ͡°)_/¯

LeetCode [78] 子集

问题描述

给定一组不含重复元素的整数数组 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; } private: void generate(int i,vector<int>& nums,vector<int> &item,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); // 第二次递归调用 } };

位运算方法

算法思路

用2进制数代表子集情况，每一位则可以代表每一个元素。例如A,B,C三个元素，则可以用三位的二进制数表示子集的情况，如001可代表集合中只有A这个元素，111即表示三个元素都存在的子集； 用按位与就可以判断每一个二进制码（代表子集的情况）是否含该元素，例如，用001代表A元素，010代表B元素，100代表C元素，则如果有101按位与代表A这个元素的特定码，即001，有：101 & 001 = 1，即 true，则代表其中含有A这个元素，然后将A加入item，这样一来就把二进制码101识别为[A,C]，以此类推。

算法代码

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; int all_set = 1 << nums.size(); // 子集数量 2^n for(int i=0;i<all_set;i++){ // 遍历所有子集 vector<int> item; for(int j=0;j<nums.size();j++){ if(i & (1<<j)){ item.push_back(nums[j]); } // 整数 i 代表从0至2^n-1这2^n个集合 // (1<<j)为构造nums数组的第j个元素的特定二进制码 // 若 i & (1<<j) 为真则 nums[i] 加入item } result.push_back(item); } return result; } };

---

LeetCode [90] 子集Ⅱ

题目描述

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

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

示例

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

算法思想

在上文第一道题的递归算法思想上，要使得有不重复的子集，例如[1,2,1]和[1,1,2]也是属于重复情况。第一种重复情况是顺序一致的两个子集，另一种重复情况是顺序不一致的两个子集。故在前文递归算法基础上，只要对sums先进性排序，就能保证只有顺序一致的子集重复的情况，这时便可以用set集合进行查重去重操作。

算法代码

class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<vector<int>> result; vector<int> item; set<vector<int>> res_set; // 用于去重的集合 set sort(nums.begin(),nums.end()); // 先进行排序，保证由于含有相同元素的集合完全一致能被set识别 result.push_back(item); // 加入空集 generate(0,nums,item,result,res_set); // 调用函数 return result; } private: void generate(int i,vector<int>& nums,vector<int> &item,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); // 第二次递归调用 } };

---

LeetCode [40] 组合总和Ⅱ

题目描述

给定一个数组 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] ]

算法思路

也是在[90]那道题上略微修改，运用剪枝操作，遇到子集构造过程中子集元素和已大于target目标时，提前回溯，大大提高算法效率！

算法代码

class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<vector<int>> result; vector<int> item; set<vector<int>> res_set; // 用于去重的集合 set sort(candidates.begin(),candidates.end()); // 先进行排序，保证由于含有相同元素的集合完全一致能被set识别 generate(0,candidates,item,result,res_set,0,target); // 调用函数 return result; } private: void generate(int i,vector<int>& nums,vector<int> &item,vector<vector<int>>& result,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()){ result.push_back(item); res_set.insert(item); } generate(i+1,nums,item,result,res_set,sum,target); // 第一次递归调用 item.pop_back(); sum -= nums[i]; generate(i+1,nums,item,result,res_set,sum,target); // 第二次递归调用 } };

---

LeetCode [20] 括号生成

题目描述

数字 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){ // item 为表示一种组合的 string // left 为当前还能放置左括号的数量 // right 为当前还能放置的有括号的数量 if(left==0 && right==0){ result.push_back(item); return ; } if(left > 0){ generate(item+'(',left-1,right,result); } if(left<right){ generate(item+')',left,right-1,result); } } };

---

LeetCode [51] N皇后

问题描述

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

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

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

示例

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

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

算法思路

先写一个函数用来计算当棋盘中（x,y）被放置皇后后，整个棋盘会剩下多少个可以放另外的皇后而不被攻击的格子，用一个矩阵表示，初始矩阵为 0，后计算出会被攻击的格子置为 1.利用回溯算法，每次考虑一行的皇后放置，按列遍历看哪个格子为安全格子，便进行放置，如果到某种情况下皇后没有格子可放了就回溯。直接上图吧

图片来自小象学院教程

算法代码

class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>> result; vector<string> location; vector<vector<int>> mark; 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: // 放置一个皇后 mark 矩阵相应改变的函数 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}; static const int dy[] = {0,0,-1,1,-1,1,-1,1}; 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_x<mark.size() && 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){ vector<vector<int>> tmp_mark = mark; location[k][i] = 'Q'; put_down_the_queen(k,i,mark); generate(k+1,n,location,result,mark); mark = tmp_mark; location[k][i] = '.'; } } } };

---

LeetCode [315] 计算右侧小于当前元素的个数（求逆序数）

题目描述

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

示例

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

算法思路

分治法的归并排序

这道题的重要思路是由归并排序扩展开的，先补充一下归并排序

#include<iostream> #include<vector> using namespace std; // 把两个已排序的数组有序合成 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); } int main() { int nums[] = { -3,9,4,10,23,5,11,-6,21,-7 }; vector<int> vec; for (int i = 0; i < 10; i++) { vec.push_back(nums[i]); } merge_sort(vec); for (int i = 0; i < 10; i++) { cout << vec[i] << " "; } return 0; }

算法思路

每次有两个已经排序好的两个数组，按上面归并排序第一个函数（把两个已排序的数组有序合成）的算法加入新的数组，而其中第一个数组中的count即为j的值（i为第一个数组的索引，j为第二个数组的索引）。

算法代码

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); // 将nums[i]与 i 绑定为 pair } merge_sort(vec, count); return count; } private: 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) { // 比较用pair的第一个元素 count[sub_vec1[i].second] += j; // 第二个元素缩影用来记录count 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); } };

ps: 小象学院教程 https://www.bilibili.com/video/BV1GW411Q77S?t=7029&p=2