LeetCode刷题笔记（二）

每期10题，上一期参见LeetCode刷题笔记（一）。

本期内容多以List操作和动态规划为主，同时针对链表内容结合上篇笔记进行了整理。

---

链表

147. 对【链表】进行插入排序

每次取出一个待排序元素

然后将它放入已经排好的序列的合适位置【升序排列，可能有负数】

关键是怎么样进行排序，从动画来看是从末尾开始进行比较，直到当前数的大小合适就可以放入了

python中的这个链表很有意思，感受一下：

## 原始定义
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

假如说一个 链表 head

其内容看似是 [4, 2, 1, 3]

但是实际调用应该是 head.val = 4 头部的第一个数

那么第二个数就应该是 head.next.val = 2

所以就要对 head.next 进行迭代，使用的都是同样的方法

问题：

• 那么怎么产生一个ListNode，继承父类吗，如何进行实例化
• 可以向后推演，如何向前呢？就是当前数字的前一个是什么【找不到，因此，要从前往后地找插入点】

总体推演

• 每一个循环应该是head向后移动一位
• 此时在新的listnode中也会从头开始进行比较，什么时候停
  • 第一是比当前的值大了一点
  • 第二是个数够了
    • 比如当前是第 k 轮，最多只能 k-1 次比较
    • 那么当比较的次数是 k 时，就要退出比较的部分，还要将 k 归0，以便下一次是从头开始进行比较
    • 那么下一轮 的轮数也要进行变化，这样就会出现两个参数了

时间复杂度问题

• 只需要更新相邻节点的指针，时间复杂度 O(1)
• 但是需要进行遍历链表的节点，时间复杂度 O(n)
• 总的时间复杂度就是 $O(n^2)$

【11月21日】想法

（1）对比head 和head.next，如果head大，就要交换一下

（2）移动head【如果**==移动==**的话，是不是还需要一个东西来存储一下】

所以说，应该是在一个链表上，自己和自己进行比较，交换数字容易，但是移动到下一个数字应该怎么做

还是复制成两个链表进行比较？

【阅读题解】

发现不只是两个链表了，而是要新建几个链表用来放置数据

阅读题解

重点的几个内容：

1. 链表前的节点 —— 哑节点 —— 便于在head前插入节点zeroHead.next = head
2. **已排序部分的最后一个节点 ** lastSorted = head
3. 待插入元素 current = head.next
4. 插入元素的位置的前一个节点 prev

然后的思路和上面的分析其实很像

怎么样将 current插入到链表中呢？

几种情况

1. 空的链表
2. 比较lastSorted.val和current.val的值，发现不用变化
3. 第2步比较之后发现确实需要进行变化：

lastSorted.next = current.next # 相当于把 lastSorted 向后移动了一位
current.next = prev.next # 相当于把排序的那个链表断开，从 prev 这里断开
prev.next = current	# 然后把 current放在了 prev 的后面

current = lastSorted.next # 更新将要插入的值

然后是判断的条件：

• 计数是不太明智的方法
• 其实从上面的分析可以看出，current才是最直接从head复制出来的东西，直接判断current是不是空的，就能终止程序

可以直接判断链表是不是空的：while curr: 如果是空的就会直接跳出

链表的恼火之处在于不断地覆盖

• 每次取出来一个值的时候，是ta后面的一长串全部都被取出了
• 如果只想改变这一个值，就要精准地覆盖这个值后面的链表，用不同的东西覆盖得到的效果就是不同的

链表的神奇之处在于消失

• 其实你并没有把一个值赋值到链表当中
• 而是把它添加到了前一个元素的next中，又把ta的next全部改成了原来的元素，这样，其实你根本没有对这个值进行操作，一个新链表已经形成了，就好像这个元素消失了一样

几个基本操作：

