能支持微信公众号的网站建设,四川住建厅考试报名官网,国内站长做国外网站,网页设计排版布局技巧文章目录1. K步编辑2. 折纸3. 字符串的不同排列4. 硬币排成线题目地址#xff0c;请点这 
1. K步编辑 
给出一个只含有小写字母的字符串的集合以及一个目标串(target)#xff0c;输出所有可以经过不多于 k 次操作得到目标字符串的字符串。 
你可以对字符串进行一下的3种操作:…
文章目录1. K步编辑2. 折纸3. 字符串的不同排列4. 硬币排成线题目地址请点这 
1. K步编辑 
给出一个只含有小写字母的字符串的集合以及一个目标串(target)输出所有可以经过不多于 k 次操作得到目标字符串的字符串。 
你可以对字符串进行一下的3种操作: 
加入1个字母删除1个字母替换1个字母 
考查动态规划最短编辑距离 
class Solution {
public:/*** param words: a set of stirngs* param target: a target string* param k: An integer* return: output all the strings that meet the requirements*/vectorstring kDistance(vectorstring words, string target, int k) {// write your code herevectorstring ans;for(auto w : words){if(minDistance(w, target)  k)ans.push_back(w);}return ans;}int minDistance(string word1, string word2) {int n1  word1.size(), n2  word2.size(), i, j;if(n10 || n20) return max(n1,n2);int dp[n11][n21];for(i  0; i  n11; i)dp[i][0]  i;for(j  0; j  n21; j)dp[0][j]  j;// DPint left, up, left_up;for(i  1; i  n11; i) {for(j  1; j  n21; j) {left     dp[i-1][j];up       dp[i][j-1];left_up  dp[i-1][j-1];if(word1[i-1] ! word2[j-1]) dp[i][j]  1  min(left, min(up, left_up));else// word1[i-1]  word2[j-1]dp[i][j]  left_up;}}return dp[n1][n2];}
};2. 折纸 
折纸每次都是将纸从右向左对折凹痕为 0凸痕为 1求折 n 次后将纸展开所得折痕组成的 01 序列。 1n201n201n20 
找规律拿张纸折几次就会发现规律了。下一个序列是在前一个序列的基础上插空加入010101... 
class Solution {
public:/*** param n: The folding times* return: the 01 string*/string getString(int n) {// Write your code hereif(n1) return 0;string ans, temp  0;while(--n){int flag  0;for(int i  0; i  temp.size(); i){ans  string(1, flag0)temp[i];flag  (flag0 ? 1 : 0);}ans  1;temp  ans;ans  ;}return temp;}
};3. 字符串的不同排列 
给出一个字符串找到它的所有排列注意同一个字符串不要打印两次。 请以字典序从小到大输出。 0n20 
排列组合回溯剪枝 
class Solution {
public:/*** param str: A string* return: all permutations*/vectorstring ans;vectorstring stringPermutation(string str) {// write your code heresort(str.begin(), str.end());vectorbool vis(str.size(), false);string s;dfs(str, s, 0, vis);return ans;}void dfs(string str, string s, int idx, vectorbool vis){if(idx  str.size()){ans.push_back(s);return;}for(int i  0; i  str.size(); i){if(vis[i])continue;if(i  1  !vis[i-1]  str[i-1]  str[i])continue;//剪枝去重s  str[i];vis[i]  true;dfs(str, s, idx1, vis);vis[i]  false;s.pop_back();}}
};4. 硬币排成线 
有 n 个硬币排成一条线, 第 i 枚硬币的价值为 values[i]. 
两个参赛者轮流从任意一边取一枚硬币, 直到没有硬币为止. 拿到硬币总价值更高的获胜. 
请判定 第一个玩家 会赢还是会输. 1n20001n20001n2000 
博弈 动态规划dp[i][j] 表示剩余硬币为 [i,j] 时我跟对手的最大差值 
class Solution {
public:/*** param values: a vector of integers* return: a boolean which equals to true if the first player will win*/bool firstWillWin(vectorint values) {// write your code hereint n  values.size(), i, j;vectorvectorint dp(n, vectorint(n, INT_MIN));for(i  0; i  n; i)dp[i][i]  values[i];for(int len  1; len  n; len){for(i  0; ilen  n; i){dp[i][ilen]  max(values[i]-dp[i1][ilen], values[ilen]-dp[i][ilen-1]);}}return dp[0][n-1]  0;}
};我的CSDN博客地址 https://michael.blog.csdn.net/ 
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步