计算机

编写一个爬虫的思路,当遇到反爬时如何处理

本站/公众号不误正业好久了,今天终于写一篇爬虫的文章,然而并没有案例,也没有代码。

写了这么多年爬虫了,经常还是会撞上反爬机制。虽然大多数时候都能解决,但是毕竟反爬机制多种多样,有时候遇到一个许久不见的反爬机制,也会感到手生,一时想不上来应对方法,而浪费不少时间。最近写了不少爬虫,接下来一段时间又不写了,趁着手还比较熟,记录一下备忘,方便大家也方便自己。

之前写过一篇常用的反爬虫封禁手段概览, 但是主要是从反爬的角度来的,这篇主要从写爬虫的角度来说说。

开章明义,当遇到反爬机制时,想要做到把数据爬下来,无非四个方法:

  1. 加代理
  2. 降速度
  3. 破解接口
  4. 多注册几个账户

好多文章为了显示自己高大上,吹些什么高并发呀,分布式,机器学习破解验证码的幺蛾子,都是扯淡。与其扯这些东西,不如老老实实把数据爬下来才是王道,如果非要扯上一些 fancy 的东西,那把监控做好比啥都重要

补充说明一下,本文探讨的是数据收集型的小型爬虫,也就是你要对少数站点在较短时间内收集大量信息。而非搜索引擎型全网爬虫,即对大量站点在较长时间内收集综合信息。(全网当然要上高并发了)

为什么说爬虫不要扯高并发?

我们知道计算机程序按瓶颈不同大概分为两类,CPU 密集型和 IO 密集型。CPU 密集型就是偏重计算的任务,比如说编解码啥的;IO 密集型就是偏重于网络的任务,比如说下载或者 web 服务器。那么爬虫是哪种呢?你估计要回答 IO 密集型,恭喜你答对了。但是这不是我想说的重点,重点是爬虫不光是 IO 密集型的任务,实际上我想把它称作 IP 密集型任务。

什么是 IP 密集型任务呢?按照上面的定义我们知道,也就是说,对爬虫来说,最瓶颈的地方其实是你持有的 IP 的数量!作为一个合格的爬虫编写者,你肯定已经擅长伪造各种 HTTP headers, 破解 JS 的加密参数,但是唯独一个 — 来源 IP — 你是无法伪造的。好多看起来很难搞的事情,如果对方站点的小霸王服务器撑得住,只要加上足够的 IP 就很简单啦,不用绞尽脑汁去想各种策略了。

为什么不要用现成的框架?

上面说了,所谓的”高并发”对爬虫没有任何卵用,那么像是 Scrapy 这种采用了协程以便提高并发的框架我就不是很懂了。以前我专门写过一篇为什么不要用 Scrapy 的文章,所以这里就不再展开细说了。

另外如果你爬虫写多了肯定有自己的一套东西了,这时候你可能会有自己的一个小框架,这是可以的。但是我还是想提两点:

  1. 千万不要做成从模板生成新的爬虫项目的功能。假如你改了模板里的一个 bug 怎么办?以前生成的爬虫还挨个修改吗?
  2. 框架尽量简单,把可以复用的功能提取成单独的 utility 函数或者库。难免有需要改框架或者不适用框架的时候,这时候依然可以复用单独的模块。

拿到抓取任务时的思路

言归正传,我们开始说当拿到一个站点需要爬取时该如何处理。

数据量较小的爬取

首先开始 easy 模式。如果你要抓的网站结构比较简单,而你要的数据也比较少。那么你首先要考虑的是不要编写爬虫. 在浏览器控制台里写个 js 表达式 console.log 一下说不定就把数据导出来了。

如果你要的数据稍微多一点时,这时候点开一个页面然后复制数据出来可能就比较复杂了。这时候可以考虑写个小脚本,别直接 while True 写个死循环就了事儿,每爬一个页面至少 time.sleep(1) 是对对方网站最起码的尊重。当然你的老板可能要数据比较急,但是多少也要悠着点。

浏览器动态加载怎么办?

初学者在这里可能遇到第一个坑:动态网页。这时候可能是个好事儿,也可能是个坏事儿。如果是动态网页,数据自然是 ajax 加载的,如果 ajax 请求没有参数验证的话,那么就简单了,只是从解析 html 变成了解析 json 而已。

