LeetCode刷题笔记（四）

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

本期内容动态规划内容出现复习情况，数组内容略有新意，图理论和拓扑排列初步入门。

数组和排序

1046. 最后一块石头的重量 - 排序问题

输入：整数数组（不会超过30个数字，1到1000之间）

输出：特定 int 值

每次运算：选出两个最大数字，返回差值（如果是0就不用返回），直到只剩下0个或1个数值，无法比较，返回该数字

（1）暴力解法

每次需要找最大的两个数字，这一步的时间和空间复杂度就已经比较高了$O(n^2)$，然后再相减，加入到新的序列中，其实还可以接受

对呀，这个问题：怎么给一个list排序（如果不使用现成的库）

首先：需要对比所有数字，确定是最大的，第二大那就排除第一个再对比一遍，做差

然后：把差值和所有数字对比，放在合适的位置（重排位置确实是用链表更好一点，但是如果执意要用列表呢，就需要拆一下再合并了）

这个方法确实是过于复杂

（2）差值，有什么规律？

简单一点，如果是1-10递增，那么每次相减都是1，连续四次之后，多了4个1，还剩1和2，然后5个1，可以预见最后有个1

如果2，4，6，8，那么2，4，2，然后2，2，然后0

这题好像确实也没有什么太多的方法就是按方法排好序就好了！

相当于本题的核心目的就是实现排序！！

排序的关键是找到数字在列表中的位置。

如果需要排列一个从大到小的数列，那么就应该比较当前数字是不是比已有序列中的数字大

所以我最后的步骤是：

（1）先写一个独立函数，在已经排好顺序的序列中找到当前元素应该放置的位置，放进去

（2）对原始序列进行一次排序（分两步）

• 遍历原序列，移位
• 把原序列中的当前数值放到新序列该放的位置上

（3）不停做差值，把差值放到序列中

看题解，很多用了sort

我没有用sort，除了一些list的用法，几乎是完全自主的

605. 种花问题

输入：整数数组 flowered（只有0和1），整数 n

输入：布尔量

功能：向数组中添加n个1，要求这些1不能相邻，如果能做到，返回true，做不到，返回false

限制：数组长度在1到20000之间，n非负，不会超过数组大小；按照题目的意思来看，已经是1的位置应该是不能被替换

思路：

这首先是回答能不能，而不是回答怎么做，所以更像一个数学问题：

如果当前数组中全部是在奇数位置，那么非常简单，计算有多少个奇数位置

比较糟糕的是有的在奇数位置，有的在偶数位置，这样在非常紧密地排列时少不了要相遇，会少一

怎么检查现有数值的位置？

另一个思路：

两个1之间有多少个0：

（1）奇数个0，直接减1除以2

（2）偶数个0，直接减2除以2

特殊情况，头部为0，偶数不用减2

尾部为0，偶数不用减2

头部的确需要考虑，那么当遇到1了，就直接表示头部过了就可以了

但是尾部其实不用考虑，会跳出的

现在遇到一个问题：[0] 的情况，那么这个应该是可以种植1个，但是按之前的计数方法是不可以的

所以最终方法是：

（1）全0的数组，直接加1除以2，比较就好了

（2）开头为0，设置一个start的flag，遇到1就会转换，并计算开头情况

（3）逐步前进，遇到1重置，计算中间的数量

（4）来到末尾，根据最后一个数值是1还是0做最后叠加

（5）最后判断输出即可

这个用时非常Amazing！

303 区域和检索 - 数组不可变

这道题我一开始有点懵逼

题目的意思是完成一个class的编写，该类的初始函数需要完成的是实例化类（传递列表）

另一个函数则是用来计算该数列第i个到第j个的总和

那么我直接用sum就计算好了

确实就这么完成了，但是问题当然是：这样相当于比如要计算多个总和的时候，就要一个一个计算了，是不是显得有一点冗余？

那还应该怎么做？

