master公式
- 所有子问题规模相同的递归才能用master公式:
T(n)=a*T(n/b)+O(n^c),a、b、c为常数
- 若log(b, a) < c,复杂度为O(n^c),log(b, a)是以b为底a的对数
- 若log(b, a) > c,复杂度为O(n^log(b, a))
- 若log(b, a) = c,复杂度为O(n^c * logn)
- T(n)=2*T(n/2)+O(n*longn),时间复杂度为O(n*(logn)^2)
字符串的全部子序列
-
时间复杂度 O(2^n * n)
-
常规做法
#include <vector>
#include <iostream>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<string> res;
unordered_set<string> st;
string path;
void generate(string &s, int curIndex) {
if (curIndex == s.length()) {
// 去重
if (st.find(path) != st.end()) return;
res.emplace_back(path);
st.emplace(path);
return;
}
// curIndex 处选中
path.append(1, s[curIndex]);
// 递归处理下个位置
generate(s, curIndex + 1);
// 回溯,删除最后一个字符
path.erase(path.length() - 1, 1);
generate(s, curIndex + 1);
}
vector<string> generatePermutation(string s) {
generate(s, 0);
return res;
}
};
- 省去擦除
#include <vector>
#include <iostream>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<string> res;
unordered_set<string> st;
string path;
// size 为当前 path 中有效长度
void generate(string &s, int curIndex, int size) {
if (curIndex == s.length()) {
// 只选取有效长度
string str = path.substr(0, size);
// 去重
if (st.find(str) != st.end()) return;
res.emplace_back(str);
st.emplace(str);
return;
}
path[size] = s[curIndex];
// curIndex 处选中,path 的长度变为 size + 1
generate(s, curIndex + 1, size + 1);
// curIndex 处不选中,path 的长度还是 size
generate(s, curIndex + 1, size);
}
vector<string> generatePermutation(string s) {
path.resize(s.length());
generate(s, 0, 0);
return res;
}
};
90. 子集 II
-
时间复杂度 O(2^n * n)
-
相同的元素作为一段
#include <vector>
#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void generate(vector<int> &nums, int curIndex) {
if (curIndex == nums.size()) {
res.emplace_back(path);
return;
}
int end = curIndex;
while (end < nums.size() && nums[end] == nums[curIndex])
end++;
// 这一段相同的元素的个数
int len = end - curIndex;
// 选中 i 个这种元素
for (int i = 0; i <= len; ++i) {
for (int j = 0; j < i; ++j)
path.emplace_back(nums[curIndex]);
// 递归处理下一段
generate(nums, curIndex + len);
// 回溯
for (int j = 0; j < i; ++j)
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
sort(nums.begin(), nums.end());
generate(nums, 0);
return res;
}
};
- 省去擦除
#include <vector>
#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
// size 为当前 path 中有效长度
void generate(vector<int> &nums, int curIndex, int size) {
if (curIndex == nums.size()) {
// 选取有效位置
res.emplace_back(vector<int>(begin(path), begin(path) + size));
return;
}
int end = curIndex;
while (end < nums.size() && nums[end] == nums[curIndex])
end++;
// 这一段相同的元素的个数
int len = end - curIndex;
// 选中 i 个这种元素
for (int i = 0; i <= len; ++i) {
for (int j = 0; j < i; ++j)
path[size + j] = nums[curIndex];
// 递归处理下一段
generate(nums, curIndex + len, size + i);
}
}
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
sort(nums.begin(), nums.end());
path.resize(nums.size());
generate(nums, 0, 0);
return res;
}
};
46. 全排列
-
时间复杂度 O(n! * n)
-
按字典序输出
-
用哈希表标记
nums
中某个位置是否已经加入到path
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<bool> entered;
// path 中 [0, curIndex) 已经放入数据,现在往 curIndex 处放入所有可能
void generate(vector<int> &nums, int curIndex) {
if (curIndex == nums.size()) {
res.emplace_back(path);
return;
}
for (int i = 0; i < nums.size(); ++i) {
// nums[i] 还没放入,就放入到 curIndex 位置
if (!entered[nums[i] + 10]) {
path[curIndex] = nums[i];
// 标记nums[i] 已经放入
entered[nums[i] + 10] = true;
// 递归处理子问题,尝试 curIndex + 1 处所有的放入可能
generate(nums, curIndex + 1);
// 取消标记,再尝试在 curIndex 处放入其他还没使用过的数据
entered[nums[i] + 10] = false;
}
}
}
// 按字典序输出
vector<vector<int>> permute(vector<int> &nums) {
entered.resize(21, false);
path.resize(nums.size());
generate(nums, 0);
return res;
}
};
- 不按字典序
- 把所有加入到
path
的元素移到nums
中的左侧,当前位置从nums
右侧元素中挑选
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
// path 中 [0, curIndex) 已经放入数据,现在往 curIndex 处放入所有可能
void generate(vector<int> &nums, int curIndex) {
if (curIndex == nums.size()) {
res.emplace_back(path);
return;
}
// nums[left] 开始到末尾都是尚未使用过的元素,从中挑出一个使用,并且在 nums 中和 nums[left] 交换位置
// 这样以来 nums 从开头到 nums[left] 就是已经使用过的元素
int left = curIndex;
for (int right = left; right < nums.size(); ++right) {
path[curIndex] = nums[right];
// 标记 nums[i] 已经放入
swap(nums[left], nums[right]);
// 递归处理子问题,尝试 curIndex + 1 处所有的放入可能
generate(nums, curIndex + 1);
// 取消标记,再尝试在curIndex处放入其他还没使用过的数据
swap(nums[left], nums[right]);
}
}
// 不按字典序输出,不使用 entered 标记元素是否使用过
vector<vector<int>> permute(vector<int> &nums) {
path.resize(nums.size());
generate(nums, 0);
return res;
}
};
- 省去
path
直接在nums
中操作
// 以 curIndex 作为标记,nums[0, curIndex)是已经排好的,也就是使用过的元素
class Solution {
public:
vector<vector<int>> res;
void backtrack(vector<int> &nums, int curIndex) {
if (curIndex == nums.size()) {
res.emplace_back(nums);
return;
}
// nums[0, curIndex)是已经排好的
// 从 nums[curIndex, nums.size()-1] 中选一个 nums[i] 放到 nums[curIndex]
for (int i = curIndex; i < nums.size(); ++i) {
// nums[i] 放到 nums[curIndex]
swap(nums[i], nums[curIndex]);
// 继续递归填下一个数
backtrack(nums, curIndex + 1);
// 撤销操作
swap(nums[i], nums[curIndex]);
}
}
// 不按字典序输出
vector<vector<int>> permute(vector<int> &nums) {
backtrack(nums, 0);
return res;
}
};
// 把 nums 数组当作标记数组
class Solution {
public:
vector<vector<int>> res;
vector<int> output;
// output 中 0 到 curIndex 已经放入数据,现在往 curIndex 处放入所有可能
void backtrack(vector<int> &nums, int curIndex) {
// output 已经放满,把当前排列添加到结果中
if (curIndex == nums.size()) {
res.emplace_back(output);
return;
}
for (int i = 0; i < nums.size(); ++i) {
// 已经被使用过的就跳过
if (nums[i] == INT_MIN) continue;
int temp = nums[i];
// 标记
nums[i] = INT_MIN;
output.emplace_back(temp);
// 继续递归填下一个数
backtrack(nums, curIndex + 1);
// 撤销操作
output.pop_back();
nums[i] = temp;
}
}
// 不按字典序输出
vector<vector<int>> permute(vector<int> &nums) {
backtrack(nums, 0);
return res;
}
};
47. 全排列 II
-
时间复杂度 O(n! * n)
-
给定一个可包含重复数字的序列
nums
,按任意顺序返回所有不重复的全排列。
#include <vector>
#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> res;
void backtrack(vector<int> &nums, int curIndex) {
if (curIndex == nums.size()) {
res.emplace_back(nums);
return;
}
// 标记元素是否曾经放入 curIndex
unordered_set<int> st;
// nums[0, curIndex)是已经排好的
// 从 nums[curIndex, nums.size()-1] 中选一个 nums[i] 放到 nums[curIndex]
for (int i = curIndex; i < nums.size(); ++i) {
// 避免生成重复的
if (st.find(nums[i]) != st.end()) continue;
st.emplace(nums[i]);
// nums[i] 放到 nums[curIndex]
swap(nums[i], nums[curIndex]);
// 继续递归填下一个数
backtrack(nums, curIndex + 1);
// 撤销操作
swap(nums[i], nums[curIndex]);
}
}
vector<vector<int>> permuteUnique(vector<int> &nums) {
backtrack(nums, 0);
return res;
}
};
用递归函数逆序栈
- 时间复杂度 O(n^2)
#include <vector>
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <stack>
using namespace std;
// 栈底元素移除掉,上面的元素依次落下来,返回移除掉的栈底元素
int bottomOut(stack<int> &stack) {
// 当前栈顶出栈
int top = stack.top();
stack.pop();
// 栈空就返回唯一的栈顶元素
if (stack.empty()) return top;
// 栈不空,就取出栈底,其他按原来的顺序压栈
int bottom = bottomOut(stack);
stack.push(top);
return bottom;
}
void reverse(stack<int> &stack) {
if (stack.empty()) return;
int bottom = bottomOut(stack);
reverse(stack);
// 最先取出的栈底,最后入栈,从而实现逆序栈
stack.push(bottom);
}
int main() {
stack<int> stack;
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
reverse(stack);
while (!stack.empty()) {
cout << stack.top() << endl;
stack.pop();
}
return 0;
}
用递归函数排序栈
- 时间复杂度 O(n^2)
#include <iostream>
#include <stack>
#include <cstdlib>
#include <climits>
using namespace std;
class Solution {
public:
static void sort(stack<int> &stack) {
int depth = getDepth(stack);
while (depth > 0) {
int max = getMax(stack, depth);
int k = countOccurrences(stack, depth, max);
moveToBottom(stack, depth, max, k);
depth -= k;
}
}
// 递归求栈深
static int getDepth(stack<int> &stack) {
if (stack.empty()) return 0;
int top = stack.top();
stack.pop();
int depth = getDepth(stack) + 1;
stack.push(top);
return depth;
}
// 递归求栈中最大值
static int getMax(stack<int> &stack, int depth) {
if (depth == 0) return INT_MIN;
int top = stack.top();
stack.pop();
int tempMax = getMax(stack, depth - 1);
int finalMax = max(top, tempMax);
stack.push(top);
return finalMax;
}
// 递归求最大值出现次数
static int countOccurrences(stack<int> &stack, int depth, int max) {
if (depth == 0) return 0;
int top = stack.top();
stack.pop();
int tempTimes = countOccurrences(stack, depth - 1, max);
int finalTimes = tempTimes + (top == max ? 1 : 0);
stack.push(top);
return finalTimes;
}
static void moveToBottom(stack<int> &stack, int depth, int max, int k) {
if (depth == 0) {
// 把出现 k 次的最大值压入栈底
for (int i = 0; i < k; i++) {
stack.push(max);
}
} else {
int top = stack.top();
stack.pop();
moveToBottom(stack, depth - 1, max, k);
// 除了最大值,其他值按照原来的顺序入栈
if (top != max) stack.push(top);
}
}
static stack<int> randomStack(int n, int v) {
stack<int> ans;
for (int i = 0; i < n; i++)
ans.push(rand() % v);
return ans;
}
static bool isSorted(stack<int> &stack) {
int pre = INT_MIN;
while (!stack.empty()) {
if (pre > stack.top()) return false;
pre = stack.top();
stack.pop();
}
return true;
}
static void test() {
stack<int> test;
test.push(1);
test.push(5);
test.push(4);
test.push(5);
test.push(3);
test.push(2);
test.push(3);
test.push(1);
test.push(4);
test.push(2);
sort(test);
while (!test.empty()) {
cout << test.top() << endl;
test.pop();
}
// Random test
int N = 20;
int V = 20;
int testTimes = 20000;
cout << "Testing started" << endl;
for (int i = 0; i < testTimes; i++) {
int n = rand() % N;
stack<int> stack = randomStack(n, V);
sort(stack);
if (!isSorted(stack)) {
cout << "Error!" << endl;
break;
}
}
cout << "Testing ended" << endl;
}
};
int main() {
Solution::test();
return 0;
}
打印n层汉诺塔问题的最优移动轨迹
- 时间复杂度 O(2^n)
- 有三根杆子A,B,C。A杆上有 N 个 (N>1) 穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆:
- 每次只能移动一个圆盘;
- 大盘不能叠在小盘上面。
- n 层汉诺塔最少移动 2^n - 1 步
#include <iostream>
#include <stack>
#include <cstdlib>
#include <climits>
#include <string>
using namespace std;
class Solution {
public:
static void hanoi(int n) {
// 1. 把 n 层从 from 移动到 to
if (n > 0) move(n, "左", "右", "中");
}
static void move(int i, const string &from, const string &to, const string &other) {
if (i == 1) {
cout << "移动圆盘 1 从 " << from << " 到 " << to << endl;
} else {
// 2. 先把 n - 1 层从 from 移动到 other
move(i - 1, from, other, to);
// 3. 再把第 n 层的圆盘从 from 移动到最终目标 to 上,此时原来上面的 n - 1 层还在 other 上
cout << "移动圆盘 " << i << " 从 " << from << " 到 " << to << endl;
// 4. 把着 n - 1 层从 other 移到最终目标 to 上
move(i - 1, other, to, from);
}
}
};
int main() {
int n = 3;
Solution::hanoi(n);
return 0;
}
标签:递归,nums,int,vector,经典,curIndex,include,stack
From: https://www.cnblogs.com/sprinining/p/18448540