leetcode 习题集 [9月]
回溯
77. 组合
class Solution {
private:
vector<vector <int>> result;
vector<int> path;
// path用来存放符合条件的结果
void backtracking(int n, int k, int startIndex){
if(path.size() == k){
result.push_back(path);
return;
}
for(int i = startIndex; i <= n; i++){
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
result.clear();
path.clear();
backtracking(n, k ,1);
return result;
}
};
40. 组合总和 II
class Solution {
private:
// 设定两个变量 一个result 一个路径变量
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used){
if(sum == target){
result.push_back(path);
return;
}
for(int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++){
if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false){
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i + 1, used);
used[i] = false;
sum -= candidates[i] ;
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// 初始化used 集合 全部设置为false
vector<bool> used(candidates.size(), false);
path.clear();
result.clear();
sort(candidates.begin(), candidates.end());
backtracking(candidates,target, 0, 0 ,used);
return result;
}
};
131. 分割回文串
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(const string& s， int startIndex){
// 确定条件 返回result增加path
if(startIndex >= s.size()){
result.push_back(path);
return;
}
// 进行回溯
// 循环条件内判断 如果是回文字符串那么加入
for(int i = startIndex; i < s.size() ; i++){
if(isHuiWen(s), startIndex, i){
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
}else{
return;
}
backtracking(s, i + 1);
path.pop_back();
}
}
// 这里独有一个函数 判断是否是回文字符串
bool isHuiWen(const string& s, int start, int end){
for(int i = start, j = end; i < j; i++, j--){
if(s[i] != s[j]){
return false;
}
}
return true;
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};
做题思路：
93. 复原 IP 地址
class Solution {
private:
vector<string> result;
void backtracking(string& s, int startIndex, int pointNum){
if(pointNum == 3){
// 这个时候可以判断最后一段是否合法 如果是合法的就直接加入result中
if(isValid(s, startIndex, s.size() - 1)){
result.push_back(s);
}
return;
}
for(int i = startIndex ; i < s.size() ; i++){
if(isValid(s, startIndex, i)){
// 处理操作
s.insert(s.begin() + i + 1, '.');
pointNum++;
backtracking(s, i + 2, pointNum);
pointNum--;
s.erase(s.begin() + i + 1);
}else{
break;
}
}
}
bool isValid(const string& s, int start, int end){
if(start > end){
return false;
}
if(s[start] == '0' && start != end){
return false;
}
int num = 0 ;
for(int i =start; i <= end; i++){
if(s[i] > '9' || s[i] < '0'){
return false;
}
num = num * 10 + (s[i] - '0');
if(num > 255){
return false;
}
}
return true;
}
public:
vector<string> restoreIpAddresses(string s) {
result.clear();
if(s.size() < 4 || s.size() > 12) return result;
backtracking(s, 0 , 0);
return result;
}
};
78. 子集
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex){
// 收集子集 如果放到终止条件的话 会丢失kong
result.push_back(path);
if(startIndex >= nums.size()){
return;
}
for(int i= startIndex; i < nums.size(); i++){
// 处理节点
path.push_back(nums[i]);
// 递归
backtracking(nums, i + 1);
// 回溯
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};
90. 子集 II
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used){
result.push_back(path);
for(int i = startIndex; i < nums.size(); i++){
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); //去重需要排序
backtracking(nums, 0 , used);
return result;
}
};
贪心
贪心算法的步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
455. 分发饼干
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int index = s.size() - 1; //饼干数组的下标
int result = 0;
for(int i = g.size() - 1; i >= 0; i--){ //遍历胃口
if(index >= 0 && s[index] >= g[i]){
result++;
index--;
} //此时小饼干可以满足胃口
}
return result;
}
};
376. 摆动序列
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
int curDiff = 0; // 当前一对差值
int preDiff = 0; // 前一对差值
int result = 1; // 记录峰值个数，序列默认序列最右边有一个峰值
for (int i = 0; i < nums.size() - 1; i++) {
curDiff = nums[i + 1] - nums[i];
// 出现峰值
if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
preDiff = curDiff; // 注意这里，只在摆动变化的时候更新prediff
}
}
return result;
}
};
53. 最大子数组和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// result先从无线小开始
int result = INT32_MIN;
int count = 0;
for(int i =0; i < nums.size(); i++){
count += nums[i];
if(count > result){
result = count;
}
if(count <= 0) count = 0;
}
return result;
}
};