LeetCode 115 不同的子序列
题目链接：115.不同的子序列
文档讲解：代码随想录
视频讲解：不同的子序列
思路与感想：这道题目跟昨天的判断子序列的一个区别在于如果字符相同那么是可以选择用或者不用当前遍历的字符做匹配的，另一个区别在于上一题实际上是求t是不是s的子序列，而这一题是求s当中有多少种方式能组成t，由此导致了dp含义的不同和初始化的差异，这道题目的dp含义是i-1结尾的s子序列中有多少个j-1结尾的t，那么在初始化的时候就要紧紧围绕这个定义进行初始化。想明白dp[i][0]和dp[0][j]还有dp[0][0]的含义是什么然后进行初始化，至于为什么从这三方面想初始化我们需要先看到递推公式。刚刚提到了这道题和判断子序列的一大区别就在于递推公式上，如果在遍历的s和t的字符相同的情况下，是有两种情况的，s选这个字符和t做匹配那就是dp[i - 1][j - 1]，如果不选那就是dp[i - 1][j]，那如果压根遍历的字符两个就不相同那就做不了匹配自然就回到了dp[i - 1][j]了，最核心的就是搞懂初始化逻辑以及递推公式的两种情况。
收获：1.子序列问题中dp值的含义很大程度影响着你递推公式的情况考虑
class Solution { public int numDistinct(String s, String t) { int[][] dp = new int[s.length() + 1][t.length() + 1]; // i - 1结尾的s的子序列中有多少个j - 1结尾的t for (int i = 0; i < s.length() + 1; i++) { // dp[0][0]表示空字符串s任意删除字符成空字符串t有一种方法，dp[i][0]表示长度i-1的s任意删除字符成空字符串t有一种方法，dp[0][i]表示空字符串s任意删除字符成长度j - 1的t有0种方法，方法数就是对应的dp值 dp[i][0] = 1; } for (int i = 1; i < s.length() + 1; i++) { for (int j = 1; j < t.length() + 1; j++) { if (s.charAt(i - 1) == t.charAt(j - 1)) { // 如果字符相同 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; // 两种情况：dp[i - 1][j - 1]是用s[i - 1]与t[j - 1]做匹配，那剩下的就是用s的前i - 2个字符和t的前j - 2个字符做匹配；而dp[i - 1][j]是不用s[i - 1]与t[j - 1]做匹配，而是用s的前i - 2个字符和t的前j - 1个字符做匹配 } else { // 如果字符不同那就根本没办法用s[i - 1]与t[j - 1]做匹配，只能考虑删除s，不能删除t，因为t是待检验的子序列串 dp[i][j] = dp[i - 1][j]; // 那就只能尝试用s的前i - 2个字符和t的前j - 1个字符做匹配了 } } } return dp[s.length()][t.length()]; } }LeetCode 583 两个字符串的删除操作
题目链接：583.两个字符串的删除操作
文档讲解：代码随想录
视频讲解：两个字符串的删除操作
思路与感想：这道题目花了几分钟就手撕了，可能是感觉来了吧。跟上一题的区别是两个字符串都可以进行删除操作了，然后dp值是最少操作次数，所以在递推公式上和初始化上也有点区别。首先是递推公式，如果遍历的两个字符相同那就不需要进行删除操作，那操作次数即dp值就等于dp[i - 1][j - 1]。但如果两个字符不相同就要考虑是删除word1还是word2还是说都删除，一开始我就想到前两个然后代码过了之后，越看这行代码越不对劲，于是想到了不对劲的原因，我也可以两个都删了，操作数加二啊，可是没有这个情况也过了，想不出原因。后面卡哥对这行代码也进行了解释他说第三种情况dp[i - 1][j - 1] + 2是可以删掉的，因为他其实就等于dp[i - 1][j] + 1或者dp[i][j - 1] + 1，那其实前两种情况就把第三种涵盖了，但是这么想逻辑感觉还是有点奇怪，这个等式成立的前提应该是这个word1的第i -2个字符跟word2的第j -1个字符依旧不相同然后进行删减操作（或者另一种情况）这个等式才成立啊。只能说存疑希望二刷的时候能理解吧，也就不花多余时间了。初始化的话有递推公式可知要初始化第一列和第一行的数据，dp[i][0]明显是把word1进行i此删除操作才能变成空串word2，所以初始化i，那初始化第一行也是这个逻辑，关键是抓住dp含义。卡哥在最后介绍了另一种想法，这道题进行删除后的最终word1和word2相同的部分其实就是它们的最长公共子序列，那么就可以想到等式：删除操作次数 = word1长度 + word2长度 - 2 * 最长公共子序列长度，这样就可以通过求最长公共子序列长度变相求删除操作次数了，这样代码部分就跟那道最长公共子序列一模一样的，最终返回这个等式即可。
收获：1.两个字符都进行删除操作的递推逻辑
class Solution { public int minDistance(String word1, String word2) { int[][] dp = new int[word1.length() + 1][word2.length() + 1]; // dp[i][j]含义：以word1[i - 1]结尾的word1和以word2[j - 1]结尾的word2进行删除操作实现两个字符串相同的最小步数 for (int i = 1; i < word1.length() + 1; i++) { dp[i][0] = i; // 长度为i的word1进行删除操作需要i步可以成为空串与word2相同 } for (int j = 1; j < word2.length() + 1; j++) { dp[0][j] = j; // 同上 } for (int i = 1; i < word1.length() + 1; i++) { for (int j = 1; j < word2.length() + 1; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { // 如果遍历的字符相同那就不需要进行删除操作，直接进行匹配，步数dp值就延续dp[i - 1][j - 1] dp[i][j] = dp[i - 1][j - 1]; } else { // 如果不同那就得选个字符word1或word2的进行删除，当前dp[i][j]即步数需要在其基础上加一。没必要都删除因为这样相当于dp[i - 1][j - 1]，反而会因此多两步肯定比dp[i - 1][j - 1]更大了 dp[i][j] = Math.min(dp[i - 1][j] + 1,dp[i][j - 1] + 1); } } } return dp[word1.length()][word2.length()]; } }LeetCode 72 编辑距离
题目链接：72.编辑距离
文档讲解：代码随想录
视频讲解：编辑距离
思路与感想：这道题目确实按卡哥所说，前面的所有子序列问题似乎都在为这一刻做铺垫。一步一步，难度逐渐增大。但是因为有了这种循序渐进的刷题策略，这道题很轻易就手撕了。这道题相较于上一题的区别在于，除了删除操作，它可以进行增加或者替换操作实现两个字符串最终相同，看上去挺唬人的，但是这个增加操作其实可以理解为一个字符串进行增加操作，那么另一个字符串进行删除操作也可以达到同样效果，操作次数也是一样的，所以可以把增加操作当删除操作，而替换操作则可以理解成当前遍历的两个字符串字符是匹配的，但这是建立在我们对当前遍历的某个字符进行替换而实现的，所以要在dp[i - 1][j - 1]基础上加一。收获：1.学会对陌生的操作转换成熟悉的操作
class Solution { public int minDistance(String word1, String word2) { int[][] dp = new int[word1.length() + 1][word2.length() + 1]; for (int i = 0; i < word1.length() + 1; i++) { dp[i][0] = i; } for (int j = 0; j < word2.length() + 1; j++) { dp[0][j] = j; } for (int i = 1; i < word1.length() + 1; i++) { for (int j = 1; j < word2.length() + 1; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(dp[i - 1][j - 1] + 1,Math.min(dp[i - 1][j] + 1,dp[i][j - 1] + 1)); // 一个字符串的增加操作等于另一个字符串的删除操作，实现同样的效果。所以可以都看作是删除。替换操作可以看作遍历的字符是相同的所以可以进行匹配，但这样的效果是我们把其中某个字符进行替换操作后实现的，所以在此基础上要加一 } } } return dp[word1.length()][word2.length()]; } }最近感觉左肩的中枢有些不适，平常来说左右一般组数我都设置的一样的，今天左边做到七八十的时候就会感觉到很疲惫，需要好好休息一下了。今天算法花了大概四个半小时加上早上补昨天进度十个小时是有的。等算法强度下来了得每天分配两三个小时在八股上了，主要就是JUC、MySQL和Redis，之前都是随着性子有时候在课上写不了代码就刷刷完全没有计划，这一点必须得改改了。慢慢沉淀吧哎呀，明年暑期大二下争取找个中大厂的日常实习，疯狂产出，大三上学期好好整理下沉淀再优化下简历，等到寒假争取找个大厂日常实习，拼命汲取实际开发经验，大三下学期高强度准备八股针对性突击算法然后冲击大厂的转正实习了，争取到机会了就好好表现争取转正，有个保底再去秋招试试能不能拿到其他大厂的offer，选择多了也就有了谈薪资的底气，秋招结束也许就有了gap的时间，到那时好好学学吉他，备考N1和雅思，不知道有没有时间，总之做一些技术之外其他感兴趣的事物吧。不过计划终究是计划，之前的我总希望别人给我个确定的答案，说哎呀你这么拼肯定能进大厂的呀，你这条学习路径是对的哦，你这么计划很合理很高效啊，后端这个方向肯定没问题的，技术岗肯定不错的呀。。。。后面发现大多数人并不愿意给我一个肯定的答复，我也从他们的沉默中明白了他们给不了一个肯定的答复，不是他们不愿意而是他们也不知道未来会怎么样，后面我也越来越少问这种有些尴尬的问题了。说到底只是为了寻求一个安慰罢了。我们并不是在考研考公就业里拼杀的敌人，而是在这个时代里相互搀扶的普通人。
