//解法1
void rightTomid(int);
void rightToleft(int);
void leftTomid(int);
void midToleft(int);
void midToright(int);
void leftToright(int);
void rightTomid(int n) {
if (n == 1) {
cout << "move 1 from right to mid" << endl;
return;
}
rightToleft(n - 1);
cout << "move " << n << "from right to mid" << endl;
leftTomid(n - 1);
}
void rightToleft(int n) {
if (n == 1) {
cout << "move 1 from right to left" << endl;
return;
}
rightTomid(n - 1);
cout << "move " << n << "from right to left" << endl;
midToleft(n - 1);
}
void midToleft(int n) {
if (n == 1) {
cout << "move 1 from mid to left" << endl;
return;
}
midToright(n - 1);
cout << "move " << n << "from mid to left" << endl;
rightToleft(n - 1);
}
void midToright(int n) {
if (n == 1) {
cout << "move 1 from mid to right" << endl;
return;
}
midToleft(n - 1);
cout << "move " << n << "from mid to right" << endl;
leftToright(n - 1);
}
void leftTomid(int n) {
if (n == 1) {
cout << "move 1 from left to mid" << endl;
return;
}
leftToright(n - 1);
cout << "move " << n << " from left to mid" << endl;
leftTomid(n - 1);
}
void leftToright(int n) {
if (n == 1) {
cout << "Move 1 from left to right" << endl;
return;
}
leftTomid(n-1);
cout << "Move " << n << " from left to right" << endl;
midToright(n - 1);
}
void test02(int n) {
leftToright(n);
}
//---------------------------递归2--------------------
void test02_1_1(int n, string from, string to, string other) {
if (n == 1) {
cout << "move 1 from " << from << "to " << to << endl;
return;
}
test02_1_1(n - 1, from, other, to);
cout << "move " << n << " from " << from << " to" << endl;
test02_1_1(n - 1, other, to, from);
}
void test02_1(int n) {
test02_1_1(n, "left", "right", "mid");
}
2.逆序一个栈 不申请额外的数据结构
int fun(stack<int>& sta) {
int num = sta.top();
sta.pop();
if (sta.empty()) {
return num;
}
int last = fun(sta);
sta.push(num);
return last;
}
void test03_1(stack<int>& sta) {
if (sta.empty()) {
return;
}
int num = fun(sta);
test03_1(sta);
sta.push(num);
}
void test03() {
stack<int> sta;
sta.push(1);
sta.push(2);
sta.push(3);
sta.push(4);
sta.push(5);
test03_1(sta);
while (!sta.empty()) {
int tmp = sta.top();
sta.pop();
}
}
3.打印一个字符串的全部子序列,要求不出现重复字面值的子序列
set<string> restr;
string tmp;
void test04_1(string& str, int index) {
if (tmp.size() <= str.size()) {
restr.insert(tmp);
}
else {
return;
}
for (int i = index; i < str.size(); i++) {
tmp.push_back(str[i]);
test04_1(str, i + 1);
tmp.pop_back();
}
}
void test04() {
string str = "aac";
test04_1(str, 0);
for (const auto& s : restr) {
cout << s << endl;
}
}
4.打印一个字符串的全部排列,且不出现重复字面值的排列
set<string> vstr5;
string str5;
void test05_1(string& str, vector<bool> flag) {
if (str5.size() == str.size()) {
vstr5.insert(str5);
return;
}
for (int i = 0; i < str.size(); i++) {
if (flag[i] == true) continue;
flag[i] = true;
str5.push_back(str[i]);
test05_1(str, flag);
str5.pop_back();
flag[i] = false;
}
}
void test05() {
string str = "aac";
vector<bool> flag(str.size(), false);
test05_1(str, flag);
for (const auto& s : vstr5) {
cout << s << endl;
}
}
5.从左往右的尝试模型
5.1递归版本
规定1和A对应 2和B对应 3和C对应。。。则一个字符串比如“111”就可以转化为"AAA",“KA”和“AK”
给定一个只有数字字符组成的字符串str,返回有多少种转化结果
int test06_1(string& str, int index) {
if (index == str.size()) {
return 1;
}
if (str[index] == '0') {
return 0;
}
if (str[index] == '1') {
int ret = test06_1(str, index + 1);
if (index + 1 < str.size()) {
ret += test06_1(str, index + 2);
}
return ret;
}
if (str[index] == '2') {
int ret = test06_1(str, index + 1);
if (index + 1 < str.size() && (str[index] + 1 >= '0' && str[index + 1] <= '6')) {
ret += test06_1(str, index + 2);
}
return ret;
}
return test06_1(str, index + 1);
if (str[index] >= '1' && str[index] <= '9') {
}
}
void test06() {
string str = "11256";
test06_1(str, 0);
}
5.2动态规划版本
int test13_1(string str) {
vector<int> dp(str.size() + 1);
dp[str.size()] = 1;
for (int i = str.size() - 1; i >= 0; i--) {
if (str[i] == '0') {
dp[i] = 0;
}
else if (str[i] == '1') {
dp[i] = dp[i + 1];
if (i + 1 < str.size()) {
dp[i] += dp[i + 2];
}
}
else if (str[i] == '2') {
dp[i] = dp[i + 1];
if (i + 1 < str.size() && (str[i] + 1 >= '0' && str[i + 1] <= '6')) {
dp[i] += dp[i + 2];
}
}
else {
dp[i] = dp[i + 1];
}
}
return dp[0];
}
6.给定两个长度都为N的数组weights和values weights[i]和values[i]分别代表i号物品的重量和价值 给定一个正数bag,表示一个载重bag的袋子,所装物品不能超过这个重量,返回能装下的最多的价值
6.1递归版本
int test07_1(vector<int>& weights, vector<int>& values, int index, int bag, int cur) {
if (cur > bag) return -1;
if (index == weights.size()) {
return 0;
}
int p1 = test07_1(weights, values, index + 1, bag, cur);
int p2 = test07_1(weights, values, index + 1, bag, cur + weights[index]);
if (p2 != -1) {
p2 = values[index] + p2;
}
return max(p1, p2);
}
void test07() {
vector<int> vec1{ 1,2,3 };
vector<int> vec2{ 1,2,3 };
cout << test07_1(vec1, vec2, 0, 3, 0) << endl;
}
6.2动态规划版本
int test12_1(vector<int>& weights, vector<int>& values, int bag) {
int size = weights.size();
vector<vector<int>> dp(size + 1, vector<int>(bag + 1));
for (int i = size - 1; i >= 0; i--) {
for (int j = 0; j <= bag; j++) {
dp[i][j] = dp[i + 1][j];
if (j >= weights[i]) {
dp[i][j] = max(dp[i][j], values[i] + dp[i + 1][j - weights[i]]);
}
}
}
return dp[0][bag];
}
7.给定一个整数数组arr,代表数值不同的纸牌拍成一条线,玩家A和玩家B都绝顶2聪明,玩家A和玩家B依次拿走每张纸牌,每次都只能拿走最左或最有的纸牌,返回最后获胜者的分数
7.1递归版本
int test08_1(vector<int>& vec, int left, int right);
int test08_2(vector<int>& vec, int left, int right) {
if (left == right) {
return 0;
}
return min(test08_1(vec, left + 1, right), test08_1(vec, left, right - 1));
}
int test08_1(vector<int>& vec, int left ,int right) {
if (left == right) {
return vec[left];
}
return max(vec[left] + test08_2(vec, left + 1, right), vec[left] + test08_2(vec, left, right - 1));
}
void test08() {
vector<int> vec{ 1,2,3,4,5 };
}
7.2动态规划版本
int test14_1(vector<int>& vec) {
vector<vector<int>> dp1(vec.size(), vector<int>(vec.size()));
vector<vector<int>> dp2(vec.size(), vector<int>(vec.size()));
for (int i = 0; i < dp1.size(); i++) {
dp1[i][i] = vec[i];
}
for (int i = 1; i < vec.size(); i++) {
int l = 0;
int r = i;
while (l < vec.size() && r < vec.size()) {
dp1[l][r] = max(vec[l] + dp2[l + 1][r], vec[l] + dp2[l][r - 1]);
dp2[l][r] = min(dp1[l + 1][r], dp1[l][r - 1]);
l++, r++;
}
}
return std::max(dp1[0][vec.size() - 1], dp2[0][vec.size() - 1]);
}
8.N皇后问题
vector<vector<string>> res9;
vector<string> str9;
bool isVaild(int row, int col, vector<string>& s, int n) {
for (int i = 0; i < row; i++) {
if (s[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (s[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (s[i][j] == 'Q') return false;
}
return true;
}
void backtracking(int n, int startIndex) {
if (startIndex == n) {
res9.push_back(str9);
return;
}
for (int i = 0; i < n; i++) {
if (isVaild(startIndex, i, str9, n)) {
str9[startIndex][i] = 'Q';
backtracking(n, startIndex + 1);
str9[startIndex][i] = '.';
}
}
}
vector<vector<string>> test09(int n) {
str9 = vector<string>(n, string(n, '.'));
backtracking(n, 0);
return res9;
}
9.假设有一排数字,记为1-N, N一定大于或等于2,开始时机器人在其中M的位置上,如果机器人来到1位置,那么下一步只能往右来到2位置,如果机器人来到N位置,那么下一步只能往左来到N-1位置,如果机器人来到中间位置,那么下一步可以往左走也可以往右走,规定机器人必须走K步,最终能来到P位置的方法有多少种
int test10_1(vector<int>& vec, int index, int k, int p) {
if (k == 0) {
return index == p ? 1 : 0;
}
if (index == 0) {
return test10_1(vec, index + 1, k - 1, p);
}
if (index == vec.size() - 1) {
return test10_1(vec, index - 1, k - 1, p);
}
return test10_1(vec, index + 1, k - 1, p) + test10_1(vec, index - 1, k - 1, p);
}
void test10() {
vector<int> vec{ 2,6,8,6,4,7,1,2,3 };
test10_1(vec, 0, 5, 3);
}
10.上一道题的记忆化搜索
int test11_1(vector<int>& vec, int index, int k, int p, vector<vector<int>> dp) {
if (dp[index][k] != -1) {
return dp[index][k];
}
if (k == 0) {
dp[index][k] = index == p ? 1 : 0;
return dp[index][k];
}
if (index == 0) {
dp[index][k] = test11_1(vec, index + 1, k - 1, p, dp);
return dp[index][k];
}
if (index == vec.size() - 1) {
dp[index][k] = test11_1(vec, index - 1, k - 1, p, dp);
return dp[index][k];
}
dp[index][k] = test11_1(vec, index + 1, k - 1, p, dp) + test11_1(vec, index - 1, k - 1, p, dp);
return dp[index][k];
}
void test11() {
vector<int> vec{ 2,6,8,6,4,7,1,2,3 };
vector<vector<int>> dp(vec.size() + 1, vector<int>(4, -1));
test11_1(vec, 0, 5, 3, dp);
}
11.给定一个数组,数组中每一个位置的值都是一个货币的面值,每一种面值都可以使用任意张,数组中都是正数且无重复值,给定一个目标值,用给定数组中的数字,有多少种方法可以把目标值得出来。
11.1递归版本
int test15_1(vector<int>& vec, int index, int target) {
if (target < 0) {
return 0;
}
if (index == vec.size()) {
return target == 0 ? 1 : 0;
}
int ways = 0;
for (int i = 0; i * vec[index] <= target; i++) {
ways += test15_1(vec, index + 1, target - (i * vec[index]));
}
return ways;
}
11.2动态规划版本
int test15_2(vector<int>& vec, int target) {
if (vec.size() == 0 || target < 0) {
return 0;
}
vector<vector<int>> dp(vec.size() + 1, vector<int>(target + 1));
dp[vec.size()][0] = 1;
for (int i = vec.size()-1; i >= 0; i--) {
for (int rest = 0; rest <= target; rest++) {
int ways = 0;
for (int j = 0; j * vec[i] <= rest; j++) {
ways += dp[i + 1][rest - (j * vec[i])];
}
dp[i][rest] = ways;
}
}
return dp[0][target];
}
int test15_3(vector<int>& vec, int target) {
if (vec.size() == 0 || target < 0) {
return 0;
}
vector<vector<int>> dp(vec.size() + 1, vector<int>(target + 1));
dp[vec.size()][0] = 1;
for (int i = vec.size() - 1; i >= 0; i--) {
for (int rest = 0; rest <= target; rest++) {
dp[i][rest] = dp[i + 1][rest];
if (rest - vec[i] >= 0) {
dp[i][rest] += dp[i][rest - vec[i]];
}
}
}
return dp[0][target];
}
12.给定一个字符串str,给定一个字符串类型的数组arr,arr里的每一个字符串代表一张贴纸,使用arr里的字符拼凑出最少使用多少张贴纸完成任务(leetcode691)
//搜索拼凑target需要的最少贴纸数量
int dfs(unordered_map<string, int>& strStickerCnt, vector<vector<int>>& myStickers, string target) {
if (strStickerCnt.count(target)) {
//如果target已经搜索过,直接返回
return strStickerCnt[target];
}
int minRes = INT_MAX, stickersSize = myStickers.size();
//统计target中各个字符出现的次数
vector<int> tar(26, 0);
for (char ch : target) {
tar[ch - 'a'] += 1;
}
//尝试使用每一个sticker
for (int i = 0; i < stickersSize; ++i) {
//如果当前sticker中没有target[0]这个字符则剪枝,并且能防止死循环
if (myStickers[i][target[0] - 'a'] == 0) {
continue;
}
//使用当前sticker,nowTarget为运用贴纸后剩余的字母
string nowTarget = "";
for (int j = 0; j < 26; j++) {
if (tar[j] - myStickers[i][j] > 0) {
nowTarget += string(tar[j] - myStickers[i][j], 'a' + j);
}
}
//搜索nowTarget字符串需要最少贴纸数
int tempRes = dfs(strStickerCnt, myStickers, nowTarget);
//更新target字符串需要的最少贴纸数
if (tempRes != -1) {
minRes = min(minRes, 1 + tempRes);
}
}
strStickerCnt[target] = (minRes == INT_MAX ? -1 : minRes);//标记target已经搜索过
return strStickerCnt[target];
}
int test16(vector<string>& stickers, string target) {
int stickersSize = stickers.size();
unordered_map<string, int> strStickerCnt;//strStickerCnt[str]表示的字符串str需要的最少贴纸数量
vector<vector<int>> myStickers(stickersSize, vector<int>(26, 0));//各个贴纸中各个字母出现的次数
//统计每一个sticker中各个字符出现的次数
for (int i = 0; i < stickersSize; ++i) {
for (char ch : stickers[i]) {
myStickers[i][ch - 'a'] += 1;
}
}
strStickerCnt[""] = 0;//初始化,空字符串不需要贴纸
return dfs(strStickerCnt, myStickers, target);
}
13.两个字符串的最长公共子序列问题
int test17(string& s1, string& s2) {
if (s1.size() == 0 || s2.size() == 0) {
return 0;
}
vector<vector<int>> dp(s1.size(), vector<int>(s2.size()));
for (int i = 0; i < s2.size(); i++) {
if (s1[0] == s2[i]) {
dp[0][i] = 1;
}
if (i > 0) dp[0][i] = max(dp[0][i], dp[0][i - 1]);
}
for (int i = 0; i < s1.size(); i++) {
if (s1[i] == s2[0]) {
dp[i][0] = 1;
}
if (i > 0) dp[i][0] = max(dp[i][0], dp[i - 1][0]);
}
for (int i = 1; i < s1.size(); i++) {
for (int j = 1; j < s2.size(); j++) {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if (s1[i] == s2[j]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp[s1.size() - 1][s2.size() - 1];
}
14.给定一个数字arr和参数a和参数b,arr代表每个人准备刷杯子的时间,a代表洗一个杯子耗费的时间,b代表杯子自行挥发干净所用的时间,返回让所有咖啡杯边干净的最早完成时间*
14.1 递归
int test18_1(vector<int>& drinks, int a, int b, int index, int washLine) {
if (index == drinks.size() - 1) {
return min(max(washLine, drinks[index]) + a, drinks[index] + b);
}
int wash = max(washLine, drinks[index]) + a;
int next1 = test18_1(drinks, a, b, index + 1, wash);
int p1 = max(wash, next1);
int dry = drinks[index] + b;
int next2 = test18_1(drinks, a, b, index + 1, washLine);
int p2 = max(dry, next2);
return min(p1, p2);
}
14.2 DP
int test18_2(vector<int>& drinks, int a, int b) {
if (a >= b) {
return drinks[drinks.size() - 1] + b;
}
int N = drinks.size();
int limit = 0;
for (int i = 0; i < N; i++) {
limit = max(limit, drinks[i]) + a;
}
vector<vector<int>> dp(N, vector<int>(limit + 1));
for (int i = 0; i <= limit; i++) {
dp[N - 1][i] = min(max(i, drinks[N - 1]) + a, drinks[N - 1] + b);
}
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j <= limit; j++) {
int p1 = INT_MAX;
int wash = max(j, drinks[i]) + a;
if (wash <= limit) {
p1 = max(wash, dp[i + 1][wash]);
}
int p2 = max(drinks[i] + b, dp[i + 1][j]);
dp[i][j] = min(p1, p2);
}
}
return dp[0][0];
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)