阅读题解

其实关键问题就是上面说的，每次计算一次总和，肯定是重复了，这样是不好的

比较省心的方法就是：

计算到第i步的总和$f_i$，第j步的总和$f_j$，最后结果等于$f_j-f_i$

而且$f_{i+1}=f_i+x_{i+1}$，这样的话就能避免循环，节省时间，确实是一种好方法

但是我写完之后遇到一些小问题：

（1）如果是从0到2的序列，那么$f_0$应该是0的，但是按以往的方法却不是的

• 看到题解中有一种巧妙的方法：sums = [0, ]
• 然后把每次计算好的 新的sums值 append 在后面：nums.append(self.num_sum[i]+nums[i])

（2）关于 序列为空（NoneArray）的问题，如果是空的序列，计算长度 len 函数（n = len(nums)）是会出问题的！【我刚才的问题可能是返回了0，而没有返回None】

• 但是奇怪的是，在 for 循环中使用 for i in range(len(nums)) 即使nums是空的也没有问题

剑指offer 03. 数组中重复的数值

输入：整数数组

输出：数组中的某个数值

要求：该数值一定是在数组中重复出现过的

老办法：计算所有数字出现过的次数，然后>2的都可以输出

代码：

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        sort = [0] * (max(nums)+1)
        for i in nums:
            sort[i] += 1
        return sort.index(max(sort))

也的确可以通过，但是这种方法不太好

有没有其他减少复杂度的方法，比如先排个序？不行，并不能保证重复的数字出现在某个位置

阅读题解

（1）遍历数组

这个方法告诉我们，根本就不用遍历完，只需要遇到重复的数字立马返回

当然新的数字需要加入到一个新的集合中，然后判断下一个数字是新数字还是已经遇到的数字

（2）原地交换

本题中有一个条件：数组长度为n，而且所有数字小于 n

那么可以让元素的索引和值一一对应

第一次遇到，交换索引

第二次遇到，直接能够判断$nums[x] = x$，所以就得到了重复的数字

830. 较大分组的位置

输入：字符串s，全是小写字母

输出：二维数组，每个元素是一个还有两个整数的数组

条件：较大分组指的是连续三个字符及以上的分组，两个整数分别是起始坐标和终止坐标

这个简单啊，直接遍历不就好了，如果不相等直接重置

相等累计，直到结尾

然后把数组汇总一下就可以了

一个特例：就是最后几个字母是一样的，那么就会一直continue，所以到最后再判断一次end和start是不是相等，得出答案

代码：

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        if not len(s):
            return []
        output = []
        start, end = 0, 0
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                end += 1
                continue
            if end - start >= 2:
                output.append([start, end])
            start, end = i, i
        if end - start >= 2:
            output.append([start, end])
        return output

可以通过，但是速度和空间都比较糟糕

阅读题解

就是一次遍历的方法，记录当前分组的长度，如果字符不同，那么就说明已经到尾部了

但是为什么我的这个代码这么慢呢？

（1）其实不用同时更新start和end，其实可以只记录start，因为end会直接由 i 来确定

减少一个变量之后，确实减少了部分用时，但是内存还是比较大

189. 旋转数组 - 数组

输入：整数数组nums，非负数 k

输出：没有输出，不要输出，直接对原数组进行调整即可

功能：间数组中的元素向右移动 k 个位置

---

题目中说至少有三种方法可以解决该问题，而且要求空间复杂度 O(1) - 原地算法

---

从示例观察来看，直接把数组中 -k到最后一个数字整体搬到最前面就好了，但是如果 k 比数组长度还要大呢？

问题是，没有输出，那我怎么输出呢

我这种方法就是使用呢额外的数组，需要注意的是，必须要使用调整nums的方法，而不是生成nums的方法

==这个方法的本质是把原数组中下标为 $i$ 的元素，放在了新数组的 $(i+k)\mod n$的位置==

---

所给提示：

