基础算法 | Ziuch の Blog

type

status

date

slug

summary

0 本节习题一览

整数二分习题：69. x 的平方根

二分枚举答案习题1：1283. 使结果不超过阈值的最小除数

二分枚举答案习题2：1552. 两球之间的磁力

一维前缀和习题：523. 连续的子数组和

二维前缀和习题：304. 二维区域和检索 - 矩阵不可变

一维差分习题：1094. 拼车

双指针习题(请分别用二分和双指针实现)：167. 两数之和 II - 输入有序数组

1 二分

💡

在有序列表里以O(logn)的复杂度下查找某一个值

💡

需要注意无限循环的问题，区分整数二分和浮点数二分

💡

二分不一定是针对列表排序，还可以用来枚举最值(数字天然有序) ，抓住题目关键字最小值最大，最大值最小

动画演示：

1.1 整数二分代码模板

整数二分习题：69. x 的平方根

1.2 浮点数二分代码模板

浮点数二分习题：好像只有一题要开会员那就算了 https://leetcode.cn/problems/pour-water-between-buckets-to-make-water-levels-equal/

二分枚举答案习题1：1283. 使结果不超过阈值的最小除数

二分枚举答案习题2：1552. 两球之间的磁力

1.3 Python标准库内的二分

`bisect_left(a, x)`

功能：找到插入位置，使得新元素可以插入到列表中，并且仍然保持列表的有序性。返回的位置是在所有等于该元素的现有元素之前。

使用场景：用于在插入元素时保持新元素在相同元素前面的位置。

参数：

a：待查找的有序列表。
x：要插入的元素。
lo（可选）：查找的起始索引，默认为 0。
hi（可选）：查找的结束索引，默认为 len(a)。

示例：

`bisect_right(a, x)`

功能：找到插入位置，使得新元素可以插入到列表中，并且仍然保持列表的有序性。返回的位置是在所有等于该元素的现有元素之后。

使用场景：用于在插入元素时保持新元素在相同元素后面的位置。

参数：

a：待查找的有序列表。
x：要插入的元素。
lo（可选）：查找的起始索引，默认为 0。
hi（可选）：查找的结束索引，默认为 len(a)。

示例：

总结对比

共同点：

都用于在有序列表中查找插入位置，使得新元素插入后列表仍然有序。
都可以通过 lo 和 hi 参数限定查找的范围。

不同点：

bisect_left 返回插入位置是在现有相等元素的左边（前面）。
bisect_right 返回插入位置是在现有相等元素的右边（后面）。

使用 bisect_left 或 bisect_right 可以根据需求精确控制新元素插入位置，使得列表保持有序的同时满足特定的顺序要求。

2 前缀和

💡

可以理解为数列里的前n项和，可以在O(1)复杂度内求得任意连续区间内数字的总和，预处理的时间复杂度为O(n)，只需要预处理一次

💡

下标从1开始，可以无须特判第一个元素

2.1 一维前缀和

基于accumulate实现前缀和：

一维前缀和习题：523. 连续的子数组和

2.2 二维前缀和

二维前缀和习题：304. 二维区域和检索 - 矩阵不可变

3 差分

💡

可以看作是前缀和的逆运算，用于在O(1)时间内给一个连续区间加上或减去同一个数。需要在操作完成后用O(n)时间内用前缀和操作计算和数组，只需要计算一次

💡

差分操作的是原数组，我们需要的是和数组，故最后需要用前缀和将原数组恢复成和数组，如果原本给出的就算和数组，那我们需要反推回原数组再进行差分

3.1 一维差分

一维差分习题：1094. 拼车

请思考，如果车上每天每站都会有固定乘客，应该如何修改你的程序

3.2 二维差分

二维差分习题：6292. 子矩阵元素加 1

4 双指针

💡

利用单调性，将双重循环优化到线性复杂度

💡

常见问题分类： (1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

4.1 双指针代码模板

双指针习题(请分别用二分和双指针实现)：167. 两数之和 II - 输入有序数组

5 离散化

💡

离散化一个序列的前提是我们只关心这个序列里面元素的相对大小，而不关心绝对大小（即只关心元素在序列中的排名）；离散化的目的是让原来分布零散的值聚集到一起，减少空间浪费。