LeetCode刷题笔记（五）

算法
Word count: 9.1k   |   Reading time≈ 35 min

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

本期内容紧贴2021年1月leetcode每日一题，本月主要内容是并查集（包括深度优先或广度优先）及双指针，包括在周赛中也遇到双指针题目，需要重点考虑。

1018. 可被5整除的二进制前缀

输入：整数列表 - 只有 0 和 1

输出：布尔列表 - 只有 false 和 true

要求：依次选择整数列表中 从 第0位到第i位的所有数字，这是一个二进制数字，如果可以被5整除，那么布尔列表的第 i 位为true，否则为false。

自我解读

方案：

（1）先获得十进制数字

由于本身就是列表，确实要稍微容易一点

$num_{10} = num_2[-1] * 1 + num_2[-2] * 2 +…+num_2[-i] * 2^{i-1}$

但是如果每次都是从头开始计算，2的幂需要计算，空间占用会比较多

（2）能不能被 5 整除其实最关键的就是看最后一位，5或者0就可以

观察一下：1，2，4，8，16，32，64，128，256，…，已经有规律了

阶数 0 1 2 3 4
最后一位 1 2 4 8 6
阶数 5 6 7 8
最后一位 2 4 8 6

那么能够产生被5整除的情况：

  • 1 + 4：索引0 + 索引2+4n
  • 2 + 8：索引1+4n + 索引3+4n
  • 4 + 6：索引2+4n + 索引4+4n

对以上组合的对数进行计算，只要能配好对，那就可以整除

我觉的这个思路就好很多，尤其对一些比较长的数字会比较好

存在几个问题：

（1）那么问题是到底要怎么样进行遍历呢：比如我可以判断 2+4n 有没有超过 len

（2）能不能利用前面的数据判断当前的情况？其实应该是可以的，每次应该计算出下一位需要几，如果是那么就是true，如果不是那么就是false；这样形成一个动态规划

比如说刚开始形成3个存储数字A1，A2，B1，B2，C1

  • 开始，如果索引0是1，A1+1
  • 如果索引2+4n是1，A2+1
  • 如果索引1+4n是1，B1+1
  • 如果索引3+4n是1，B2+1
  • 如果索引4+4n是1，C1+1

最后判断：A1+C1 == A2，B1 == B2，这样又会出现一个问题，如果刚好是 22222，那么也是可以的，这样是1+4n为奇数

注意，0对数值大小完全没有影响

（3）新方案，设一个数值Res，直接遍历字符串，然后

  • 索引0是1，Res+1
  • 索引1+4n是1，每个+2
  • 索引2+4n是1，每个+4
  • 索引3+4n是1，每个+8
  • 索引4n是1，每个+6

最后，如果Res可以被5整除，那么就是true，如果不是那就不行

然后，每次是在结尾增加了一位数字

  • 索引0 -》索引1，Res+1

  • 索引1+4n -》 索引2+4n，每个+2

  • 索引2+4n -》 索引 3+4n，每个+4

  • 索引3+4n -》 索引 4n，每个-2

  • 索引4n -》 索引1+4n，每个-4

确实是可以进行抵消的，但问题是前面各索引有1有0需要计数吗？

也就是说我只统计各索引的次数，然后每次把这些数字进行移动（轮换）

观察题解

官方题解

从二进制到十进制数字的特点是：$N_i = N_{i-1} \times 2 +A[i]$

每添加一位数字，计算余数，看能不能被5整除就可以了，这个方法也不错，还很简单

相对来说，我的方法还是复杂了，惭愧！

947. 移除最多的同行或同列石头 - 并查集

输入：二维整数数组，每个子数组只有两个整数元素，相当于坐标

输出：一个整数

要求：同行（第一个元素相同），或者同列（第二个元素相同）的子数组只能保留一个，最后输出的就是要去除的子数组的数量

自我解读

遍历数组，如果行号是新的，行号list新增一个

如果列号是新的，列号list新增一个