• 把链表自己移动一位：list_node = list_node.next
• 把链表 head 的头换成另一个数字：head.val = xxx 固然是可以的
• 在链表前面添加另一个链表：another_list_node.next = list_node
• 在链表 head 的头后插入一个新的数字（其格式应该也是链表）：curr.next = head.next; head.next = curr【也就是先要复制后面的内容，然后再把这些内容加到head 的后面】
• 遍历链表：while head.next.val <= curr.val: prev = prev.next

链表总是最大限度地发挥next的作用

---

动态规划

LCP 19. 秋叶收藏集

本题的好处是：替换，而不是交换，这样数学过程会简单一点

现在主要考虑的就是，黄叶是不是在一起，左右是不是有红叶，感觉是动态规划

3片叶子：

• 找黄色的
  • 如果没有，直接换中间的， 换一次
  • 如果开头，要换两次
  • 如果结尾，换两次
  • 如果全是黄叶，换两次
  • 如果两片黄叶在一块，换一次
  • 两片黄叶分开，换三次

有很多叶子

• 找黄色的，标记为1
• 加和？还是找到它的位置？
• 看有没有断开？
  • 取首项索引，末项索引
  • 中间各项进行检测
  • 但是这样不见得是最好的方式

【10月1日思路】按照数量来决定换还是不换

首先找出黄叶的位置（索引）

python字符串中查找的方法有四种：

• find()，返回找到的第一个字符的索引，找不到返回 -1
• index()，返回找到的第一个字符的索引，找不到报错
• rfind()和rindex()是倒着找

如果是列表，那么是

• list.index 也是找第一个匹配项的索引
• 用enumerate函数

numpy可以找指定元素的索引

• np.argwhere

Python从列表中找出所有元素索引的几种方法

python找出一个列表中相同元素的多个索引

Python3 返回字符串中某个给定字符的全部索引

matlab中对矩阵直接判断：A>a，就能得到同样大小的矩阵，但是python似乎不可以

• 取首末索引，计算中间段数量
• 计算出黄叶数量

中间段有没有红

• 有
  • 有多少红叶
    • 红叶比黄叶多，换黄叶
    • 红叶比黄叶少，换红叶
    • 有一些情况，比如yrrrryyyy，这要怎么换，肯定是只换第一个黄叶最好

特殊情况

• 全是红叶，换一次
• 全是黄叶，换两次
• 首尾是黄叶，各处要换一次

我做题总有一种被套住的感觉

被带入到了题目中，而没有跳出来

这个问题相当于是在分段，把集中的部分放在一起，怎么样来判断集中和零散？

• 一种方法是首尾判断，然后确定中间是不是掺杂，掺杂则是零散，不掺杂则是集中
• 但是掺多掺少也是问题

我掌握的计数方法过少了，只有循环计数

阅读题解

动态规划

分为三种状态：然后分析需要将某一片叶子变色时，当前这片叶子和之前的叶子共同作用的情况，而且需要把次数传递下去

python中的float("inf")表示正无穷，float("-inf")表示负无穷，可以做简单加、乘算术运算，当然结果还是inf

从公式角度来说，如果用$f[i][j]$ 表示对前 i 片叶子进行操作的次数，而且当前的第 i 片叶子处于状态 j。

j 有三种：0 表示前面的红色，1 表示黄色部分，2表示后面的红色部分

• j = 0， 第 i 片叶子需要变成红色时，i 之前的叶子都是 j = 0 的状态

  $f[i][0]=f[i-1][0]+isYellow(i)$

  如果是黄色，才会增加变换的次数

• j = 1，需要把第 i 片叶子变成黄色，i 之前的叶子可以是 j = 0，也可以是 j = 1

  $f[i][1]=min{f[i-1][0], f[i-1][1]}+isRed(i)$

  如果是红色，才会增加变换的次数

• j = 2，需要把第 i 片叶子变成红色，i 之前的叶子可以是 j = 1或2

  $f[i][2]=min{f[i-1][1], f[i-1][2]} + isYellow(i)$

  如果是黄色，才会增加变换的次数

但是问题有

