文章目录
- 引言
- 复习
- 新作
- 1143-最长公共子序列
- 个人实现
- 参考实现
- 编辑距离
- 个人实现
- 参考实现
- 贪心——买股票的最佳时机
- 个人实现
- 参考实现
- 贪心——55-跳跃游戏
- 个人实现
- 参考做法
- 总结
引言
-
昨天主要是面试，然后剩下的时间都是用来对面试中不会的东西进行查漏补缺，顺便和同学聚会。今天继续把算法做了。
-
总觉得自己的进度还是太慢了，项目不整理出来，连简历都没有办法修改，这里得加快一下进度，然后今天除了刷算法，主要是干两件事
- 整理想去参加的暑期openday，记录在表格中
- 继续准备项目，并且根据项目完善自己的简历。
-
动态规划基本上已经全部做完了，今天能够最后几题收个尾，练了那么久，基本上都能够做出来。
复习
新作
1143-最长公共子序列
题目链接
注意
- 都是小写英文字母组成==》可以使用ACSCII码进行操作
- 字符串的长度从1到1000==》注意边界条件
- 子序列==》不改变原始序列中字符相对位置的情况下，删除一部分的元素
- abcde==》ade
- 返回最长公共子序列的长度，没有返回零
个人实现
-
这道题不在之前任何一个模板里面，没什么思路，只能自己使用集合的角度去考虑问题，想想看。
-
单纯使用暴力搜索的算法是怎么做的？
- 如何提取出一个字符串的子串？每一个字符存在两种情况，加入或者不加入，假设有n个字符，那就是的2的n次方个字串了，这个问题规模太大了。何况是两个字符串
- 假设能够将两个字符串的所有子串都提取出来，那么再一个一个匹配，就是 2 n 2^n 2n * 2 n 2^n 2n，然后在比较获取最长的长度，这样问题规模就已经爆炸了。
-
在转换一下，最长的子串，肯定是建立在较短的字符子串上面的
- 任何一个字符串新增加一个字母，都有可能会改变的最终匹配的字符串的长度
- 如何从短的字符串过渡到长的字符串？使用什么方法？或者表达式？两个字符串，是不是需要从两个维度进行考虑f[i][j],分别表示的两个字符串对应到对应索引的位置，然后最长的公共子串长度？但是有一个问题，就是你需要记录的是匹配的字符串长度的索引，然后一旦后续有变化，在往后面的索引继续增加就行了。
具体推导，看是看图吧，如下图，是我自己的推导
- 整理出来了，但是没有使用集合的角度去分析，但是大概的逻辑是对的就行了，先做着吧。时间复杂度就是m*n
class Solution {
public:
int longestCommonSubsequence(string t1, string t2) {
int m = t1 n = t2;
vector<vector<int>> f(t1,f(t2,0));
vector<vector<int>> td1(t1,f(t2,0));
vector<vector<int>> td2(t1,f(t2,0));
// 遍历对应的索引位置
for(int i = 0;i < m;i ++){
for(int j = 0;j < n;j ++){
// 多种情况，分别是仅仅增加i、仅仅增加j或者两者同时增加
if(i) f[i][j] = max(f[i][j],f[i-1][j]+commonSeq(t1.substr(td1[i - 1][j],i),t2.substr(td2[i - 1][j],j)))
if(j) f[i][j] = max(f[i][j],f[i][j-1]+commonSeq(t1.substr(td1[i][j-1],i),t2.substr(td2[i][j-1],j)))
if(i && j)
f[i][j] = max(f[i][j],f[i-1][j-1]+commonSeq(t1.substr(td1[i-1][j-1],i),t2.substr(td2[i-1][j-1],j)))
// 还需要更新最后两者索引相同的最后的索引，方便下次调用。
// 这里得更新两次，不过还是能做的，如果能够写完，还是对的。
}
}
}
};
总结
- 整理思路加上画图，以及最后的写代码，差不多用了半个小时，还是没写完，不过严格按照时间限定出发，没做出来，不过我觉得我的思路大体还是对的。
- 有一个问题
- 单独增加一个和单独增加多个，没有任何意义，因为能够增加多个，就是表示两个数组都没有遍历完，所以还是有问题的。
思路有问题，实现不了
参考实现
- 思路和我分析的还是比较相似的，只不过我有一个问题，就是没有意识到如果相同就加一，不同就不变，然后任何一个状态都是从最初的状态一步一步迭代过来，就像我之前的推理一一样，最基础的这个问题的形态我没有搞清楚。
- 状态当成主要有两个作用
- f[i][j] = f[i - 1][j - 1] + 1这个是表示对应的相同的迭代情况。
- 其余的不变就是， 是为了把状态不断延续下去，这个原理有的时候并不好想，也比较难想，我就是这里没有想出来，确实是一个问题。
疑难解答
- 之前还是有一个问题，就是如何保证，A列表加入一个新元素之后，另外一个列表不增加新的元素，然后新增加的元素会带来更多公共子串
- 不用担心，这里正常每一个字符串都会相互匹配一次，下一次两者 相同的时候，一定会加上这个情况
- 对于那种单个边相加的，只需要考虑上一个状态是怎么计算的就行了。
下面是我参考他的思路写的代码
class Solution {
public:
int longestCommonSubsequence(string t1, string t2) {
int m = t1.size(), n = t2.size();
vector<vector<int>> f(m + 1,vector<int>( n + 1,0));
t1 = " " + t1;
t2 = " " + t2;
// 遍历对应的索引位置
for(int i = 1;i <= m;i ++){
for(int j = 1;j <= n;j ++){
// 这里是单边相加
if(t1[i] != t2[j]) f[i][j] = max(f[i][j-1],f[i-1][j]);
else f[i][j] = f[i - 1][j - 1] + 1;
}
}
return f[m][n];
}
};
- 这里并不知道如何处理索引为0的情况，所以这里在开头增加了一个空格
再参考修改
- 这里使用i- 1来判定是否相等就可，很聪明，跟之前个优先队列的提前试探一样。
class Solution {
public:
int longestCommonSubsequence(string t1, string t2) {
int m = t1.size(), n = t2.size();
vector<vector<int>> f(m + 1,vector<int>( n + 1,0));
// 遍历对应的索引位置
for(int i = 1;i <= m;i ++){
for(int j = 1;j <= n;j ++){
// 这里是单边相加
f[i][j] = max(f[i][j-1],f[i-1][j]);
if(t1[i- 1] == t2[j - 1]) f[i][j] = f[i - 1][j - 1] + 1;
}
}
return f[m][n];
}
};
下面再leetcode上摘抄的一部分矩阵关系变化图很有参考意义
编辑距离
- 题目链接
注意
- 只有三种操作
- 插入一个新的字符==》任何位置插入元素
- 删除原来的字符==》删除任何位置的元素
- 替换对应的字符
- 将一个单词变成另外一个单词的最小操作次数
个人实现
-
首先，如果对这道题的状态限定一下，保证每一个操作之后都有固定的三种操作，就变成一个三叉树，然后进行广度优先遍历深度，是可以解决问题的，但是现在是不限定的每一层的节点数或者分支数，这个是完全没有办法的使用类似的方法。
-
首先，我们先来看看最多操作，也没有一个通用的算法，因为单词的长度的不一样。
- 目标长度单词小于当前的单词，那就先删除，保证长度是一致的，然后在替换，这个是最直接的。
- 目标长度单词大于当前的单词，那就先添加，保证的长度一致的，然后再替换，结果最直接。
-
上述方法很好实现，除此之外，我还需要确定一件事，就是删除元素之后，是否能够保证后续的元素会自动跟上，如果是的话，那么这个问题就变了，删除特定位置的元素，也能够实现单词转换。
-
动态规划，没什么思路，甚至集合都不知道怎么操作，属性表达式倒是很好说明
- f[i][j],把字符串从i变成j，所有的方案各自的步骤数量
- 属性是最小的步骤数
- 状态转换不知道了，不过和上面那道题有点像
下面的方法纯属胡扯了，没有任何必要
class Solution {
public:
int minDistance(string a, string b) {
int m = a.size(),n = b.size();
vector<vector<int>> f(m +1 ,vector<int>(n + 1,0));
for(int i =1;i <= m; i++){
for(int j = 1;j <= n;j ++){
if(a[i-1] == a[j-1])
// 相同的话，删除中间所有的元素
if(i != j) f[i][j] = f[i - 1][j - 1] + abs(i - j);
else
// 不同直接删除
f[i][j] = f[i][j] = f[i - 1][j - 1] + 1;
}
}
return f[m][n];
}
};
忽然间有思路了，想起来了
- 计算最长公共子串的数量len，具有如下的等式关系
- 如果tar == len，直接返回sour - tar
- 如果tar > len,
- sour > tar
- sour < tar
- 如果tar < len,
- sour > tar
- sour < tar
上述几种情况需要好好理理，应该是能够解决这个问题的，但是今天又超过时间了，直接看解答。
参考实现
- 这道题就是属于完全想的不对，但是这种双类型的字符串的，都有一个诀窍，就是两个维度，并且都是从最后的一个元素开始考虑的，而且之前的所有元素，都是已经满足条件的，不要有额外的特殊情况。
- 这里就是假设除了最后一个元素都是匹配的，所以要对最后一个元素进行讨论和考虑，按照顺序执行三种操作即可
- 删除最后一个元素，就能保证两个字符串匹配，所以被删除的字符串的前面的所有字符串都是匹配的，f[i][j] = f[i - 1][j] + 1
- 增加一个新的元素，就能保证最后两个字符串是匹配的，并且添加地元素就是目标的最后一个元素，Bj，所以状态转移就是f[i][j] = f[i ][j- 1] + 1
- 替换掉对应的元素，两个元素都不相等
- 两个元素相等，无操作
实现代码
class Solution {
public:
int minDistance(string a, string b) {
int m = a.size(),n = b.size();
vector<vector<int>> f(m +1 ,vector<int>(n + 1,INT_MAX));
a = " " + a;
b = " " + b;
// 初始化边界条件
for(int i = 0;i <= m;i ++) f[i][0] = i; // 目标字符串是空的，删除操作若干次
for(int i = 1;i <= n;i ++) f[0][i] = i; // 当前字符串是空的，目标字符串的是有长度的，添加若干次
for(int i =1;i <= m; i++){
for(int j = 1;j <= n;j ++){
f[i][j] = min(f[i-1][j],f[i][j-1]) + 1;
int t = a[i] != b[j];
f[i][j] =min(f[i][j], f[i - 1][j - 1] + t);
}
}
return f[m][n];
}
};
总结
- 为什么总是写不出来，我觉得是因为我看问题的角度和他的不一样，他的问题角度是最后一个元素就能保证当前状态完全成立，但是我会被困在中间状态，改变不了，还是改变一下。
- 这里的边界条件处理也很特殊，需要根据实际情况尽心处理。
贪心——买股票的最佳时机
题目链接
注意
- 计算能够获取的最大利润
- 当天买入，然后后续的某一天卖出，计算差价
个人实现
- 这道题就是爽题，单纯是一道状态机模型，是DP，爽题。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> buy(prices.size() + 1,-1e6); // 持有状态：
vector<int> sell(prices.size() + 1,-1e6); // 无持有状态
buy[0] = 0 - prices[0];
sell[0] = 0;
for(int i = 1;i < prices.size();i ++){
buy[i] = max(sell[i -1] - prices[i],buy[i-1]);
sell[i] = max(sell[i - 1],buy[i - 1] + prices[i]);
}
return sell[prices.size()-1];
}
};
给我整麻了，看错题了，这里是只能买入一次，然后卖出一次，不是可以操作多次
- 只能操作一次，那么直接暴力搜索就行了，平方的时间复杂度，会超时，在想想哈.
弄成下面这样，惨不忍睹
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
vector<pair<int,int>> f(prices.size());
for(int i = 0;i < prices.size();i++) {
if(i + 1 < prices.size() && prices[i] == prices[i + 1]) continue;
f.push_back({prices[i],i});
}
sort(f.begin(),f.end(),[](auto a,auto b){
return a.first > b.first;
});
for(int i = 0;i < prices.size();i ++){
if(i + 1 < prices.size() && prices[i] == prices[i + 1]) continue;
// 找到往后小的元素
for(auto x : f)
if(x.second > i ) {
res = max(res,x.first - prices[i]);
break;
}
}
return res;
}
};
参考实现
- 这个思路感觉很清晰，但是我没有想到，感觉就是差点，
- 找到对于第i天的历史最低点，然后计算利润即可。遍历一次是可以记录历史最低点的，然后反复计算对应的利润就行了
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX,maxPrift = 0;
for(int i = 0;i < prices.size();i ++){
if(prices[i] < minPrice) minPrice = prices[i];
else{
maxPrift = max(maxPrift,prices[i] - minPrice);
}
}
return maxPrift;
}
};
贪心——55-跳跃游戏
题目链接
注意
- 一开始位于第一个下标
- 数组的值表示你最多可以跳的次数，你可以选择[0,value]的任意一个数值作为你跳的步骤
- 数组长度边界值为一，可以跳过
- 每一个值可以为零，最大没有越界
个人实现
- 从当前的位置出发能不能到达目标点，直接使用暴力进行搜索可以试试看，遍历所有情况，如果能够找到目标点，就返回true
- 时间复杂度：最多是 1 0 9 10^9 109，应该会超时，但是可以进行剪枝，先写出来再说
- 使用dfs递归实现，具体实现如下
十五分钟写成这样，超时，只能通过一半的样例，不行
class Solution {
public:
bool dfs(vector<int> nums,int idx){
// 等于目标值，直接返回
if(idx == nums.size() - 1) return true;
for(int i = nums[idx];i >= 1;i --){
if(idx + i < nums.size() && dfs(nums,idx + i)) return true;
}
return false;
}
bool canJump(vector<int>& nums) {
if(nums.size() == 1) return true;
if(nums[0] == 0 ) return false;
// 正常情况，第一个数值不为零，并且长度超过了一
return dfs(nums,0);
}
};
可以将问题拆解一下，先拆成到中间某一个节点的情况
是不是思路有问题，不应该使用模拟的方式。发现了，特殊情况时针对0而言的，只要有一个非零的数字，就能够一直往下走，所以按照零进行分段就行。
class Solution {
public:
// 递归调用
bool dfs(vector<int> nums,int idx){
// 等于目标值，直接返回
if(idx == nums.size() - 1) return true;
for(int i = nums[idx];i >= 1;i --){
if(idx + i < nums.size() && dfs(nums,idx + i)) return true;
}
return false;
}
bool canJump(vector<int>& nums) {
if(nums.size() == 1) return true;
if(nums[0] == 0 ) return false;
int dis = 0,sp = 0;
for(int i = 0;i < nums.size() -1;i ++){
if(nums[i] != 0) dis = max(dis,nums[i]);
else{
cout<<i<<sp<<endl;
if(i - sp > dis) {
return dfs(nums,i - 1);
}
else sp = i;
}
}
return true;
}
};
写的这个还是有问题，不伦不类的，将两个都结合了，还有问题，不过我发现，判断还是有问题的，其实不需要看整个，只需要看，零前面的那个数字是多少就行了，能不能盖过零。综合来判定，我的思路没考虑到，时间不够，认输
参考做法
- 这里跟我的思路很想，但是我没有考虑地很周全，是计算每一个点所能够访问的最远距离，如果i超过了能够访问的最远距离，就表示访问不到，直接跳过。
- 最远距离更新方式
- 判定当前的i是否可以访问到
- j = max(i + nums[i],j);
很直观的做法，没考虑到
class Solution {
public:
bool canJump(vector<int>& nums) {
for(int i = 0,j = 0;i < nums.size();i ++){
// i超过了最远距离，不能访问了
if(i > j) return false;
// 没有超过最远距离，需要进行更新
j = max(i + nums[i],j);
}
return true;
}
};
总结
- 今天的进度有点慢了，为什么会这么慢，上午就刷了两道题，是因为什么？中间洗了一下衣服，然后刷了一会视频，不行，还是有点来不及。下午吃饭快点，多留点时间。
- 真的难呀，一天天的，不如开机重启！
- 难受呀，晚上两道题，没有一道题是按时AC的，那道简单题还看错题目了，然后花了很多时间，结果简答的思路都没有考虑到。不过无所谓了，学到了，练习到了，今天又刷了四道题，明天继续加油！