遇到新的子数组，检查行号是不是在行号list中，是，del+1，直接下一个

否，检查列号是不是在列号list中，是，del+1，直接下一个

否，下一个，过

但是，题目中要求是：==可以移除的石子的最大数量==

比如示例1：

1
2
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5

如果按照我的思路，先记录了【0，0】，那么会去掉【0，1】【1，0】，但是不会取消【1，2】

但是实际答案说的却是：先移除【2，2】，因为它和【2，1】同行了，。。。最后就只剩下了【0，0】，就像是后来的先移除，这样一定是移除最多的吗？

另一个问题：所有输入一定是一行一行进行展示的吗，这样的话岂不是要简单一点

既然需要最大移除数量，那么就要把移除的石子的两个坐标也加入到list中，这样一定是最大的吗？

还是存在一点问题的：

例如一个输入：[[0,1],[1,0],[1,1]]，最多可以移除两个石子，但是按照上面的算法却只能去除一个石子

image-20210115142425858

类似的，其实这样一个三角结构，会决定到底应该怎么样进行移除

我们如果是从前往后，那么就只能移除1个，但是如果从后往前，就可以移除两个，同样，反过来也是一样的

新增案例：[[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]]

这个案例说明了，子数组并不是按顺序的，如果不按顺序来进行排列

就有可能导致少删除一个

阅读题解

横坐标相同、或者纵坐标相同，那么就形成了一条边，有联系的边构成了一个连通图

==一定可以把一个连通图里的所有顶点根据该规则删到只剩下一个顶点==

原因是：连通图中，可以通过遍历方式遍历到该连通图中的所有顶点，按照遍历的逆向顺序移除石头就可以只剩下一块石头

所以，题目的结果 = 石头总数 - 极大连通子图（连通块或连通分量）的个数（连通块的数量=最后剩下的石头的数量）

并查集里的元素是描述 横坐表和纵坐标的数值

遍历数组，每个元素的横坐表和纵坐标在并查集中进行合并

合并：所有横坐标 为x的石头和所有纵坐标 为y的石头都属于同一个连通分量

那么在并查集内部，我们要如何区分横纵坐标？

石头的位置是 数组，并查集底层是一维，怎么样在并查集中区分横纵坐标

方法是扩大坐标区间，比如题目说 $0<=x_i,y_i<=10^4$，那么就可以操作：$横坐标 \pm 10001 $，从而超越原来的区间，保证不会重复

==问题是怎么合并？==

（1）第一种方法：需要枚举计算任意两点间的连通性，可以使用深度优先或者广度优先搜索的方法进行计算

官方题解的python3代码中使用了edge=collections.defaultdict(list)来作为存储单元，用于建图，也就是通过枚举找到了所有相互关联的边

但是到了深度优先搜索这里，看上去还是使用了一些库吗？vis.add(x)，但是vis并没有进行定义，也有可能是定义的晚了（在下方，函数调用前有一个定义vis=set()）？我个人觉得这个写法很糟糕，也许是和下面的代码进行了联动，但是展示出来的效果却非常差

（2）第二种方法：

上面的方法需要循环套循环进行元素的遍历完成建图，还是有一点麻烦了。

任意两点之间直接相连或间接相连其实都是可以的，我们只关注两点之间的连通性。

该方法说对于拥有k个石子的任意一行或者一列，都使用 k-1 条边进行连接

所以方法就是：

  1. 先用哈希表存储每一行或每一列所拥有的石子，对纵坐标加了10000，以区分横纵坐标
  2. 然后分别处理每一行或每一列的连通属性

非官方题解：

大多数方法建立了一个专门的==class（class UnionFind）==来归纳并查集的方法，然后对该类中的方法进行调用

终于找到一个可能比较容易理解的算法了

参考：Python,并查集, O(nlogm)94%,O(m)19%

仍然保留了两个关键：

  • 答案 = 石头总数 - 连通块的数量
  • 纵坐标+10000，==这样就可以把坐标也看成edges了！==