• 什么时候改变状态呢？
  • 从代码来看，其实并没有改变状态
  • 不同状态的值一直存在，只不过看选用那个状态罢了
  • 好比说，刚开始是一片红叶，isRed(i) 会是1，这样 $f[i][1]$ 就有值了，但是等到下一次循环时，选择的是最小的那个，也就是 $f[i][0]$，而不会选择有值的这个，所以，并不影响
  • 直到出现一篇黄叶，局势才会变化
  • 可以自己做推演，这个方法确实很妙
• 此外，叶子的数量必须是大于状态数量的，所以像$ f_{01}, f_{02}, f_{12}$ 其实是不存在的
• 初始值 $f_{00}$ 也是要考虑一下的

学习： f = [[0, 0, 0] for _ in range(n)]

这句是把 f 变成了一个n行3列的全零数组，便于后面的计算

最后，注意两个问题：

• range(1, n)，必须是从1开始，因为00已经在前面初始化了
• i >= 2，要包括2，不然就会失败了

70. 爬楼梯【经典&基础】

n阶楼梯，每次可以爬1或2级台阶，问：爬完的方法有多少种

【仅作为数学问题】

n阶台阶，最多n步（1种）

然后减少步数，少一步=一个2级台阶（n-1步，n-1种）

少两步=2个二级台阶（n-2步，$C_{n-2}^2$）

······

最少也要 n/2 步（1种）

• 如果 n 是偶数，最少 n/2
• 如果 n 是奇数，最少 n+1/2
• 不管 n 是奇数还是偶数，统统加1，然后除以2取整就好了

次少要加1步（$C_{\frac{n}{2}+1}^1$）

所以总共就是

偶数：$S_o(n)=C_n^0+C_{n-1}^1+C_{n-2}^2+···+C_{\frac{n}{2}+1}^1+C_{\frac{n}{2}}^0$【这里面的数字都是整数吗？确实都是吧】

奇数：$S_j(n)=n+S_o(n-1)$【其实奇数的时候，少不了有1步代替不了，直接拎出来，剩下就是整数问题了】

下来是计算问题

• 传统方法是阶乘，复杂度爆炸了，不可以
• 巧妙一点的方法，有没给有简单一点的级数？
• 或者能不能进行转化【可能还是要回到动态规划】

【动态规划怎么做】

假设已经爬了 k级，i步，还有j=n-k级

• 下一步爬1级，k+1级，i+1步，还剩j-1级
• 下一步爬2级，k+2级，i+1步，还剩j-2级

像一个二叉树，但是一直这样开枝散叶下去不是太妙，感觉复杂度会比较高

动态规划问题的基本思路

联系方程：例如本题，$f(x)=f(x-1)+f(x-2)$

转移方程：

边界条件：f(0)=0【定义】, f(1)=0【实际】

…到这里，再看上面的方程，这已经成为一个很基本的数学问题了

（1）不断进行滑动就可以实现了【不过这样的复杂度为什么是$O(1)$而不是$O(n)$】确实，时间复杂度是O(n)，空间复杂度是O(1)

（2）使用矩阵的方法

$\left[\begin{matrix} f(n+1) \f(n)\end{matrix}\right]=\left[\begin{matrix}1 & 1\1 &0\end{matrix}\right]\left[\begin{matrix}f(n)\f(n-1)\end{matrix}\right]$

那么就是要求矩阵的n次方了

（3）上面的递归方程其实可以用特征方程的方式求解通项公式，当然这个感觉会稍微有一点难

总结：

本题形成的序列是斐波那契数列。！！所以就是求斐波那契数列了！

• n比较小，可以用递归法，不做记忆化操作
• 一般情况下用转移方程，递推、递归、滚动数组
• n不断扩大时，需要使用矩阵快速幂的方法
• 也可以直接使用斐波那契数列的通项公式计算

使用python使用方法（1）进行解题

需要有个东西记录数字

终止条件是什么？f(n)是要求的数字，n是台阶的数量

