刷题一周总结 2020.12.20 | One Fly Bird's Nest

算法 2020-12-20

递归与回溯对比

来自拉勾《300分钟搞定数据结构与算法》之递归与回溯

顺序	回溯	递归
第一步	判断当前情况是否非法，如果非法就立即返回	判断输入或者状态是否非法，如果非法就报错
第二步	当前情况是否已经满足递归结束条件，如果是就将当前结果保存起来并返回	判断是否满足结束递归的条件。在这一步当中，处理的基本上都是一些推导过程当中所定义的初始情况
第三步	当前情况下，遍历所有可能出现的情况并进行下一步的尝试	将问题的规模缩小，递归调用。在归并排序和快速排序中，我们将问题的规模缩小了一半，而在汉诺塔和解码的例子中，我们将问题的规模缩小了一个
第四步	递归完毕后，立即回溯，回溯的方法就是取消前一步进行的尝试	利用在小规模问题中的答案，结合当前的数据进行整合，得出最终的答案

题目归类

构建最大（最小）字符串（数字）

拼接最大数
 去除重复字母
 移掉K位数字

核心思想

都使用单调递增栈来进行操作并保存最后答案
去掉一个数字后,低位会替代高位。
1. 返回247去掉一个数字后最大的数
2. 答案为47，思路为去掉遇到的第一个a[i-1] < a[i]的数，如果遍历完数组还没遇到就去掉最后一个数
```
if a[i-1] < a[i]:
             del a[i-1] # del速度比pop快
```

判断什么时候出栈入栈很重要

# 出栈
while stack and ord(stack[-1]) > ord(num) and k:

一般时间复杂度和空间复杂度都为O(N)，所有字符最多各进栈出栈一次，空间复杂度为单调递增栈

题解参考

https://leetcode-cn.com/problems/remove-k-digits/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-5/

队列

二叉树的层序遍历

核心思想

用队列，先入先出
如何分层次：
1. 用null来做标记，遇到null时说明一层已遍历完，在队列尾部加上null并cnt+1
2. 一口气把当前层次（队列当前的长度）全都遍历完毕，一边遍历一边把下一层的节点入栈，当前层次遍历完后再进入下一层的全部遍历。
结束的标志：栈为空

栈

有效的括号

简单题
要注意判断最后是否有效的条件：
- 遍历时左右括号不能对应/栈为空就返回False
- 最后的栈是否为空

动态规划/贪心

买卖股票的最佳时机

能买卖1次，贪心
假设前面已经在最低点购买了股票，判断卖出的时机是否为最高点

转移方程为

if (prices[i] < minprice):
    minprice = prices[i]; #更新买入的最低点，确保在前面的最低点购买了股票
elif (prices[i] - minprice > maxprofit):# 判断卖出的时机是否为最高点
    maxprofit = prices[i] - minprice;

买卖股票的最佳时机含手续费

能买卖n次，可以dp也可以贪心
贪心即：当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利

  n = len(prices)
  buy = prices[0] + fee
  profit = 0
  for i in range(1, n):
    if prices[i] + fee < buy:
      buy = prices[i] + fee
      elif prices[i] > buy:
        profit += prices[i] - buy
        buy = prices[i]
        return profit

Dp，需要考虑当前手上持有股票（现在买入，之前就买入），不持有股票两种状态（现在卖出，之前就不持有）。

转移方程：dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]−fee}

dp = [[0, -prices[0]]] + [[0, 0] for _ in range(len(prices) - 1)]
        a1 = 0
        a2 = -prices[0]
        for index in range(1,len(prices)):
            # 转移方程，a1为当前手上不持有股票的最大利润，a2为当前手上持有股票的最大利润
            a1,a2 = max(a1,a2+prices[index]-fee),max(a1-prices[index],a2)
        return a1

最大子序和

和贪婪差不多，子序必须是连续的，如果前面的序列为负数，则去掉。

动态转移方程为：

pre = max(pre + x, x); # 动态转移方程
maxAns = max(maxAns, pre);# 用来保存最后结果，特别是当序列全为负数时，保存的是最大的数

数学题

要找到数学公式

旋转图像

方法1:找公式
1. matrix[row] [col]
  matrix[col] [n−row−1]
  matrix[n−row−1] [n−col−1]
  matrix[n−col−1] [row]
方法2: 利用翻转的特性（旋转=先水平翻转再沿着斜线翻转）
1. 拆解一次旋转的步骤
  matrix[row] [col] = matrix[col] [n−row−1]
  -> matrix[n−row−1] [col]
  -> matrix[col] [n−row−1]
水平翻转的特性：
[x,y] = [n-x-1,y]
沿着对角线翻转的特性：
[x,y] = [y,x]
垂直翻转的特性：
[x,y]=[x,n-y-1]