这里举了例子：

[[0,0],[1,1],[1,2]]=>[[0,10000],[1,10001],[1,10002]]

这里（1）思考为5个nodes：0,10000,1,10001,10002

（2）把[0,10000]视为 node 0和node 10000有edge连通，其他类似，这样就好理解为什么+10000能方便求解了

然后转化为了熟悉的图并查集问题，遍历所有edges，找出所有连通组

步骤一：给所有纵坐标+10000

还是比较容易的

1
2
for stone in stones:
    stone[-1] += 10000

步骤二：如何遍历所有的edges，找出所有连通组？

代码中建立了一个字典吗？还是set？

dus={s+i*10000:s+i*10000 for stone in stones for i, s in enumerate(stone)}

遍历每一个石头，i 是第几个，s是坐标值啊，s+i*10000?这个我就不太理解了，是原来的意思吗

神奇，我尝试了一下：

1
2
3
4
>>> ss = [[0,0], [1,1], [2,2]]
>>> dus = {k+i*10000:k+i*10000 for s in ss for i, k in enumerate(s)}
>>> dus
{0: 0, 10000: 10000, 1: 1, 10001: 10001, 2: 2, 10002: 10002}

没想到真的能出这样的结果

当我打下下面的代码的时候，发现了问题所在：

1
2
3
4
5
6
7
8
9
10
>>> for s in ss:
...     for i,k in enumerate(s):
...         print(k)
...
0
0
1
1
2
2

这是因为 enumerate 针对的是stone，而不是stones！

每个stone只有两个元素，所以 i 只有0 或1，而k就是横坐标或者纵坐标

所以每个横坐标对应0，不会加10000，每个纵坐标对应1，会加10000，就区分开来了，而且使用的是字典，会自动去重！

【妙啊】

然后定义了一个find函数：

  • 输入是 i
  • 如果 字典中 i 对应的位置不是 i
    • 那么继续find（字典中 i 对应的数值），并赋值给 字典中 i 的位置
  • 返回 字典中 i 对应的数值

需要观察一下

比如说 字典 bus = {1:1, 2:2, 0:0}

dus[0] = 0肯定的

如果 字典 bus = {1:2, 2:1, 0:1}

dus[0] = 1，不等于0

那么我们再找 find(dus[0]) = find(1)

find(1)中，dus[1] = 2，也不等于 1，再找find(2)

find(2)中，dus[2] = 1，也不等于 2，再找find(1)不停循环

也就是说不停找，直到找到字典中 key和value一样的值？

然后遍历stones，如果横坐标在字典中，而且横坐标对应的值不等于纵坐标对应的值【这有可能相等吗】

  • 那么，字典中横坐标对应的位置，value等于纵坐标+10000对应的数值

举个例子

stones = [[0,0], [0,1], [0,2]]

那么

dus={0:0, 10000:10000, 10001:10001, 10002:10002}

  • 首次循环：0 在dus，find(0) = 0 != find(0+10000)=10000【是否存在】

    • 所以 dus[find(0)] = dus[0] = find(0+10000) = 10000
    • dus={0:10000, 10000:10000, 10001:10001, 10002:10002}

  • 下一个循环：0 在dus，find(0)中，dus[0] = 10000 != 0了，找find(10000) = 10000，赋值给 dus[0]，最后输出10000 != find(10001) = 10001

    • 所以 dus[find(0)] = dus[10000] = find(10001) = 10001
    • dus={0:10000, 10000:10001, 10001:10001, 10002:10002}

  • 下一个循环：0 在dus，find(0)中，dus[0] = 10000 != 0了，找find(10000) = 10001 != 10000，再找find(10001)=10001，赋值给 dus[0]，最后输出10001 != find(10002) = 10002

    • 所以dus[find(0)] = dus[10001] = find(10002) = 10002
    • dus={0:10000, 10000:10001, 10001:10002, 10002:10002}

然后，需要再来一个循环：