（1）最简单的方法需要增加存储空间

（2）比较困难的就是再不添加任何空间的情况下解决问题，这意味着需要使用某种方法在原始数组的基础上移动相关的元素

（3）一种方法是 reversing the array（or part of it），翻转？

---

阅读题解

环状替换

• 比如从 0 =》 到 $(0+k)\mod n$，然后从 $(0+k)\mod n$ 到$(0+2k)\mod n$，一直到回到 0 位置，这个过程一定是走了整数个圈数
• 比如 a 圈，总共遍历了 b 个元素
• 那么 $ an = bk$ 总的元素数量是相等的，所以 an 一定是 n 和 k 的公倍数（不能重复，所以是最小公倍数 $lcm (n,k)$)
• b 也就是这个最小公倍数 除以 k ，$lcm(n,k)/k$
• 每次遍历会 访问 b 个元素，所以最后应该遍历 $n/b$ 次
• 由于 b，n，k之间的关系

所以最后需要遍历 n 和 k 的最大公约数次

应该说，这个方法看起来的可行性高，而且也不难

数组翻转

基于事实：将数组元素向右移动k次，尾部 k mod n 个元素会移动至数组头部，其余元素向后移动 k mod n 个位置

所以就可以先把所有元素翻转，这样尾部的 k mod n 个元素被移至头部

然后再翻转前后两个区间，以 k mod n -1 为界，就得到了最后的大浪

这里的示例中写了一个翻转的函数，简单来说就是用 一个调换数组元素的方法 实现 整个数组的翻转

（1）指定 start 和end结点

（2）判断 start 和end 的关系，然后将两个数字对应的数组中的数字互换

（3）start +1，end -1

然后循环，这个方法很不错

问：python中对数组的操作都有哪些？

list.reverse() 就是对列表进行反向

list.sort() 对原列表进行排序

但是截取一段，然后进行翻转的方法是不可以的，这样其实还是相当于增加了空

动态规划

面试题08.01 三步问题

输入：int 类型数值 n

输出：int 类型数值

功能：从0开始，每次可以增加1，2或3，直到数值加到n，求所有到达 n 的种类

本题是可以通过暴力方法进行求解的，那么就是排序种类问题

如果使用动态规划的方法呢？

其实到达从上一步到达下一步的方法只有3种路径

提示1：自上而下处理问题，先从最后一步开始

最后一步有三种方法

但是从 i 到 i+3 不止一种走法

提示2：如果直到跳到第100级台阶之前的每一级台阶的跳法数量，可以计算第100级台阶的跳法数量吗？

这个提示实在是太妙了

那肯定是 【99级的跳法数量 + 98级跳法数量 + 97级跳法数量】

虽然有以下几种情况：

99级中有两种情况：

• 98级 + 1级
• 97级 + 2级

98级一种情况：

• 97级 + 1级

但是这些情况并不影响各自到100级台阶的情况

所以这是在提醒我，$sum_n = sum_{n-1}+sum_{n-2}+sum_{n-3}$

提示3和提示4是在强调：相加还是相乘

提示4：

当我们先做什么再做什么，需要相乘

当我们这样做或那样做，需要相加

初始条件：

sum_0 = 0

sum_1 = 1

sum_2 = 2

sum_3 = 4

sum_4 = 7 …

这么说这就是一个数列啊，直接按照数列的方法也是可以进行求解的！

也就是说本题是在求解一个数列，不过这个数列的项不少，要找一个通项公式可能比较困难

提示5，6是关于优化的，计算时间复杂度

制表法是什么，怎么样进行优化

时间复杂度在哪，显然是在重复计算上，要不停变换三个加数，但是实际上加数是在不断交替的，而并非真的是在重新计算，但现在的情况是每个加数都进行了重新计算

还有一个问题，是不是可以通过除以3来把这个过程优化一下？

阅读题解

题解中讲到的方法是使用矩阵实现快速计算

