??题目链接：Click me.
好多其实都是 Leetcode 的原题 0.0
Leetcode 原题：72. 编辑距离。
先解决 leetcode-72 。
给定字符串 A 和 B，我们一共有 6 种不同的操作（A 和 B 各有三种）。但是下面 3 种情况是等价的：
A[i] 修改和对 B[i] 修改。例如 A = "cat", B = "bat" ，那么修改单词 A 的第一个字母 b -> c，和修改单词 B 的第一个字母 c -> b 是等价的。A[i] 。B[i] 。那么实质上有效操作只有三种：
状态方程：dp[i, j] 为 s1 的前 i 个字符与 s2 的前 j 个字符的编辑距离。
转移方程
if s1[i-1] == s2[j-1] then:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]+1, di[i][j-1]+1)
else
dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)
/**
* dp[i-1][j]+1 表示向 A 插入一个字符后，与 B 相同
* dp[i][j-1]+1 表示向 B 插入一个字符后，与 A 相同
* dp[i-1][j-1]+1 表示修改 A 的一个字符后，与 B 相同
**/
代码实现
含空间优化。
class Solution
{
public:
int minDistance(string word1, string word2)
{
return dp1(word1, word2);
}
int dp1(string &s1, string &s2)
{
int len1 = s1.length(), len2 = s2.length();
if (len1 == 0) return len2;
if (len2 == 0) return len1;
vector<int> dp(len2 + 1, 0);
for (int j = 1; j <= len2; j++) dp[j] = j;
vector<int> buf(dp);
for (int i = 1; i <= len1; i++)
{
buf[0] = i - 1;
dp[0] = i;
for (int j = 1; j <= len2; j++)
{
if (s1[i - 1] == s2[j - 1])
dp[j] = min(buf[j - 1], min(buf[j], dp[j - 1]) + 1);
else
dp[j] = min(buf[j - 1], min(buf[j], dp[j - 1])) + 1;
}
buf = dp;
}
return dp.back();
}
int dp2(const string &s1, const string &s2)
{
int len1 = s1.length(), len2 = s2.length();
if (len1 == 0) return len2;
if (len2 == 0) return len1;
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
int i = 0, j = 0;
for (auto &v : dp) v[0] = i++;
for (int &x : dp[0]) x = j++;
for (i = 1; i <= len1; i++)
{
for (j = 1; j <= len2; j++)
{
if (s1[i - 1] == s2[j - 1])
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
else
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
return dp[len1][len2];
}
};
然后本题就很简单了：
vector<string> kDistance(vector<string> &words, string &target, int k)
{
// write your code here
vector<string> ans;
for (auto &x : words)
{
// dp1 是上面的函数
if (dp1(x, target) <= k)
ans.push_back(x);
}
return ans;
}
题目描述：折纸，每次都是将纸从右向左对折，凹痕为 0，凸痕为 1，求折 n 次后，将纸展开所得折痕组成的 01 序列。\(1 \le n \le 20\) .
样例：
样例 1
输入: 1
输出: "0"
样例 2
输入: 2
输出: "001"
这题是找规律。当场用纸模拟一下：
1 => 0
2 => 0 0 1
3 => 001 0 011
4 => 0010011 0 0011011
我们记 \(S_n\) 是第 \(n\) 次折纸的 01 序列。
那么：
其中 \(not(x)\) 表示对 01 序列按位取反，\(reverse(x)\) 表示对字符串 \(x\) 反转。
代码：
class Solution
{
public:
/**
* @param n: The folding times
* @return: the 01 string
*/
string getString(int n)
{
// Write your code here
string s = "0";
for (int i = 1; i < n; i++)
s = s + "0" + rev(s);
return s;
}
string rev(const string &s)
{
string res = "";
for (int i = (int)s.length() - 1; i >= 0; i--)
res += (s[i] == ‘0‘) ? ‘1‘ : ‘0‘;
return res;
}
};
描述：给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。 请以字典序从小到大输出。 \(0 \le n \le 20\) .
样例
样例 1
输入："abb"
输出：["abb", "bab", "bba"]
样例 2
输入："aabb"
输出：["aabb", "abab", "baba", "bbaa", "abba", "baab"]
代码
class Solution
{
public:
/**
* @param str: A string
* @return: all permutations
*/
vector<string> stringPermutation(string &str)
{
// write your code here
sort(str.begin(), str.end());
vector<string> ans;
ans.push_back(str);
while (next_permutation(str.begin(), str.end()))
{
ans.push_back(str);
}
return ans;
}
};
Leetcode 原题：486. 预测赢家。
递归解法
递归模拟 Alex 先手的 4 种情况：
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
return rec(nums);
}
bool rec(vector<int> &v)
{
if (v.size() <= 1) return true;
int sum = 0;
for (int x: v) sum+=x;
int alex = f(v, 0, (int)v.size()-1);
return alex >= (sum - alex);
}
int f(vector<int> &v, int l, int r)
{
if (l == r) return v[l];
if (l+1 == r) return max(v[l], v[r]);
if (l < r)
{
// Alex get 1st
// int a = v[l] + f(v, l+2, r);
// int b = v[l] + f(v, l+1, r-1);
// Alex get the last
// int c = v[r] + f(v, l+1, r-1);
// int d = v[r] + f(v, l, r-2);
// 为什么是 min ？因为「最优策略」下，要让对手 Bob 的得分最小
return max(v[l] + min(f(v, l+2, r), f(v, l+1, r-1)),
v[r] + min(f(v, l+1, r-1), f(v, l, r-2)));
}
return -1;
}
};
动态规划
参考官方题解。
状态方程：dp[i,j] 表示当数组剩下的部分为下标 i 到下标 j 时，当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。
只有当 \(i \le j\) 时，数组剩下的部分才有意义。
当 \(i \le j\) 时，当前玩家可以选择 \(nusm[i]\) 或 \(nums[j]\)，然后轮到另一个玩家在数组剩下的部分选取数字。在两种方案中，当前玩家会选择最优的方案，使得自己的分数最大化。因此可以得到如下状态转移方程：
最后判断 \(dp[0, len-1]\) 的值，如果大于或等于 0，则先手得分大于或等于后手得分，因此先手成为赢家，否则后手成为赢家。
代码实现：
bool dpSolution(vector<int> &v)
{
if (v.size() <= 1)
return true;
int len = v.size();
vector<vector<int>> dp(len, vector<int>(len, 0));
for (int i = 0; i < len; i++)
dp[i][i] = v[i];
for (int d = 1; d < len; d++)
{
for (int i = 0; i < (len - d); i++)
{
int j = i + d;
dp[i][j] = max(v[i] - dp[i + 1][j], v[j] - dp[i][j - 1]);
}
}
return dp[0][len - 1] >= 0;
}
原文：https://www.cnblogs.com/sinkinben/p/13736594.html