class Solution:
    def climbStairs(self, n: int) -> int: 
        a, b = 1, 1 # f(0), f(1)
        c = a + b   # f(2)
        times = 2   # 2
        if n == 1:
            return 1
        while times < n:
            a, b = b, c
            c = a + b   # f(times+1)
            times += 1
        return c

这里刚开始用的是for循环，最后改成了while

for 不能这么用，for的话这是for i in range···

53. 最大子序和

输入：整数数组

操作：找一个连续子数组（至少一个元素，重点是连续）

输出：最大和

从给的例子来看：

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

并不是遇到负数就断了

而是如果负数将这个序列和归0了，甚至是变为负数了，那么这个子序列就中断了

也不是要从头加到尾

比如开头的负数就不要了

几个特例：

（1）[1]

只有一个元素，而且是正数

（2）[-1]

只有一个元素，而且是负数

（3）[-2, -1]

两个都是负数

我的算法为什么会遇到上述问题：

• 首先是起始项，如果选择0，那么会对全负数不友好
• 如果选择nums[0]，也就是第一个数

我其实并没有用动态规划，而是用了一种存储的方法：

（1）当前值是正还是负，主要看负的情况：

如果当前是负的，那么比较当前值和过去sum的大小：

如果当前值稍大，那就记录当前值，如果过去值稍大，那就记录过去值

（2）如果当前是正的，就要考虑过去值还需不需要了

如果过去值sum是负的，那就不用加了，直接重新开始

其他情况，都直接往sum上加就好了

所以：

• 更新开头有两种方式
  • sum < 0，i > 0
  • sum < i < 0
  • 总结就是 sum < 0，sum < i
• 遇到负数也会加，只是要把本次加负数之前的数字保存下来

阅读题解

==妙蛙种子吃了妙脆角到了米奇妙妙屋，妙到家了==

这里讲的第一种方法是动态规划的方法：

每一步，我们计算到该位置的最大子序和$f(i)=max{f(i-1)+a_i, a_i}$

站的角度不同，我是考虑“要不要把当前的值加入 过去的序列 sum中”

而这个方法则是观察每一个位置的最大子序和 ，考虑的是 “前面的子序和对我当前数值有没有用”

198. 打家劫舍

输入：非负整数数组

输出：从数组中取出最大数字和的子串，要求，数字之间不能相邻

这个题感觉很有意思啊

钱的数量：f(n)，应该叫 到第n个数值，最多的钱数

• n 表示当前字符串的长度

只有两种可能：没有取当前的数字，那就等于 f(n-1)；如果取了当前的数值，那就等于跳过了一个数值 f(n-2)+i，把这两种情况比较一下，就是当前位置应该的情况

f(n) = max( f(n-2) + i, f(n-1))

初始条件：

• f(0)=0
• f(1)=i
• f(2)=max(f(0)+i, f(1))

==喜极而泣！！！==

这是我第一次用动态规划的方法完成了解题！！！

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return sum(nums)
        max_sum = []
        max_sum.append(0)
        max_sum.append(nums[0])
        for i in range(2, len(nums)+1):
            max_sum.append(max(max_sum[i-1], max_sum[i-2] + nums[i-1]))
        return max_sum[-1]

非常完美，一次过！

---

List操作

977. 有序数组的平方

定性：python排序问题

给定一个非递减顺序排序的整数数组A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

这个题思考一种方法还是比较简单的：

• 看绝对值，绝对值进行排序
• 然后平方

已经是非递减顺序了

主要问题是有可能出现两个一样的数字

还有就是绝对值一样的

列表的排序

list.sort() list 本身会被修改

sorted(list) list 本身不会被修改

思考其他的思路：

如果能找到负数和非负数的分界线

就可以进行“归并排序”：

• 两个指针分别移动，选择小的那个放入其中

再进一步，我们甚至不需要知道分界点在哪里，就从头和尾两端开始对比，哪个大就放在列表中，是最后一项

这样也是可以的

list 中进行添加元素

• append 在末尾添加一个
• extend 在列表末尾一次性追加另一个序列中的多个值

463. 岛屿的周长