对dus字典中的每一个值进行遍历：

for k in dus: print(k)

这里要注意，输出的只有 字典dus 的键 key，而没有value值

紧接着上面的注释

现在，find(0) = find(10000) = find(10001) = find(10002) = 10002

所以，最后的字典是：

dus={0:10002, 10000:10002, 10001:10002, 10002:10002}

最后一步，set(dus.values())

应该是取字典 dus 的所有值 values，然后生成集合 set，会去重，再计算集合的长度就是连通域的数量了

简直是太妙了！！！

其实find函数就是寻找最高节点的过程；

而第一个循环的意义就是把横坐标的指向改变，也就是添加连通边edge，建图的过程

1584. 连接所有点的最小费用

输入：二维整数数组，每个子数组有两个整数，表示坐标点

输出：整数，表示将所有点连接起来的最小总费用

要求：任意两点之间有且仅有一条简单路径，总路径长度和要最小

果然，又是一个图论的问题

比如说我们要建图，每个点要连接到最近的一个点

但是如果两个点互相是最近的点呢 - 构成了一个孤立的群，两个群之间找一个最短的边即可

如果 A 周围最近的是 B，B 周围最近的是 C，C 周围最近的会不会是 A？不会，一定不是 A

image-20210119161038414

不然的话，离 A 最近的就不是 B 了

又是一个并查集的问题

官方题解

满足任意两点之间有且仅有一条简单路径，只有 树结构 - tree

该树 = 给定图的生成树，总权值最小的生成树，成为最小生成树

经典算法：Kruskal 算法

  1. 图中所有边按照长度的由小到大进行排序，等长边任意顺序
  2. 从前往后（也就是从小到大）扫描排序后的边，如果扫描到的边 连接了两个相异的连通块，则将它插入图中
  3. 最后得到的图就是最小生成树

所以现在的问题是 key 应该取edge的两个端点，还是选择edge 的边长

第一步：建立一个字典，字典的所有value就是list

rec = collections.defaultdict(list) ，表示建立了一个具有默认值的字典，默认值是list

56. 合并区间 - 数组

输入：一个二维数组，每个子数组包含两个整数，表示一个区间的起始和终止端

输出：一个二维数组，每个子数组包含两个整数，表示一个区间的起始和终止端

要求：输入数组可能会有重叠，将重叠的两个区间进行合并，输出区间不能有重叠

我曾想到过一个方法，类似做直方图

  • 先新建了一个字典，默认为0
  • 然后遍历所有的区间，有这个区间，那就在这个区间内将所有的数字对应在字典中的value +1
  • 最后取出所有有数字的key值，再取start和end进行集合

问题是遇到了一个样例：

[[1,4],[5,6]]

如果直接进行直方图，那么一定会得到 [[1,6]]

但是实际上这两个区间并没有重叠

原有代码;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 先建立一个字典，对每一个key的默认值是int类型
        merge_dict = collections.defaultdict(int)
        merge_list = []

        for interval in intervals:
            start, end = interval[0], interval[1]
            for i in range(start, end+1):
                merge_dict[i] += 1

        start = 0
        max_key = max(merge_dict.keys())
        for i in range(max_key+1):
            if not start and merge_dict[i]:
                start = i
            if start:
                if not merge_dict[i]:
                    merge_list.append([start, i-1])
                    start = 0
                elif i == max_key:
                    merge_list.append([start, i])
                    break
            i += 1
        return merge_list

官方题解

排序方法

如果按照区间的左端点进行排序，在排序后：

==可以合并的区间一定是连续的==

官方证明中举例是： a[i], a[j], a[k]，a[i]和a[k] 能合并，但是 a[i] 和 a[j], a[j] 和 a[k]均不能合并

但是我自己举了一个例子：[1,10],[2,5],[10,11]，这个例子明显不满足上面说的 a[i]和a[j]也不能合并的条件，所以其实并不满足题意

用 merged 区间表示最后需要输出的多维列表，先将第一个列表存储到区间中：