另一种情况是接口是需要参数验证的,这时候又分两种处理方式:

  1. 如果只是爬一下数据,直接上浏览器,爬完了事儿。
  2. 如果嫌浏览器资源占用太多,那么往往就会需要破解接口,这种情况下需要一定的 JS 逆向能力。

有的网站对浏览器甚至还做了一些限制,他会检测你的浏览器是正常的用户浏览器还是用程序控制的自动化浏览器。不过这都不是问题,无非就是伪造一下 webdriver 对象和 navigator 对象罢了。这个我也写过一篇具体文章讲如何伪造。

当然这时候也可能遇到情况比较简单的特殊情况,那就是对方的某个更新接口是固定的,而且加密参数里面没有时间戳,那么直接重复请求这个接口就行了。一般来说这种情况算是”瞎猫撞见死耗子”, 多数情况下,接口的签名都校验了搜索的参数和时间戳,也就是你变换关键词,或者想重放请求的话是行不通的,这时候就老老实实破解吧。

一般破解 JS 其实也都不难,常用的信息摘要,或者加密方法也没多少。不过先别接着破解,花上五分钟搜索一下有没有别人已经破解过了,可能就省了你半天到几天的功夫,何乐而不为呢?

实在要开始破解的话,在 JS 的控制台中全局搜索 (Opt+Cmd+F) 一下 AES, MD5 之类的关键词,可能就有收获。另一方面在 ajax 请求上加上断点,逐步找到加密的函数。

找到加密函数之后,如果简单一点的,直接写在一个函数里的,可以抽取出来直接调用 node 执行算出参数,或者你比较勤快用 Python 重写一下都可以。然而比较棘手的是有些函数是和 window 对象或者 DOM 绑定在一起的,这时候也可以考虑把整个 JS 文件保存下来,补全需要的接口。

最常见的 IP 封禁

正如我们前面说的,作为一个爬虫老手,伪造和破解简单的加密都是基本功了,比较蛋疼的还是封禁 IP, 这你下什么苦功夫也没法解决的,是一个资本问题。

当我们爬取的速率比较快的时候,就可能被对方拉黑 IP, 这时候有可能是临时性拉黑,有可能是持续性拉黑,有可能是永久性拉黑。

永久性拉黑比较狠,也没啥办法,直接换 IP 吧。需要区分的是临时性的拉黑和持续性拉黑。如果是临时性拉黑,也就是你的请求超过阈值了就会请求失败,但是过段时间自己又恢复了,那么你程序逻辑也不用改,反正就一直请求呗,总有数据的。如果是持续性拉黑就比较坑了,也就是说如果你被拉黑了还不停止请求,那么就一直出不了小黑屋,必须停下来 sleep 几秒。这时候你的程序的逻辑就需要适应这种机制。如果是单独的脚本还好,对于一些标准化的系统就需要考虑这些机制。

当我们需要换 IP 的时候,肯定不能手工去记得过几分钟换一下子 IP 了,那也太烦人了,一般是需要一个 IP 池子的。

代理 IP 按照质量和来源又分为几类:

  1. 比较垃圾的公用 IP
  2. 比较稳定的机房 IP
  3. 民用网段 IP

网上有一些站点会提供一些免费的代理 IP, 估计他们都是扫来的。这些 IP 可能都有无数的程序在扫描,使用他们,所以可以说是公用的 IP 了。通过收集验证这些 IP, 可以构造一个代理池子。如果实在很穷,或者抓取量不是很大,可以用这种 IP. 虽然这些 IP 特别慢,失败率特别高,总比用自己的一个出口 IP 要好一些。

比较稳定的机房 IP. 这种一般就需要花钱买了,稍微想多抓点数据,一个月 100 那是起步。对付大多数的抓取已经足够了。

对于有一些变态的站点,他们甚至会验证来源 IP 的用途。比如说一看你 IP 来自阿里云机房,啥也不说直接拉黑。这时候就需要所谓的”民用 IP”了。这种有专门的厂商和 App 合作来提供民用网络出口,也可以自己买 ADSL 机器自动拨号搭建,反正成本都是非常非常高了,一个月至少 1000 起步了。

带上账户或者验证码

