目录标题
- 让字符串成为回文串的最少插入次数
- 题目
- 题目分析
- 代码
- 题目
- 题目
- 字符子串 （滑动窗口）
- 题目
- 题目分析
- 代码
- 最长连续子序列 （头尾表）
- 题目
- 题目分析
- 代码
让字符串成为回文串的最少插入次数
题目
本题为为LC原题 题目如下
题目分析
这是一道范围尝试模型的动态规划
我们规定dp[i][j]的含义是 让字符串i到j位置成为回文串的最少插入次数
那么假设我们现在要求dp[i][j]的数值我们需要知道什么信息呢？
- dp[i + 1][j]
知道了该位置的插入次数之后我们只需要在前面再插入一个字符就能形成回文字符串了
- dp[i][j-1]
同理
- dp[i+1][j-1]
只有当字符串的i j位置相同的时候我们可以使用这一项 dp[i][j] = dp[i+1][j-1]
代码
class Solution {
public:
int minInsertions(string s) {
if (s.size() == 1) {
return 0;
}
vector<vector<int>> dp(s.size() , vector<int>(s.size() , 0));
int i = 0;
while (i < s.size() - 1) {
if (s[i] == s[i+1]) {
dp[i][i+1] = 0;
} else {
dp[i][i+1] = 1;
}
i++;
}
for (i = s.size() - 3 ; i >=0 ; i--) {
for (int j = i + 2; j < s.size(); j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i+1][j-1];
}else {
int p1 = dp[i+1][j] + 1;
int p2 = dp[i][j-1] + 1;
dp[i][j] = min(p1 , p2);
}
}
}
return dp[0][s.size() - 1];
}
};
题目
列举出一种拼接的可能性 （返回一个字符串）
我们在获得dp表之后 只需要从右上角的位置开始依次递推 就能得出最终的答案
题目
列举出所有拼接的可能性 （返回所有可能的字符串）
我们在获得dp表之后 只需要从右上角位置开始依次递推所有的可能性 就能得出最终的答案 （递归）
字符子串 （滑动窗口）
题目
现在给定一个字符串 str 给定一个目标字符串 aim 现在请问 是否在str字符串中有一个连续的子串m和目标字符串（字符的顺序无所谓）
如果有则返回这个连续子串的初始位置 （如果有多个 则返回第一个即可）
如果没有则返回-1
题目分析
本题是一个很明显的滑动窗口问题 （aim的长度是固定的 在字符串str上从左到右移动）
现在的问题是 我们有没有办法优化该窗口查找的时间复杂度
一般的方法是 我们每形成一个滑动窗口 就让该窗口的字符和aim字符串里面的字符进行比较
那么有没有一种更好的方式呢？
带有这种字符数目的题目 我们就要联想到哈希表
我们可以在哈希表中 统计aim每个字符的个数 在第一次形成窗口的时候让这些字符的个数减去窗口中字符的个数 （可以小于0）
之后我们遍历哈希表 查看是否所有的value都为0即可
代码
int process(string& s1, string& aim) {
unordered_map<char, int> map1;
for (auto x : aim) {
map1[x]++;
}
int L = 0;
int R = aim.size() - 1;
for (int i = L; i <= R; i++) {
if (map1.count(s1[i]) == 1)
{
map1[s1[i]]--;
}
}
for (int i = R + 1; i < s1.size(); i++)
{
int r = 0;
for (auto x : map1) {
if (x.second != 0) {
r = 1;
}
}
if (r == 0) {
return i - aim.size();
}
if (map1.count(s1[L]) == 1)
{
map1[s1[L]]++;
}
L++;
R++;
if (map1.count(s1[R]) == 1)
{
map1[s1[R]]--;
}
}
int r = 0;
for (auto x : map1) {
if (x.second != 0) {
r = 1;
}
}
if (r == 0) {
return s1.size() - aim.size();
}
}
最长连续子序列 （头尾表）
题目
本题为LC原题 题目如下
题目分析
本题其实和 C++ 算法提升二 中的信息流问题解法一样 还要更简单一点
我们要打印的是一个连续的区间 所以说等数据到了之后让其跟我们现在需要的数据对比的方式肯定不可行
那我们想想看 怎么才能让一段数据连续呢？ ---- 单链表
我们可以使用单链表来表示一串连续的数据 但是这里也会出现一个问题
我们怎么保证接收到的数据正好让这一串单链表连接起来呢？
这里提供一种思路
我们创建两章哈希表 头表和尾表
头表 存储一串连续的单链表的头部
尾表 存储一串连续的单链表的尾部
图中的每个数字都代表一个节点 后面其实都有一个指针指向空
假如说现在加入一个四号节点
那么图片就会变成上面这样
但是由于3 4 5本身就是一串连续的字节流 所以说头表尾表就会变成下面的形式
头表中只剩下一个3 尾表中只剩下一个5
假设我们现在想要的第一个数字是2 那么当2来到之后只需要和3 头尾相连 我们打印整个单链表就能得到我们想要的结果了 （当然我们要记得处理下头尾表数据）
代码
struct Node {
int _num;
Node* next; // next指针
Node(int x) {
_num = x;
next = nullptr;
}
};
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, Node*> head;
unordered_map<int, Node*> tail;
unordered_map<int, int> count11;
for (auto x : nums) {
if (count11.count(x) == 0) {
auto* n1 = new Node(x);
head[x] = n1;
tail[x] = n1;
// 查看x是否是某个链表的尾巴
if (tail.count(x - 1) == 1) {
tail[x - 1]->next = n1;
head.erase(x);
tail.erase(x - 1);
}
// 查看x是否是某个链表的头
if (head.count(x + 1) == 1) {
n1->next = head[x + 1];
tail.erase(x);
head.erase(x + 1);
}
count11[x] = 1;
}
}
int ans = 0;
for (auto& x : head) {
auto cur = x.second;
int count = 0;
while (cur) {
cur = cur->next;
count++;
}
ans = max(ans, count);
}
return ans;
}
};