遍历所有区间

  • 左端点在上一个区间的右端点后
    • 是，表示不重合，那么加入输出数组
    • 否，表示重合，那么需要更新右端点

第一步：排序，怎样按照第一个元素的大小进行排序？

list.sort()方法的使用

list.sort(key=lambda x: x[0])就可以根据第一个元素的大小进行排序

排序保证了后一个区间的起始点不会小于前一个区间的起始点，所以只需要比较尾巴，不用比较头了

第二步：遍历，进行对比

==本方法的独特性在于，直接与上一个区间进行对比，而不需要再对前面的区间进行对比了==

比如上面的区间对比完了之后已经存储在 merged 里面了，那么现在最新的一个区间，只需要和 meged[-1]进行对比，就可以了，而不需要从 merged[0] 开始进行对比

最后的程序：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda x: x[0])
        merged = []

        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            elif merged[-1][1] >= interval[0]:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

154-offer 11 旋转数组的最小数字

二分查找方法

首先说明旋转数组是指能旋转一次就变成升序数组的数组

所以特点就是，原来的数组是升序排列的

当旋转一次后，其排列规律是：

fig1

最小值右侧的元素都是小于等于右边界点的

最小值左侧的元素都是大于等于左边界点的

可以利用以上的性质从而缩小最小值所在的区间

有一种情况是中间某个点的数值大小 等于 边界点

fig4

那么这个时候不能简单说明该点左侧或者右侧是区间，而应该调整边界点（边界点一定是满足降序要求的，从而找出区间）

面试题04.二维数组中的查找

一个二维数组，每一列从上到下递增，每一行从左到右递增

请在该数组中找某一个数值时候存在，当存在时返回 True，不存在 返回 False

暴力方法，直接查找

线性查找，比如从数组的左下角开始查找，如果比target大，那么行数 -1，如果比 target 小，那么列数 +1

674. 最长连续递增序列

输入：一个递增数组

输出：最长连续递增子数组的长度

非常的明白，就是贪心法把最长的找出来

可能会遇到两个问题：

（1）怎么处理末尾的问题，到末尾，一方面要继续比较是不是递增序列，另一方面还要把当前的子序列输入进结果

（2）怎么样重置，重置为0是不好的，应该重置为1

所以我的代码是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        len_list = []
        len_max = 0
        for i,num in enumerate(nums):
            if not i:
                len_max += 1
            elif num > nums[i-1]:
                len_max += 1
            else:
                len_list.append(len_max)
                len_max = 1
            if i == len(nums)-1:
                len_list.append(len_max)
        return 0 if not len_list else max(len_list)

而官方的代码是：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        ans = 0
        n = len(nums)
        start = 0

        for i in range(n):
            if i > 0 and nums[i] <= nums[i - 1]:
                start = i
            ans = max(ans, i - start + 1)
        
        return ans

每次计算的过程中都在更新最大值，这样能够减少对空间的使用

其次记录的并不是递增序列的长度，而是起始位置，这样也可以减少空间的消耗，只有在变小的时候才会更新起始位置

15. 三数之和

本次周赛的过程中，遇到这类问题，找到四个数字构成定积元组一类的问题，怎么样减小时间复杂度？

发现15、16、18三道题都是这样的问题，看来需要进行一个专题的解决。

相似题目：两数之和、最接近的三数之和、四数之和、较小的三数之和

标签：数组，双指针

输入：一个整数数组

输出：二维整数数组，每个子数组中有3个数字，和为0

要求：

  • 找出所给整数数组中和为0的所有组合
  • 组合不能重复
  • 所给整数数组中的数字是有可能重复的

在示例中出现了一种情况，如果本身数字比较少，少于3个，直接可以返回结果为空

如果数字在3个以上，那也只好进行遍历了，找到所有组合，这样的话，一定需要 $O(n^3)$