但是实际上使用递推的方法就是可以实现的，问题是中间的数也会比较大，所以只在最后一步取模会导致空间和用时都比较高，可以考虑每一步都给 几个数值取模，这样的话不影响结果，还能保证时间和空间复杂度

509. 斐波那契数

输入：n

输出：f(n)表示斐波那契数列的第n个数字

注意：f(0) = 0, f(1)=1

斐波那契数列的问题其实之前遇到过，确实有一些比较好的方法可以借鉴，很经典

面试题16.17. 连续数列

输入： 整数数组

输出：子数组和

要求：该子数组连续，且该子数组的和再所有子数组最大

本题和53题，和offer42题为同一个问题

f(n) 表示以n结尾的最大和的连续子数组的和

那么$f(n+1) = max(f(n), f(n)+i_{n+1})$是吗？显然不一定，要让这个成立，只需要 $i_{n+1}$是正数就可以了【错了！！！】

是$f(n+1) = max(f(n)+i_{n+1}, i_{n+1})$，其实也还是重置的方法

提示1：把数字想象成正负交替的数字序列

因为实际上不会只包含正序列或者负序列

提示2：如果有一个和为负数的数列，那么一定不是一个数列的开始或结束（因为这个数列完全可以去掉）

如果它们连接了另外两个数列，那么就可以以一个数列的形式出现

提示3：从数组的开头开始，当这个子数列增长时，仍然是最佳子数列

但是一旦变成负数，就没有意义了

这让我想起以前做过的一道题，就是把类似的数列的和存储了下来

只要是负的就重置，并把变负之前的和记录下来

相当于是在计算以每一个数字开头的数组的最大连续正数和

总结一下，这类题已经做了三遍了：

• 刚开始还愿意仔细分析序列的正负特点，到后来只愿意使用动态规划来做了

• 动态规划上，关于连续的特点，要么是接着上一个序列，要么是从头开始：$f(n+1) = max(f(n)+i_{n+1}, i_{n+1})$

• 而间断的特点就是，可以是上一个，或者是上一个加上当前的：$f(n+1) = max(f(n), f(n)+i_{n+1})$

有的题目需要给出连续的个数

有的题需要给出最后的和，一定要适应一下

图

1203. 项目管理 - 图，拓扑排序

输入： n - 项目数量， m - 小组数，group - 每个项目对应的小组，beforeItems - 每个项目的先决项目

输出：列表 - 项目排序

要求：

• 每个项目对应的小组写在 group中，最多一个小组负责，全程不需要修改，只需要判断，-1表示没有小组接手，但是仍然需要进行排序
• 同小组的项目需要相邻
• 要先完成先决项目，才能完成后续项目
• 小组和项目都是从0开始排序

---

从示例来看，首先需要把先决项目完成

然后可以根据项目组进行排序

感觉是使用树结构的方法会比较好

从before开始查找整个树

官方标签：深度优先搜索，图，拓扑排序

---

三个提示：

• 图问题
• 在 dependency graph 的基础上找一个拓扑排序的方法
• 建立两个图，一个基于小组，一个基于项目

---

在本问题中，我需要知道的是：

（1）我应该怎么样构建一个图？

（2）怎样使用图进行排序

拓扑排序

有向图G，将G的n个点排列成一组序列，任意一对顶点（u -> v）之间判断边

如果存在有向边 u -> v，那么 u 在序列中需要出现在 v 的前面

本题中

（1）把项目 items 抽象成点，项目间的依赖关系抽象成边，依赖条件就是有向边，进行拓扑排序

（2）==【同组项目要彼此相邻】== = 组与组之间也存在依赖关系，所以要解决组之间的拓扑排序

所以，本题分两步

（1）首先解决组与组之间的依赖关系，组抽象成点，组与组的关系抽象成边，建图判断是否存在拓扑排序（groupTopSort，以组为先）

