知识点

LeetCode算法题

1. LeetCode算法题

   1. 复习

      1. 1143.【最长公共子序列】

         解题思路：

         两个字符串子序列问题，一定有两个指针在两个字符串上移动。然后利用动态规划思路来解题。

      2. 583.【两个字符串的删除操作】

         解题思路：

         观察删除后的最终结果，发现就是求两个字符串的最长公共子序列，直接用上方解法即可。

      3. 712.【两个字符串的最小ASCII删除和】

         解题思路：

         相当于求公共子序列中，ASCII和最大的公共子序列，变化一下最长公共子序列解法即可。

      4. 647.【回文子串】

         解题思路：

         回文串类型问题都是使用双指针从中心扩散的。

         这个题要注意，避免重复计算回文串。因此使用两个boolean[]，用来标记哪些回文串已经被记录了。

      5. 516.【最长回文子序列】

         解题思路：

         最长、子序列问题，一般都首先思考动态规划。

         回文问题，一般都定义左右两个指针。这就是两个状态。

         然后思考dp[]，dp[]定义。我们定义dp[i][j]为s[i..j]的最长公共子序列长度。

         base case，就是dp[i][j]为1，因为一个字符肯定是最长回文子序列为自身。

         然后思考动态转移方程。该题目很好思考。

         最后，根据base case和动态转移方程思考遍历方式。

      6. 416.【分割等和子集】

         解题思路：

         01背包问题变种，相当于问每个元素只能取一次，问sum(nums) / 2容量的背包能否有一种装法可以装满。

      7. 518.【零钱兑换 II】

         解题思路：

         经典背包问题。