提示：

  1. 如果能固定一个数字，那么就变成了一个“两数之和”的问题了
  2. 在两数之和问题中，如果我们固定一个数组，我们就需要扫描整个数组，找最后一个数字是不是存在，可不可以修改这个数组从而让这个查找变得更快呢？
  3. 或者在不改变数组的情况下，我们呢是不是可以通过使用额外空间 的方法，比如哈希表来加速搜索

我直接用遍历的方法进行计算，遇到一个问题：可能会出现相同的元组

例如：nums=[-1,0,1,2,-1,-4]

如果从头开始遍历，可能有 [-1,0,1]，然后又会遇到[0,1,-1]，这两个元组会重复（如果是list确实不重复），但是[-1,-1,2]又是可以的

官方题解

  1. 用排序避免重复答案

  2. 所谓双指针的方法是说：一个头指针，一个尾指针，如果和比较小，移动头指针，如果和比较大，移动尾指针，直到找到值

但即使如此，还没有完全解决问题，比如 [0,0,0,0]，也只能出一个结果 [0,0,0]，但是如果只是进行移动，而没有进行判断，最后会出两个[0,0,0]

实际题解中用了一些细节来解决各种问题：

  1. 如果这次的首位数字和上一次的首位数字相同，直接跳过
  2. 第二个元素虽说是左指针，但是也可以用for循环
  3. 这次的第二个元素也应该和上一次的第二个数字不同，也就是所找一个全新的第二个数字
  4. 只移动右指针即可

官方代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合，随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的错误代码（时间会比较长）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []
        # 排序，以免重复
        nums.sort()

        # 遍历第一个数字 A
        for i in range(n):
            # 确保在i循环中，该数字不会重复
            if i>0 and nums[i] == nums[i-1]:
                continue

            # 遍历第二个数字 B，正着遍历
            for j in range(i+1,n):
                # 确保在j循环里面，该遍历数字是不会重复的
                if j>i+1 and nums[j] == nums[j-1]:
                    continue
                target = - nums[i] - nums[j]

                # 第三个数字，从尾部遍历
                k = n-1
                while j<k and nums[k]>target:
                    k -= 1
                if j == k:
                    # 说明到头了，这个循环结束了
                    break
                if target==nums[k]:
                    result.append([nums[i],nums[j],nums[k]])
        return result

关键的原因请看第22行： k=n-1这行代码如果放在 j循环中，那么就跟3个循环是一样的！！

如果放在 j循环的外面，立马就不一样了，j 增加， k并没有每次都归 （n-1），这样就减少了一次循环，这是非常重要的！

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

输入：整数数组 nums，整数target

输出：整数

要求：在nums中找3个数字，其和与target最接近，输出的整数即为该和，假设只有一个答案

那么这一次，我们需要记录最小的和，也就是差值最小的和，然后每次去比较差值，如果没有更小的了，那就是它了

还是双指针

先要做一个排序

第一个数字遍历

  • 开头取一个，结尾取一个
  • 如果大了，结尾小一位，如果小了，开头就要加一位，最终会有一个最接近的
1
2
3
4
5
6
7
8
9
10
11
12
sort
for i in len:
    first_num = list[i]
    k = n-1
    for j in i+1:len:
        second_num = list[j]
        sum = first_num + second_num
        sum_des = target - sum
        while list[k] > sum_des:
            k -= 1
        sum += second_num + third_num

但是此时的比较方案和上面又不太一样了，如果 k减到最后已经比最后的差值小了，再升 j 还是小

没关系，我们可以额外使用一个变量，用来比较和存储比较小的差值

本题的三个数字是不是还需要像上面的题一样避免重复？

  • i 不变的情况下，确实 j 不用再重复了
  • i 如果重复呢，确实也不用，所以 i 最好也不要重复了

官方题解

  1. 本题和15题不一样的地方在于，本题要的是最小差距，而不是枚举所有的最小差距的取值

  2. 双指针既可以用之前的双循环的方式进行书写，也可以使用真的双指针，两个索引的方式进行书写

  3. 初始化 最佳答案的方法是，直接赋值，赋一个很大的值，比如1e7