输入：一个矩阵，只由0和1构成，大小不定【宽和高不会超过100】

计算：0和1的接触称为边界，计算这些边界的总数

在一行中，当 1 开始，就有 1 个横向边界，也会有一个 横向出的边界，也就是穿越法，穿过几次

在一列中，从1开始进入边界，然后穿越边界

所以关键就是检查是不是连续的？这样的计算方法感觉反而要困难一点

从大的方向来说，分两次进行计算：

1. 横向遍历一遍
2. 纵向遍历一遍

在每一次计算的过程中，进入1则＋1，出1的区域则+1

python中关于二维list的遍历？

只能使用二维索引？那复杂度有点高了

或者还有一个方法：

找出所有的1，然后观察周围的元素，如果有0，加个1，那就是计算周围四个元素的和，然后用4减一下，这个方法可以

349. 两个数组的交集

给定两个数组，用函数计算交集

一个方法：

先找出比较短的那个数组，

然后针对该数组中的每一个数字，

在另一个数组中找一下有没有，

有的话加入交集数组，

最后输出交集数组。

还有更快的方法吗？

有，两个元组可以使用 &直接得到交集

然后再使用list进行转化

前面两个之所以为元组，是因为两边都用set进行了去重

这个方法确实是可以的，但是问题在于没有办法去重，

为了去重，在计算出比较短的那个数组后，需要首先去一下重，可以使用set(list)，该函数会返回去重后的结果，值得注意的是转化为了元组，但是仍然可以使用for循环进行索引

402. 移掉k位数字

给定一个以字符串表示的非负整数num：比如“1432219”

移除其中的k个数字：比如k=3，可以移除4，3，2

使得剩下的数字最小：按上面的移除方式，最后剩下的就是1219，最小

发现：

• 仅仅是去除，不改变顺序
• 如果用排列的方法，但n比较大或者k比较小的时候是比较难的

发现规律：

• 如果当前数字比左侧的大，就要删去
  • 【不对，如果129，k=1，显然删9更小，但很有可能会把2删掉】
  • 【其二，如果左边的数字大，更应该删除左边的数字，因为它让整个数字更大了】
  • 所以官方给出的办法是找比左边数字小的数字，然后把左边的数字删掉，单调不降删最后一个就可以了
• 如果当前数字是0，就要删去左边的数字【此时，索引值要跳到一个不是0的位置，左边的数字也会跳】

涉及两个步骤：

• 第一，找出数字的位置
• 第二，把数字去掉【怎么样更快速地去掉那一位上的数字了，而且0也要去掉】

列表转字符串用join方法：

"".join(list)也就是使用没有字符的方法合并list中的数值

阅读题解

官方题解的解释我觉得是很不错的

其主要思路就是：

• 如果当前数字比左边的小，那么就要删除左边的数字【这说明，我发现的规律还是不够严谨】

需要处理的细节问题是：

• 如果整列遍历完，单调不降，那么就要删除最后一个

退出条件：

• 整个数列已经是空的了
• 新的栈顶元素不大于当前数字【注意这里的栈中，栈顶是队尾，栈底是队首】
• 或者已经删除了k个数字

额外情况：

• 如果删除的数量不足，那么就要从最后面开始删
• 前导0的问题，要删掉前导0
• 如果最终数字序列为空，返回0

一个高赞题解的思路：

大致上是一致的，不过又增加了一点东西：

从丢弃和保留两个方面入手

• 也就是说先按照我们的原理丢弃一遍
• 然后再把丢弃完毕后的list再保留我们需要的位数
• 【这个保留操作确实是一个考验，就是说我们不能直接使用原来的list减去应该去除的数量，而是需要把字符串也给改掉】

人家的方法确实是不错：

• 首先用 for 循环遍历 num 中的每一个数字【我则是用index的方式进行平移】
• 然后使用 while 进行判断，也就是实现一个不断进行删除的操作【这样就避免了嵌套或者是递归的问题】
• 最后是活用 pop 和 append 的问题【一个减，一个加，来回推拉】
• 针对全部都删除的特殊情况，使用一个or 【字符串的or操作？】