（2）存在拓扑关系（groupTopSort），再确定组内依赖关系，遍历拓扑序，对于任意 组 g，对所有属于组 g 的点再进行拓扑排序，最后把组内拓扑排序按顺序放入答案数组

细节

（1）部分项目无人接手，groupId = -1，不利于编码，可以重新编号，但又不能与真实的小组编号冲突，可以从 m 开始正序编号【真实小组编号在0到m-1之间】

（2）将拓扑排序抽象成一个函数进行复用，函数定义 topSort(deg, graph, items)表示：

• 待排序点集 items
• 点的入度数组 deg
• 点的连边关系 graph，graph[i] 表示点 i 连出点组成的集合

（3）建图过程中，如果发现两个项目属于不同的项目组，组间关系图添加相应边，否则在组内关系图中添加相应边

---

阅读题解

参考一个题解说明：[Python] 两次拓扑排序100%

入度：

有向图G中，对于节点 v，从节点 n1，n2，…，nm出发都可以一步到达 v，那么节点 v 的入度就是 m（是说v的来源有m条吗？）

拓扑排序

图中节点与节点之间的访问顺序，可用拓扑排序方法生成一个可行的访问序列

（1）建图

（2）统计图中所有节点的入度

（3）BFS 方法获得访问序列

• 将入度为0的节点添加到队列中
• 遍历队列
  • 得到队首节点并出队
  • 将当前节点添加到访问序列中
  • 将当前节点所有邻居节点的入度 -1
  • 如果邻居节点的入度变为0，将邻居节点入队

【？？？】确实没看懂

方法：

两次嵌套拓扑排序

思路：

1. 建图
2. 对小组进行拓扑排序，获得访问小组的顺序
3. 遍历小组的访问顺序
   1. 得到该组的项目顺序
   2. 将项目顺序添加到答案中

建图：

• 无组项目给全新组号
• 小组建图计算组入度
• 统计各组有哪些项目
• 组内建图算项目入度

返回空列表的条件：

• 小组不在得到的访问顺序中
• 项目不在得到的该组项目的访问顺序中

queue = collections.deque()

deque 是一个双端队列，可以从两端进行 append 的数据结构【不过从左端加入使用的是 queue.appendleft()】

还可以从两端出队列 queue.pop() 和 queue.popleft()

一般需要提前 from collections import deque

参考：collections中 deque的使用

代码分析

组数 m 也就是 group_id 的最大值

遍历 n 个项目，给没有组接手的项目重新标记组号 m, m+1, …

初始化几个列表：【列表的初始化建议】

• 项目入度列表 - n个0 [0]*n
• 小组入度列表
• 项目邻居列表 - n个子列表 [[] for _ in range(n)]
• 小组邻居列表
• group_to_tasks 【这个列表用来做什么？】

遍历任务==【组间排序】==

• 按照各项目所属的小组号，在 group_to_tasks的相应位置，添加任务号

  • 也就是说，这个数组存放的是 各组对应的任务数

• 遍历先决任务的list

  • 这个list 的id是当前任务，value 是先决任务
  • 可以判断两个任务的是不是同组 group[id] 和 group[value]
    • 不同组，那么该小组的入度 +1，先决组的邻居加上当前组【组间建图】
    • 同组，那么任务的入度 +1，先决任务的邻居加上当前任务【组内建图】

接下来获得小组的访问顺序

• 使用自定义函数 self.topological_sort，输入是 任务或者小组，入度，邻居三个内容【具体分析见下一个部分】
• 首先对小组间进行排序，输入小组号的列表，所有小组的入度列表，所有小组的邻居列表

做一个判断：如果组外排序数组数量【排的是小组的访问顺序】，不等于所有组的数量，那么就直接返回空列表【为什么】

最后遍历小组号，注意小组号超过 m 的就不用了==【组内排序】==【排的是组间的排序】

• 对组内根据任务进行拓扑排序
  • 输入：group_to_tasks[group_id]，任务入度，任务邻居