最后完成的代码是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 首先排序
        nums.sort()
        len_num = len(nums)
        min_tar = 1e7

        # 第一个数字的索引
        for i in range(len_num):
            # 防止重复
            if i and nums[i] == nums[i-1]:
                continue
            # 第二个数字的索引
            j = i + 1
            # 第三个数字的索引
            k = len_num - 1
            while j < k:
                sum_three = nums[i] + nums[j] + nums[k]
                if sum_three > target:
                    k -= 1
                elif sum_three == target:
                    return sum_three
                else:
                    j += 1
                if abs(sum_three - target) < abs(min_tar - target):
                    min_tar = sum_three
        return min_tar

相比官方答案有一点偷懒的地方就是更改 j和k 的时候是直接改，并没有去检查一下修改后的实际数值和修改前的有什么区别，这样其实不太好，确实会重复计算。

18. 四数之和

输入：整数数组nums，目标值 target

输出：二维数组

判断nums中是否存在 a,b,c,d，满足 $a+b+c+d=target$，找出所有满足的组合（不能重复）

本题看上去还是用双指针的方法进行解决

第一种遍历方法：固定1、2、4，然后让第3位数字遍历

先排序

第一个数字 i 直接循环

第二个数字 j从 i+1 开始递增

最后一个数字 从 n-1 开始递减

然后第三个数字 就要在 j 到 k 之间进行遍历

要注意的是，这一次，j和k的遍历都不能重复了，要保证是不同的

之前的问题中，实现这一目标，有两种方法：

  1. 循环用 for，然后在循环体中添加判断 当相同的时候就continue

  2. 循环用 while，循环体中直接判断，判断结束后直接修改索引（第二种方法可能看起来比较容易，实际上两个方法可能消耗的时间差不多）

    这种方法的不足之处是，需要修改的时候，考虑的会比较多

    而且使用while比较的时候似乎需要考虑会不会超出索引边界

1
2
3
4
5
6
7
8
9
10
11
12
sort
for a in list:
    if a == last_a:
        continue
    
    j = a+1
    k = len-1
    while j<k-1:
        for c in range j->k:
	        if a+j+c+k == target:
    	        result.append(this_group)
        # 该怎样控制 j 和 k 的增减产生双指针的效果呢？

在写上面那种方法的时候突然想到，如果我们先固定1，2，那么3，4不就是一个新的双指针了吗？而且这种方法看起来更可靠

但是同样需要注意，2可以和1重复，但是2和之前的2不要重复，1和之前的1也不要重复，3也不要重复

出现的问题是在运行过程中，不是超出了时间限制，就是超出了内存限制

哦，我忘了一件事，就是在 ==等于target的时候，也需要进行移动==，不然就出不去了

官方题解

阅读官方的代码，发现了几个有意思的点：

  1. 第一个数字的索引区间是 0到 n-3

  2. 第二个数字的索引区间是 i+1 到 n-2，还使用了 j>i+1 保证满足j的区间正确

  3. 还有就是一些比较基础的判断：

    • i,i+1,i+2,i+3 这样四个数字加起来如果都比target大，就不用再循环了
    • i，n-1，n-2，n-3这样四个数字加起来如果比 target小，那也不用循环了
    • i，j，j+1，j+2，这样四个数字加起来比 target 大，本轮（第二层循环）可以结束了
    • i，j，n-1，n-2，这样四个数字加起来比target 小，本轮（第二层循环）可以结束了

  4. 最后在修改 左右区间的时候

    1. 只有=target的情况下，修改区间才需要判断是不是和之前的相等
    2. 不等于target，那就直接更改左右边界，不用判断和之前的是不是重复

  5. 还有很有意思的地方：

    1. 官方题解中

      1
      2
      3
      while left < right and nums[left] == nums[left + 1]:
          left += 1
      left += 1

      因为是和右侧对比，所以可以先对比，最后再 +1

    2. 我刚开始的方法是，先+1，然后再和左侧进行对比

    3. 应该说两者还是有一些细节上的不同的