IP 毕竟算是匿名的。对于一些数据更敏感的网站来说,他们可能要求你登录后才能访问。如果数据不多,那么直接用自己账户跑一下就完了。如果每个账户的访问额度有限,或者要爬的数据特别多,那可能需要注册不少账户,这时候只要不是付费账户,那么其实都好说(除了微信). 你可以选择:

  • 买一些账号,比如说微博账号也就一块半一个而已。
  • 自己注册一些,网上有免费邮箱,也有手机短信接码平台。

这时候不要急着去写个脚本自动化注册啥的,可能你并不需要那么多的账户。

比需要账户稍微弱一点的限制是验证码,图文验证码现在都不是问题了,直接打码平台或者训练个模型都很简单。复杂一点的点按,图片选字等就当饭后甜点吧,弄得出来弄不出来全看运气了。在这里我想说的一点是,请分辨一下你要爬的网站是每次请求必须验证码,还是在封禁 IP 之前出验证码。如果不是每次请求都出验证码,直接加大代理池吧,没必要抠这些东西,真的,时间才是最宝贵的。

不过这里需要特别注意的一点是:一定要考虑清楚其中的法律风险,需要账户访问已经说明这不是公开数据了,可能会触发对方的商业利益或者触犯用户的隐私,一定三思而后爬。

事情没那么简单

如果一个网站只采用一种手段,那么我们分析起问题来就简单了。然而遗憾的是,基本没这种好事儿。比如说一个网站可能即检测了浏览器的 webdriver, 而且还要封 IP, 这时候你就得用浏览器再加上代理,有时候给浏览器设置代理这件事情还挺复杂。还有可能你用账户 Cookies 爬起来飞快,但是竟然还会封 IP, 哼哧哼哧加上了代理池,又发现账户不能换登录 IP, 简直想骂人。

还有一些神仙网站,比如说淘宝或者裁判文书网,可能本文说的都完全没有任何价值,不过好在我大概不会碰这些网站了。

选哪些接口爬

其实我发现一般常见爬虫任务无非几种:

  1. 找到网站的一个列表,把里面数据全都爬下来。
  2. 自己弄些 id 或者关键词,通过查询或者搜索接口把数据全都爬下来。
  3. 刷网站的一些更新或者推荐接口,以期不断抓取。

首选的肯定是无状态的接口,搜索接口在大多说网站还是可以直接就拿来用的。如果有需要登录的,也有不需要登录的接口,那想都不用想,肯定爬不需要登录的接口。哪怕登录了,好多还是会封 IP, 何必呢?有些网站的详情或者翻页可能就需要登录了,实在没办法也只能走这些接口。这时候一定要做好登录出口和普通爬虫的代理池隔离。

要判断清楚爬虫任务是爬全量数据还是增量数据。一般来说爬全量数据的需求都有点扯,一定要和需求方 argue 一下,可能对方根本就没想清楚,觉得先把数据存下来然后慢慢再想怎么用,对于这种傻 X 需求一定要顶回去,别急着跪舔或者炫技。如果一定要爬全量,那也可以慢慢来,不用非着急忙慌的把对方网站都搞挂了,这并不是啥值得炫耀的,而是应该被鄙视。而且一般网站也不会把全量数据让你都能看到,比如可能只能翻 500 页,这时候只能通过细分查询条件来尽可能多地获得一些数据。增量的话一般就好说一点,就像上面说的,定时刷一下更新或者推荐接口就好了。

要爬 App 吗?一般来说现在的网站还是有足够的数据的,除非是一些只有 App 而没有网站的站点,那就没办法了。App 的破解和 JS 其实思路一样,但是可能好多 App 加了壳,或者把加密算法写到了 C 里面,相比 JS 来说,完全不是一个数量级了。对于 App 的破解我基本一窍不通,也就是靠写一些网页爬虫混口饭吃。

你应该庆幸的一点是,你需要写的只是一个爬虫,而不是发帖的机器人,一般网站对于这种制造垃圾数据的防范机制肯定比爬虫要复杂很多。

这里再次特别强调一下:破解别人的 App 可能是非法行为,需要法律责任。

最后,总结一下