我觉得这个方法里面最好的一点是：

• 充分考虑到每一个数字被遍历了【for循环】
• 对每一个数字的操作，都操作到底，又兼顾条件【while循环】
• 向空列表中推拉数据，形成新的数据

在python中使用栈的结构：

• 其实就是list列表
• list.pop() 用于移除列表中的一个元素（默认最后一个元素）
  • 输入可以是index：list.pop(-1)，可以没有参数
  • 输出，返回的是该元素的值
• 再用list.append()向列表中添加元素
• 还有str.lstrip(chars)，用于截掉字符串左边的空格或指定字符

字符串之间使用or

• 两侧非空则取左
• 有非空则取另一侧

参考：字符串的and和or操作

我用了一种偷懒的方式，希望把原来的代码稍加修改就能实现新的目标，但是这样是很错误的，例如：1234567890，如果按照我的代码，首先会去除9，然后保留len(num)-k个数字，那就会删除9个数字，最后剩下的是 1 ，而不是 0

第一版代码：

# 冗长而不能解
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        left_num_idx = 0
        index = 1
        del_num = 0
        del_num_idx = []
        # 去除操作
        while del_num != k and index < len(num):
            print(num[index])
            if num[index] < num[left_num_idx]:
                del_num += 1
                del_num_idx.append(left_num_idx)
                left_num_idx = index
            else:
                left_num_idx = index
            index += 1

        new_num = []
        for i in range(len(num)):
            if i not in del_num_idx:
                new_num.append(num[i])
        new_num_str = "".join(new_num)

        # 保留操作，避免去除的数量不够
        new_num_str = new_num_str[:len(num)-k].lstrip('0')

        if not len(new_num_str):
            new_num_str = '0'
        return new_num_str

新的代码思路：

• 要删除左侧较大的数字，而且一直要删到小于等于它为止
• 能不能首先将数据变成一个可以进行方便删改的数据形式——比如list，按照索引进行删改确实要比str要方便的多

删除的原则：

• 左侧比当前的数字大

那么以下几个问题：

• 左侧没有了
• 怎么跳出删除

新的代码基本是照搬高赞代码：

class Solution(object):
    def removeKdigits(self, num, k):
        stack = []
        remain = len(num) - k
        for digit in num:
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        return ''.join(stack[:remain]).lstrip('0') or '0'

121. 买卖股票的最佳时机

输入：一个数组【股票场景，第i个数字表示股票第i天价格】

输出：数组中后面数字减前面的数字，能减出的最大差值【股票场景，最多一笔交易，计算获取的最大利润】

给一个位置记录最大值，如果出现更大的最大值，更新记录

给一个位置记录最小值，如果出现更小的最小值，最小值重新记录，最大值也重新记录？【也不对，万一后面并没有更大值了就不行了】

给一个位置记录利润，当每次需要更新最小值的时候，就会刷新一下利润；循环结束之后也需要刷新一下利润

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        maxPrice = prices[0]
        minPrice = prices[0]
        profit = []
        profit.append(maxPrice - minPrice)
        n = 1
        while n < len(prices):
            if prices[n] < minPrice:
                profit.append(maxPrice - minPrice)
                minPrice = prices[n]
                maxPrice = prices[n]
                # print(profit)
            elif prices[n] > maxPrice:
                maxPrice = prices[n]
            n += 1
        profit.append(maxPrice - minPrice)
        # print(profit)
        return max(profit)

看上去这个代码好像是可以了

但是，题目是真的狠，输入是10000到0倒着数，而且还写了好多0

最后还是可以通过的，就是不要print！！！

阅读题解

官方题解的第二种理解，文字似乎有点问题，仔细看代码，其实和我的方法几乎是一样的原理

但是官方题解没有用list去记录，而是巧妙使用max，min进行比较

---

OK！本期10题就先到这里了，期待下一个10题快点到来！