• 做一个判断，如果任务排序后的长度不等于每组对应的任务数，那么就返回空
• 把排序号的任务列表添加到最后输出列表中

把最终排序列表输出

---

其实这里面自定义的函数==拓扑排序函数==才是关键

自定义函数的具体内容：

输入：待排序数组，对应入度，对应邻居列表

初始化双端队列和输出列表

遍历待排序列表，item

• 如果 item 对应入度为0，直接将 item 加入双端列表
• 【入度为0表示这就是最底层的节点了，如果不是0，那么就是说还有子节点，不饿能直接进行排序？】

如果双端列表为空，直接返回空数组【双端列表究竟是什么意义】

接下来是广度优先排序（BFS）

• 只要双端列表不为空就一直循环

• 将双端列表的左元素移出，放入输出列表中

  • 对该元素的邻居进行遍历
  • 各邻居的入度 -1
  • 如果有邻居的入度为0，那么也将这个邻居加入双端列表

• 直到双端列表为空

最后输出输出列表

---

仔细体会各步骤的用意

1. 找到了每一个组对应的所有任务
2. 避免无人认领项目的影响【至少不能认为他们是同组的】
3. 两步排序的方法分了组间排序和组内排序，分别考虑组要靠在一起，其次是组内顺序也要考虑
4. 首先考虑的是任务的先后关系
   1. 先后任务在同组，那么任务入度不同
   2. 先后任务在不同组，那么小组入度不同【小组的入度 = 先决组的数量，先决组是小组的邻居】，至于说各任务在组内入度就要看是不是还和组内任务有先后关系
   3. 如果==任务的先决任务列表==恰好为空，那刚好，对该任务的入度和邻居都不影响【那么直接排顺序就好了，这是最简单的情况】
5. ==【入度本身是强调先后顺序，有入度，那么该小组或者该项目就应该往后排】==
   1. 入度越小的项目或者小组，就越应该往前排
   2. 全都有入度，那么这个任务或者小组根本就不可行
6. 组间排序考虑各小组的入度，组内排序考虑各项目的入度
7. 拓扑排序的方法，就是从入度来判断一个值能不能进行排序，然后对该值的邻居排序，未排序的内容入度就应该减小，相当于在剩下的内容中进行排序

这样通过遍历任务，获得了小组的入度和项目的入度，邻居则是同时获得的【左邻居还是右邻居并不重要，重要的是邻居都要包含在列表里面】【一个小组或者一个项目的邻居有上限吗，有什么样的意义】

==建图的关键是两个列表：入度 和 邻居==

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        max_group_id = m
        for task in range(n):
            if group[task] == -1:
                group[task] = max_group_id
                max_group_id += 1
        # 到此，共有 max_group_id 个组

        group_indegree = [0] * max_group_id
        task_indegree = [0] * n
        group_neighbours = [[] for _ in range(max_group_id)]
        task_neighbours = [[] for _ in range(n)]
        group_to_tasks = [[] for _ in range(max_group_id)]

        for task in group:
            group_to_tasks[task].append(task)
        print(group_to_tasks)

上面是我写的一个初步的代码，我们分析一下第 16 行，我希望能够得到 每个组对应的task情况，但是这种遍历方法肯定是不对的，而是应该

for task in range(n):
    group_to_tasks[group[task]].append(task)

这样才可以实现把 task 放到对应的 group 中的想法。

然后，我根据回忆进行程序的复现过程中，另一个问题是组内排序的方法，应该遍历已经排好序的组的列表

这样可以获得组号

然后根据组号去查找每组里面的任务

对任务进行排序

最后把排好序的任务放到最终输出的列表就完成了！

---

OK，本期的解题就是这些，总体来说，简单题虽然能够尝试，但是限制了对真正算法的现象和理解，还是需要多对其他难度和其他类型的题进行尝试，从而获得更好的学习效果！