所以总结下来,我觉得遇到一个网站的需要考虑的思路是:

  1. 预估下需要爬的数据和时间节点,算出来每秒需要爬多少数据。别上来就设计个啥架构,八成根本用不上。
  2. 如果需要的速率比较小,那么直接 time.sleep(5) 慢慢跑着,也就是尽量不要触发封禁。
  3. 尽量找到一个公开的,不需要登录就能访问的接口或者页面,直接上代理池,别想那么多别的。
  4. 能从一个接口拿到的数据,不要再去多请求其他的接口,尽量减少访问量。
  5. 能很快破解的 JS 也可以破解一下,比较复杂的直接上浏览器,浏览器就直接做好伪装,省得出问题。
  6. 需要登录认证的一定要考虑 Cookie 异地失效的问题,最好使用单独的高质量 IP. 做一套路由机制,保证每个 Cookie 都从同一个 IP 出去。

总之,一次解决一个问题,不要同时触发两个反爬问题,容易按下葫芦起了瓢。

就是这些吧,本文核心观点 — 最简单粗暴的还是加大电量(误加 IP 池,如果一个不够,那就两个。加钱能解决的问题都不是问题。好多同学可能觉得你这叫哪门子爬虫啊,分布式系统也没有,最好玩的逆向你说去网上抄别人的答案,哪还有毛意思啊!然而,很遗憾,这才是现实世界,对于业务来说,爬虫最重要的是你拿到有用的数据,而不是写代码写牛逼了,有这时间回家陪陪家人不好么~

参考文献

本文没有任何参考文献,纯意识流瞎写。文中引用了之前写的几篇文章,懒得贴了,感兴趣自己在网站或者公众号找吧。

PS: 监控很重要,爬虫最怕跑着跑着对面改版了或者加反爬了,有了监控才好及时发现问题。关于监控,强烈推荐 Prometheus, 可以参考我以前的文章。

sche – 一种人类能够看懂的 cron 语法

在 Linux 系统上,我们一般使用 cron 来设置定时任务,然而 cron 的语法还是有些佶屈聱牙的,几乎每次要修改的时候都需要查一下文档才知道什么意思,以至于有 crontab.guru 这种网站专门来解释 cron 的语法。

想象一下,能不能有一种让人一眼就能看懂的语法来表达周期性的调度操作呢?比如说这样:

every 10 minutes         , curl apple.com
every hour               , echo 'time to take some coffee'
every day at 10:30       , eat
every 5 to 10 minutes    , firefox http://news.ycombinator.com
every monday             , say 'Good week'
every wednesday at 13:15 , rm -rf /
every minute at :17      , ping apple.com
every 90 minutes         , echo 'time to stand up'

这样的配置文件是不是很容易懂呢?如果要写成 crontab 的格式大概是这样的:

*/10 * * * *    curl apple.com
0 * * * *       echo 'time to take some coffee'
30 10 * * *     eat
*/7 * * * *     firefox http://news.ycombinator.com  # 实际上是不对的,因为 cron 没法随机
0 0 * * MON     say 'Good week'
15 13 * * WED   rm -rf /
# every minute at :17  无法实现,因为 cron 中没有秒
0 0-21/3 * * *  echo 'time to stand up'  # 需要两条命令来完成每隔 90 分钟的操作
30 1-22/3 * * * echo 'time to stand up'

可以很明显看出,cron 的语法可读性还是差一些的,关键是维护起来更是像读天书一样。幸运的是,我在周末刚刚做了一个小工具,虽然还比较粗糙,但是也已经可以解析上面这种可读性比较好的语法。下面简单介绍一下如何使用:

介绍 sche

sche 是一个 Python 程序,所以可以使用 pip 直接安装:

pip install sche

安装之后,就会得到一个 sche 命令,帮助文件如下:

-> % sche -h
usage: sche [-h] [-f FILE] [-t]

A simple command like `cron`, but more human friendly.

The default configuration file is /etc/schetab, syntax goes like:

    # (optional) set time zone first
    timezone = +0800

    # line starts with # is a comment
    every 60 minutes, echo "wubba lubba dub dub"

    # backup database every day at midnight
    every day at 00:00, mysqldump -u backup

    # redirect logs so you can see them
    every minute, do_some_magic >> /some/output/file 2>&1

optional arguments:
  -h, --help            show this help message and exit
  -f FILE, --file FILE  configuration file to use
  -t, --test            test configuration and exit

我们只需要把需要执行的命令放到 /etc/schetab 文件下就好了,这里显然是在致敬 /etc/crontab。比如说:

-> % cat /etc/schetab
timzone = +0800
every 5 seconds, echo "wubba lubba dub dub"
every 10 seconds, date

-> % sche
wubba lubba dub dub
Tue Sep  1 22:15:01 CST 2020
wubba lubba dub dub
wubba lubba dub dub
Tue Sep  1 22:15:11 CST 2020
wubba lubba dub dub
wubba lubba dub dub
Tue Sep  1 22:15:21 CST 2020
wubba lubba dub dub

如何让 sche 像 cron 一样作为一个守护进程呢?秉承 Unix 一个命令只做一件事的哲学,sche 本身显然是不提供这个功能的,可以使用 systemd 实现,几行配置写个 unit 文件就搞定了。

sche 的来源

sche 是 schedule — 另一个 Python 库的一个 fork, schedule 支持这样的 Python 语句:

schedule.every(10).minutes.do(job)
schedule.every().hour.do(job)
schedule.every().day.at("10:30").do(job)
schedule.every().monday.do(job)
schedule.every().wednesday.at("13:15").do(job)
schedule.every().minute.at(":17").do(job)

然而我的需求是把时间配置独立出来,能够像 cron 一样存到一个文本文件里,而不是写成 Python 代码,于是提了一个 PR,增加了 when 这个方法来解析表达式。同时我还强烈需求时区支持,然而原版的 schedule 也不支持。所以就创建了一个 fork.

sche.when("every wednesday at 13:15").do(job)
sche.timezone("+0800").every().day.at("00:00").do(job)

最后,原生的 cron 命令实际上(至少我)已经极少用了,然而 crontab 的语法流传还是非常广的,在所有需要定时任务的地方,几乎都能看到 cron 的身影,比如说 Kubernetes job 等等,如果能够使用一种让正常人能随时看懂的语法,感觉还是很有意义的。

参考

  1. https://schedule.readthedocs.io/en/stable/
  2. https://crontab.guru/
  3. https://stackoverflow.com/q/247626/1061155

Python 3 中的 dataclass

在 Python 中,如果要为一个类添加一些数据成员的话,需要做的事情还挺多,比如说编写 __init__,
__str__ 这些函数,代码都是重复的,没啥意义。在 Python 3.7 中,终于添加了一个语法糖,叫做
dataclass. 下面我们就来看一下吧~

# 注意!包名叫 dataclasses, 多了个 es
from dataclasses import dataclass

@dataclass
class InventoryItem:
    """Class for keeping track of an item in inventory."""
    name: str
    unit_price: float
    quantity_on_hand: int = 0

    def total_cost(self) -> float:
        return self.unit_price * self.quantity_on_hand

上面的代码就相当于以前的:

def __init__(self, name: str, unit_price: float, quantity_on_hand: int=0):
    self.name = name
    self.unit_price = unit_price
    self.quantity_on_hand = quantity_on_hand

def __repr__(self):
    ...

def __eq__(self):
    ...

...

我们知道,在 Python 的默认参数中,使用 mutable(可变) 的对象是一种常见的坑,在 dataclass 中当然也存在
了,还好标准库中给我们提供了一个方法。

# 会报错
@dataclass
class Request:
    headers: dict = {}

# 相当于
class Request:
    def __init__(self, headers={}):
        self.headers = headers


# 正确的写法
from dataclasses import field

@dataclass
class Request:
    headers: dict = field(default_factory=dict)

字典这种类型是比较容易想起来不能直接做参数的,比较坑的是对于其他的自定义对象,Python 解释器并不会提
示有问题,比如说这样:

# 千万别这么做
@dataclass
class Request:
    headers: Headers = Headers()

这时候坑爹的事情就发生了,每次创建新的 Request 对象引用的都是同一个 Headers 对象,也就是在声明这个类
的同时产生的这个 Headers 对象!原因也很简单,就像是上面的 dict 一样,这个 Headers 并不是在 init 函数
中,所以只会产生一次。所以,需要牢记的是:dataclass 中的所有对象默认值就相当于函数的默认参数,永远不
要传递一个 mutable 就好了。

# 上面的例子相当于
class Request:
    def __init__(self, headers=Headers()):
        self.headers = headers

# 正确的做法
@dataclass
class Request:
    headers: Headers = field(default_factory=Headers)

dataclasses 模块中还提供了 asdict 方法,这样就可以方便地转换为 json 对象啦。

from dataclasses import asdict


@dataclass
class Request:
    url: str = ""
    method: str = ""

req = asdict(Request())

参考资料

  1. https://docs.python.org/3/library/dataclasses.html

刷 LeetCode 的经验

最近断断续续面试了三个月,也拿了一些大厂(美团百度阿里)的 offer, 分享下刷题经验

  • 一定要使用自己最擅长的语言,不要想其他的,不要引入额外的复杂度;
  • 复习基础算法,如排序,二分查找,树的遍历等,同时做一些基础题;
  • 简单的递归,比如树的一些题目,是最容易引导你进入刷题状态的;
  • 递归是几乎所有有技巧的题目的基础,栈是递归、树是递归、回溯也是递归、动归更是递归;
  • 除了递归之外,剩下的基本是考察基础操作的题目,比如螺旋打印矩阵等等,一定要注意细节;
  • 每道题 10 分钟完全没思路就看答案;
  • 如果连续有 5 道题目看答案了,去补习知识,不要再做了;
  • 代码超过 20 行了,一般情况下说明写的有问题,直接看答案(确实有个别非常繁琐的题目,面试一般不考);
  • 开始的时候按分类刷,不要按顺序刷;
  • 如果遇到完全没有思路的题目,不要悲伤,不要觉得自己是个傻瓜。秉承「闻过则喜」的态度,试想如果是面试时候恰好考到这道题目呢?
  • 刷过了过几天又忘了也没关系,根据艾宾浩斯记忆曲线,前几天是忘得最快的时候,多看几遍;
  • 当然,死记硬背是没用的,一定要理解题目;
  • 做题的时候身边要有白纸,随时在纸上画下示意图,不要空想;
  • 做了几道同类题之后,总结做题模板,比如说 backtracking 的做题模板;
  • 后期刷熟了,不要分类刷,随机刷;
  • 已有的题库就当做例题,反复看,彻底学透。每周参加周赛,做新题,作为模拟面试。

最后一点,刷 LeetCode 其实就像是大学里的期末考试,如果你两周复习时间可以搞定一门期末考试,那么两周时间也完全能搞定 LeetCode。要做到「战略上藐视,战术上重视」。

按照考察的方面,题目大概分成两类:

  1. 递归;
  2. 其他题目。

对于递归题目,拿到题目首先要思考:

  1. 怎么才能把题目的输入规模缩小,简化为规模更小的问题
  2. 另一方面基础情形是什么

然后再考虑选用哪种实现方式,是回溯还是动归。

特别注意的地方

  • 不要沉迷于研究语言特性。

    就像上面说的,使用自己最熟悉,日常使用最多的语言。不要觉得 C++ 或者 Java 或者 Whatever 刷题最爽,或者你看的答案采用了什么语言,抓住主要矛盾,你是来刷题的,不是学习新语言的。我之前犯得错误就是边学 Rust 边刷题。

  • 不要沉迷于数论

    LeetCode 上有一些涉及到数论的题目,但是代码面试不是 ACM, 也不是你的大学期末考试。最多熟悉一下排列组合算法、全排列和欧几里得算法就行了,不要沉迷于数论。

  • 要总结自己的特殊问题

    说了这么多,都是共性的问题,但是每个人都会有自己特殊的问题。比如说我的问题就在于不太敢用字典,总觉得会让人感觉投机取巧,我一个工作四年的人,肯定是知道字典的,但是做算法题的时候总在潜意识里避免使用。实际上 LeetCode 第一题就用到了字典。

面试刷题总结(十)- 指针类题目与窗口

链表的指针题目

一般使用 dummy head 的话,循环条件是 while p.next, 而不使用的话,则是 while p.

递归反转列表

int reverseList(ListNode node) {
    if (node == null || node.next == null) {
        return node;
    }
    ListNode head = reverseList(node.next);
    node.next.next = node;
    node.next = null;
    return head;
}

都比较简单,主要是细节的使用。

  • LeetCode 24
  • LeetCode 25
  • LeetCode 206

参考资料

  1. https://mp.weixin.qq.com/s/YFe9Z35CE4QWPDmPNitd4w

前缀和

前缀和这个概念可以说是「会者不难,难者不会」,概念本身是很简单的,但是如果不知道的话,好多题就两眼一抹黑了。前缀和即为数组从 0 到当前位置的和,类似的概念还有后缀和,前缀积,后缀积等。

presum[0] = A[0]
presum[i] = presum[i-1] + A[i]

例题

求数组中绝对值最小的子数组

利用前缀和的性质:A[i] + A[i+1] + ... + A[j] = presum[j] - presum[i-1] 前缀和排序,取差值最小值。

有一道题,求两个时间之间的差值,其实是类似的。当差值直接累加计算不好求的时候可以转换为前缀和的差。

把一个数组从中间 p 位置分开,使得 a[0]+…+a[p-1] 与 a[p]+a[p+1]+…+a[n-1] 差值最小?

也就是使得:presum - (total - presum) = 2 * presum - total 最小。

参考资料

  1. https://www.cnblogs.com/AndyJee/p/4474073.html

面试刷题总结(六)-栈和队列

栈本身是一种特别简单的数据结构,这里就不多说了,主要记录一些以前不会的题目。

单调栈

单调栈就是满足单调性的栈。比如递增的栈,如果新的元素比栈顶的元素小的话,就要一直弹出,直到找到满足条件的栈顶,然后再入栈。

单调队列

单调队列使用两个队列组成。其中一个是普通的队列,另一个是维护大小顺序的队列。这里的队列不是严格的队列,而是可以从尾部弹出的双端队列。

from collections import deque

class MonoQueue:
    def __init__(self):
        self.q = deque()  # 实际储存数据
        self.m = deque()  # 维护单调关系,队首元素总是最大值

    def push(self, x):
        self.q.append(x)
        while len(self.m) > 0 and self.m[-1] < x:
            self.m.pop()
        self.m.append(x)

    def pop(self):
        x = self.q.popleft()
        if self.m[0] == x:
            self.m.popleft()
        return x

    def __len__(self):
        return len(self.q)

    def top(self):
        return self.m[0]

例题

单调队列的题目

  • LC84. Largest Rectangle in Histogram
  • LC239. Sliding Window Maximum
  • LC739. Daily Temperatures
  • LC862. Shortest Subarray with Sum at Least K
  • LC901. Online Stock Span
  • LC907. Sum of Subarray Minimums

POJ3250 Bad Hair Day

有 N 头牛从左到右排成一排,每头牛有一个高度 h[i],设左数第 i 头牛与「它右边第一头高度 >= h[i]」的牛之间有 c[i] 头牛,试求 sum(c[i])。

这道题使用单调栈做。

def sum_distance(H):
    ans = 0
    stack = []
    for h in H:
        # 单调递减的栈
        while stack and stack[-1] < h:
            stack.pop()
        ans += len(stack)
        stack.append(h)
    return ans

参考资料

  1. https://oi-wiki.org/ds/monotonous-stack/
  2. https://www.hankcs.com/program/algorithm/poj-3250-bad-hair-day.html
  3. https://oi-wiki.org/ds/monotonous-queue/
  4. https://oi.men.ci/monotone-queue-notes/

小技巧

时间复杂度需要优化

如果你的算法和预期的时间复杂度还差一些数量级,那么考虑下是不是某个操作可以转化成 hash 查表,这样这个操作就是 O(1) 了。

如何证明算法正确

一般使用归纳法。

UnionFind 算法

unionfind 算法是用于计算图中的节点连通性的算法。其中连同的意思是满足『自反』『对称』『传递』三个意思的连通。

class UnionFind:
    def __init__(self, count):
        self.count = count
        self.parents = list(range(count))  # 初始化时 parent 指针指向自己

    def union(self, p, q):
        """把 p, q 两个节点连通起来"""
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        self.parents[p_root] = q_root
        self.count -= 1

    def find(self, p):
        """找到 p 节点的根节点"""
        while self.parents[p] != p:
            p = self.parents[p]
        return p

    def is_connected(p, q):
        p_root = self.find(p)
        q_root = self.find(q)
        return p_root == q_root

在上面的算法中,我们发现 union 和 is_connected 主要依赖于 find 的时间复杂度。而在树极端不平衡的情况下,是可能退化到 O(n) 的,所以不优化的前提下,时间复杂度是 O(n)。

优化1 – 保持树平衡

class UnionFind:
    def __init__(self, count):
        self.count = count
        self.parents = list(range(count))  # 初始化时 parent 指针指向自己
        self.sizes = [1] * count  # 记录每棵树的大小

    def union(self, p, q):
        """把 p, q 两个节点连通起来"""
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        if self.sizes(p_root) > self.sizes(q_root):
            self.parents[q_root] = p_root
            self.sizes[p_root] += self.sizes[q_root]
        else:
            self.parents[p_root] = q_root
            self.sizes[q_root] += self.sizes[p_root]
        self.count -= 1

经过这个优化之后,时间复杂度就降到 O(logN) 了。

优化2 – 路径压缩

在调用 find 函数的时候,把

class UnionFind:
    def find(self, p):
        """找到 p 节点的根节点"""
        while self.parents[p] != p:
            # 神奇的路径压缩
            self.parents[p] = self.parents[self.parents[p]]
            p = self.parents[p]
        return p

Go 语言实现

type UnionFind struct {
    count int,
    parents []int,
    sizes []int
}

func NewUnionFind(n int) (*UnionFind) {
    parents := make([]int, n)
    sizes := make([]int, n)
    for i := 0; i < n; i++ {
        parents[i] = i
        sizes[i] = 1
    }
    return &UnionFind{n, parents, sizes)
}

func (uf *UnionFind) Union (p, q int) {
    pRoot := uf.Find(p)
    qRoot := uf.Find(q)
    if pRoot == qRoot {
        return
    }
    if uf.sizes[pRoot] < uf.sizes[qRoot] {
        uf.parents[pRoot] = qRoot
        uf.sizes[qRoot] += uf.sizes[pRoot]
    } else {
        uf.parents[qRoot] = pRoot
        uf.sizes[pRoot] += uf.sizes[qRoot]
    }
    uf.count -= 1
}

func (uf *UnionFind) Find(p int) int {
    while uf.parents[p] != p {
        uf.parents[p] = uf.parents[uf.parents[p]]
        p = uf.parents[p]
    }
    return p
}

func (uf *UnionFind) IsConnected(p, q int) bool {
    pRoot := uf.Find(p)
    qRoot := uf.Find(q)
    return pRoot == qRoot
}

LeetCode 题目

LeetCode 200 岛屿的数量

这个题就很简单了,简直是 UnionFind 的直接应用。

  1. Union-Find 并查集算法详解

面试刷题总结(五)- 贪心算法

天字第一条:永远不要首先尝试贪心算法,并尝试证明它是对的。而要使用动态规划推出一个算法,然后可以尝试简化到贪心算法。

尤其是在面试中,基本不会出现贪心算法,太 tricky 了。如果一个面试官问了一个题目,并且他只会用贪心算法解,那么这个面试官水平也一般,这样的公司不去也罢。

相比动态规划来说,贪心算法一般来说:

  1. 要求条件更严格,也就是贪心选择条件;
  2. 时间复杂度往往更低,能达到线性时间复杂度。

贪心选择性质:每一步都选择局部最优解,而局部最优解恰好是全局最优解。贪婪一般需要预排序,证明贪婪成立可以采用数学归纳法,或者证明不会有更好的方法

区间问题

合并、排序区间也是一个常见的问题。

例题

LeetCode 56

LeetCode 57 合并区间

这道题关键之处在于合并后,把剩余的区间直接加上来,这样就不用考虑不少特殊情况了。

class Solution:
    def insert(self, intervals, newInterval):
        ans = []
        start, end = newInterval
        remainder = 0
        for x, y in intervals:
            if start <= y:
                if end < x:
                    break  # 找到了结尾了
                start = min(start, x)
                end = max(end, y)
            else:
                ans.append([x, y])
            remainder += 1
        ans.append([start, end])
        ans += intervals[remainder:]
        return ans

会议室 II

LeetCode 矩形重叠问题

参考资料

  1. 面试不会考贪心算法