wy的leetcode刷题记录_Day28_动态规划完结篇
时间：2022-10-30
784. 字母大小写全排列
今天的每日一题是：784. 字母大小写全排列
题目介绍
- 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
- 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
示例 1：
输入：s = “a1b2”
输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]
示例 2:
输入: s = “3z4”
输出: [“3z4”,“3Z4”]
思路
首先对于大小写的转换，我们可以通过位运算来操作因为每个字符的大小转换相差32，我们可以通过异或32来转换，而对于搜索的话我们可以采用BFS或者DFS，这里我们采用BFS来操作：我们遍历每一个字符c：
- 如果c为一个数字，则队列中的所有序列的末尾都加上一个c，修改后的序列放入队列
- 如果c是一个字母，则所有的序列末尾分别加上c的小写形式和大写形式后，再放入队列
- 如果队列中的字符长度等与s的长度，则表示搜索已经完成了
代码
class Solution {
public:
vector<string> letterCasePermutation(string s) {
vector<string> ans;
queue<string> qu;
qu.emplace("");
while (!qu.empty()) {
string &curr = qu.front();
if (curr.size() == s.size()) {
ans.emplace_back(curr);
qu.pop();
} else {
int pos = curr.size();
if (isalpha(s[pos])) {
string next = curr;
next.push_back(s[pos] ^ 32);
qu.emplace(next);
}
curr.push_back(s[pos]);
}
}
return ans;
}
};
收获
使用BFS搜索s，最重要的是遍历顺序，不明白的可以打印出来看每一轮的情况，这样才能理解。
647. 回文子串
647. 回文子串
题目介绍
- 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
- 回文字符串 是正着读和倒过来读一样的字符串。
- 子字符串 是字符串中的由连续字符组成的一个序列。
- 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
思路
方法一：动态规划
- 确定dp数组的含义：布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的?串是否是回??串，如果是dp[i][j]为
true，否则为false。 - 确定dp数组的递推公式：首先我们通过嵌套循环来比较俩个字符是否相等，如果不相等的话那肯定不是回文字符串，如果相等的话情况还得细分，当ij时，也就是遍历到同一个字符的情况那肯定是回文字符串，如果i-j1那么就是这俩个字符相邻相等那么肯定也是回文字符串，而其他情况则取决于内层的字符串也就是dp[i+1][j-1]的情况，如果内层字符串是回文字符串那么他就是回文字符串，反之不是回文字符串
- 初始化：一开始所有的都初始化为false
- 遍历顺序：对于这道题遍历顺序是非常重要的，因为我们的dp[i][j]大概率通过dp[i+1][j-1]推出，所以我们肯定是从下到上，从左到右开始遍历,即从左下向右上递推。
方法二：双指针法
?先确定回?串，就是找中?然后想两边扩散看是不是对称的就可以了。在遍历中?点的时候，要注意中?点有两种情况。?个元素可以作为中?点，两个元素也可以作为中?点。
代码
class Solution {
public:
int countSubstrings(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n,false));
int result=0;
for(int i=n-1;i>=0;i--)
{
for(int j=i;j<n;j++)
{
if(s[i]==s[j])
{
if(j-i<=1)
{
dp[i][j]=true;
result++;
}
else if(dp[i+1][j-1])
{
result++;
dp[i][j]=true;
}
}
}
}
return result;
}
};
class Solution {
public:
int countSubstrings(string s) {
int result = 0;
for (int i = 0; i < s.size(); i++) {
result += extend(s, i, i, s.size());
result += extend(s, i, i + 1, s.size());
}
return result;
}
int extend(const string& s, int i, int j, int n) {
int res = 0;
while (i >= 0 && j < n && s[i] == s[j]) {
i--;
j++;
res++;
}
return res;
}
};
收获
这道题比较重要的就是递推的遍历顺序，对于遍历顺序我们首先需要列出相应的递推公式，然后根据公式手绘一个图看一下具体的遍历方法，首先必须得保证不能超限，其次保证不能死循环，最重要的是一定是由已知的知去推未知的值。
516. 最长回文子序列
516. 最长回文子序列
题目介绍
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。
示例 2：
输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。
思路
- 确定dp数组的含义：dp[i][j]：字符串s在[i, j]范围内最?的回??序列的?度为dp[i][j]。
- 确定dp数组的递推公式：如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;如果s[i]与s[j]不相同，，那么分别加?s[i]、s[j]看看哪?个可以组成最?的回??序列。加?s[j]的回??序列?度为dp[i + 1][j]。加?s[i]的回??序列?度为dp[i][j - 1]。那么dp[i][j]?定是取最?的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
- 初始化：
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0)); for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
代码
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i + 1; j < s.size(); j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][s.size() - 1];
}
};
收获
动态规划是一个非常重要的知识点，关键就在于最基础的三部，以及多刷题！
|