知识点

LeetCode算法题

  1. LeetCode算法题

    1. 复习

      1. 股票买卖系列(穷举+备忘录)

        1. 一次买入卖出

          解题思路:

          穷举思路。

          1、两个for循环,穷举所有买卖可能,然后取差值最大的。

          2、因为两个for相等于,固定buy的天数,然后穷举sell的天数,重复计算很多。因此,更好的穷举思路是:sell的天数肯定是从第1天开始(从第0天计算),因此完全可以通过一个变量存储[0..i]天的最小值,并随着天数更新,这样肯定差值最大。因此一个for循环即可搞定。

        2. 不限次数买入卖出

          解题思路:

          穷举思路:

          因为不限制次数买入卖出,因此先利用一次买入卖出的来推导,发现会有无穷个for循环,因此肯定需要递归函数。递归函数参数为还剩下的天数,函数体中是一次买入卖出的穷举。

          然后,可以利用固定sell来优化为一个for循环。

          其次,穷举+备忘录。

          基于上述的一个for循环的穷举,可以通过一个memo数组来去除重叠子问题(因为天数数组切片可以通过多条递归路径得到,因此有重叠子问题)。

          最后,贪心算法。

          该题目符合贪心条件,用贪心算法是最优解。核心思想就是全局最优解通过局部最优解得到,本题可以理解为:既然可以预知未来,那么能赚一点就赚一点

          贪心算法解法为:

           int process(int[] prices) {
               int res = 0; 
               // 从第1天开始,只要能赚就立刻赚一点,汇总全部就是最优解
               for (int i = 0; i < prices.length; i++) {
                   if (prices[i] > prices[i - 1]
                       res = res + (prices[i] - prices[i - 1]);
               }
          
               return res;
           }
        3. 限制交易次数

          解题思路:

          还是递归函数,不过参数多个k罢了。然后继续使用备忘录剪枝

        4. 含冷冻期

          解题思路:

          还是递归函数,参数还是只有天数数组。不过就是函数体中需要修改一下罢了。

        5. 含手续费

          解题思路:

          还是递归函数,参数还是只有天数数组。不过是利润中减去手续费罢了。

      2. 股票买卖系列(动态规划)

        1. 限制交易次数为k

          解题思路:

          该题目为股票买卖问题中最泛化的形式,通过该题目研究所有股票买卖问题。

          首先,明确状态。状态有3个,天数、是否持有股票、还允许交易的次数。

          然后,明确选择。选择有3个,买入、卖出、不操作。至于买入卖出的顺序等问题,可以先暂时忽略,这里只考虑选择。

          用一个三维数组 dp 就可以装下这几种状态的全部组合,用 for 循环就能完成穷举。

          明确dp数组定义。dp数组表示利润最大值。

          根据状态和选择,找出状态转移方程:因为我们的选择是 buy, sell, rest,而这些选择是和「持有状态」相关的,所以只看状态转移的关键是持有状态。

          dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])

          dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

          最后,明确base case:dp[-1][k][0] = 0; dp[-1][k][1] = -inf; dp[i][0][0] = 0; dp[i][0][1] = -inf

        2. 其他股票买卖

          解题思路:

          根据题意,直接套用上面的状态转移方程和base case

      3. 打家劫舍系列

        1. 基础打家劫舍

        2. 环形打家劫舍

          解题思路:

          第一间房子和最后一间房子也相当于是相邻的,不能同时抢,则有3种情况:1、首尾的都不抢;2、只抢头部;3、只抢尾部,这3种情况中最大的就是答案。

        3. 二叉树打家劫舍

          解题思路:

          还是打家劫舍解法,但是注意二叉树的左右节点都是相邻节点,因此结果为左右的相加。

      4. 1312.【让字符串成为回文串的最少插入次数】