秋招突击——7/4——复习{}——新作{最长公共子序列、编辑距离、买股票最佳时机、跳跃游戏}

引言

• 昨天主要是面试，然后剩下的时间都是用来对面试中不会的东西进行查漏补缺，顺便和同学聚会。今天继续把算法做了。

• 总觉得自己的进度还是太慢了，项目不整理出来，连简历都没有办法修改，这里得加快一下进度，然后今天除了刷算法，主要是干两件事

  • 整理想去参加的暑期openday，记录在表格中
  • 继续准备项目，并且根据项目完善自己的简历。

• 动态规划基本上已经全部做完了，今天能够最后几题收个尾，练了那么久，基本上都能够做出来。

复习

新作

1143-最长公共子序列

题目链接

注意

• 都是小写英文字母组成==》可以使用ACSCII码进行操作
• 字符串的长度从1到1000==》注意边界条件
• 子序列==》不改变原始序列中字符相对位置的情况下，删除一部分的元素
  • abcde==》ade
• 返回最长公共子序列的长度，没有返回零

个人实现

• 这道题不在之前任何一个模板里面，没什么思路，只能自己使用集合的角度去考虑问题，想想看。

• 单纯使用暴力搜索的算法是怎么做的？

  • 如何提取出一个字符串的子串？每一个字符存在两种情况，加入或者不加入，假设有n个字符，那就是的2的n次方个字串了，这个问题规模太大了。何况是两个字符串
  • 假设能够将两个字符串的所有子串都提取出来，那么再一个一个匹配，就是$2^n$ * $2^n$，然后在比较获取最长的长度，这样问题规模就已经爆炸了。

• 在转换一下，最长的子串，肯定是建立在较短的字符子串上面的

  • 任何一个字符串新增加一个字母，都有可能会改变的最终匹配的字符串的长度
  • 如何从短的字符串过渡到长的字符串？使用什么方法？或者表达式？两个字符串，是不是需要从两个维度进行考虑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
• 时间复杂度：最多是$10^9$，应该会超时，但是可以进行剪枝，先写出来再说
• 使用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的，那道简单题还看错题目了，然后花了很多时间，结果简答的思路都没有考虑到。不过无所谓了，学到了，练习到了，今天又刷了四道题，明天继续加油！