果然，使用基础判断条件能够极大减少判断时间！

再把 和的计算结果保存下来，又能节省一点时间（毕竟后面多次用到了计算出来的和）

小岛问题 - DFS练习

参考：小岛问题 - DFS子专题

深度优先遍历的方法

经典方法：（四联通）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def dfs(i,j):
    if i或j 出界: return
    if (i,j)已经遍历过: return
    temp = board[i][j]
    # 将（i，j）添加到已经遍历过的列表中
    seen.add((i,j))
    # 按照四连通，分别对上下左右四个方向进行递归遍历
    dfs(i+1, j)
    dfs(i-1, j)    
    dfs(i, j+1)    
    dfs(i, j-1)    
    # 撤销标记
    seen.remove((i,j))

# 使用算法：单点搜索
dfs(0, 0)
# 多点搜索
for i in range(M):
    for j in range(N):
        dfs(i, j)

这种方法的标记是专门用了一个列表来存放遍历过的点

还有一种标记方法是原地标记，比如直接把遍历过的点的values变成 -1

参考：深度优先遍历

Depth-First-Search 深度优先搜索算法，遍历或搜索树或图的算法

  • 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
  • 当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。
  • 这一过程一直进行到已发现从源节点可达的所有节点为止。
  • 如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
  • 属于盲目搜索。（对应启发式搜索，有目的地搜索）

DFS是图论中的经典算法，和图、拓扑排序密切相关

对于树的题目，基本上都可以使用DFS来解决

DFS通常可以基于递归来做，因此算法会更简洁

并查集练习

有个同学这样进行描述：并查集 union-find

一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

有一个联合-查找算法（Union-find Algorithm），两个操作：

  • find：确定元素属于哪一个子集【建图和压缩路径】
  • union：将两个子集合并成同一个集合

不带权并查集

带权并查集

以下对无权并查集的基本类进行研究：

class UF：

初始化函数：

（1）建立一个字典parent表示父元素的集合

（2）建立一个整数cnt，用于记录？

查找（find）：

  • 如果不在父集合中
    • cnt +1
    • 父集合中添加元素

集合（union）：

  • 调用连通判断函数（connected）检测 两个元素是不是连通的

连通（connected）：

  • 通过 find 函数判断两个元素的find值是不是相等

说真的这个class包括里面的函数不是很好理解

字典的使用

使用 collections.defaultdict() 建立字典

collections.defaultdict()为字典提供默认值，以免字典中Key不存在的时候引发KeyError的异常

这是一种==提供了默认值的字典==

该函数返回一个类似字典的对象

defaultdict 是 Python 内建字典类（dict）的一个子类

rec = collections.defaultdict(list)

那么在调用的时候，使用rec.items 可以比较完整地调用key和values的值对，也可以通过 rec.values()调用所有的values，这样不会包括 keys

参考：

该博客中说，key 值可以自定义，value 的类型与括号中设置类型先沟通，比如括号中是list，那么最后的键值对的值就是list

修改字典

如果 字典的 value是list：可以 rec[k].append(v)

如果 字典的 value是set：可以 rec[k].add(v)

如果 字典的 value是int：可以 rec[k]+=1

list.sort()综合排序方法

list.sort(cmp, key, reverse)

  • cmp - 使用该参数的方法进行排序
  • key - 每个列表中用来进行比较的元素，可以取自于可迭代对象中，指定可迭代对象中的一个元素进行排序
  • reverse - 降序标志，默认是false升序

比如如果需要对列表的第一个元素进行比较，可以这样进行使用：

list.sort(key = lambda x: x[0])

OK，本期的解题就是这些，并查集其实理解还不够深入，深度优先和广度优先将是一个大的领域，接下来需要重点关注！

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 Sun Yue

请我喝杯咖啡吧~

支付宝
微信