有些问题，我们找不到"一步到位"的巧妙解法，只能把所有可能都试一遍。比如：8 个皇后怎么摆在棋盘上互不攻击？一个数独怎么填？面对这类问题，回溯（backtracking） 就是那把"系统地穷举"的工具。它不是瞎试，而是一条路走到黑，发现走不通就立刻回头换一条，并且用"剪枝"提前砍掉注定失败的分支。这一课，我们掌握回溯的套路，理解它和 DFS（第 14 课）、DP（第 17 课）的关系。一、回溯 …
先看一个经典问题：爬楼梯。每次可以走 1 级或 2 级，问爬到第 n 级有多少种走法？一个直觉的解法是递归（第 9 课学过）：def climb(n):
if n <= 2:
return n
return climb(n-1) + climb(n-2)
print(climb(5)) # 8看着很优雅，但它有个致命问题：大量重复计算。算 climb …
导航软件怎么算出从你家到机场的最快路线？地图上成千上万条路，它不可能每条都试一遍。答案藏在两个算法里：Dijkstra 算法（算最短路径）和它背后的思想——贪心（greedy）。这一课，我们认识"贪心"这种最直白的算法策略，并用它推导出 Dijkstra 最短路径算法——这是导航、网络路由、游戏 AI 寻路的底层机制。一、贪心是什么：每一步都挑眼前最好的贪心策略：在每一步，都做出当前看起来最优 …
前面几课，我们处理数据的方式大多是"一次性算完"：读进去，算一遍，吐结果。但现实里有一大类问题，是边读边变、边走边看的——你处理到第 5 个字符时的行为，取决于前 4 个字符是什么。比如：你要判断一个字符串里有没有连续的 "ab"。看到 'a' 时你心里想"下一个是 'b' 吗？"，看到 'b' 时想"上一个是不是 …
从这一课起，我们进入第三个阶段：并发与同步。前面我们认识了进程、线程这些"演员"，现在要回答一个更现实的问题：舞台上只有一块 CPU，几十个"演员"都想上，该让谁上、上多久？ 这个"排班"的工作，就交给CPU 调度。从"为什么感觉程序在同时跑"说起你同时开着浏览器、音乐、编辑器。可你的电脑可能只有一个 CPU 核。一个核，同一时刻只能跑一个进程——那凭什么你觉得它们"同时在跑"？答案是：CPU …
前面几课，我们认识了进程、线程、fd、fork/exec、信号。但你有没有发现一个问题：这些"孤岛"之间，怎么交换数据？ 进程 A 算出一个结果，进程 B 怎么才能拿到？这一课，我们就来解决进程之间"说话"的问题——进程间通信（IPC，Inter-Process Communication）。从"ls | wc"说起你在终端敲下：ls | wc -lls 列出当前目录的文件，wc -l 数一数 …
到目前为止，我们学的结构都是一条线（数组、链表）或一棵树（二叉树）。但现实里很多东西是网状的：社交网络：A 关注 B，B 关注 C，C 又关注 A……城市地图：道路把一个个路口连起来，能绕圈网页链接：页面互相指向，构成一张巨大的网这些"节点 + 任意连线（可以有环）"的结构，就是图（graph）。它是最通用的数据结构——链表和树，都只是图的特例。这一课，我们学图怎么存、怎么遍历，掌握 BFS …
想象一个场景：医院急诊室。病人源源不断地来，但病情重的必须先看，不能简单按先来后到排队。你需要一个数据结构，它能做到——随时把"最急的那个"拎出来，新病人来了随时插进去。这个"永远知道谁最大/最小"的数据结构，就是堆（heap）。它是优先队列（priority queue）的实现方式，也是很多算法（topK、Dijkstra、任务调度）背后的功臣。一、优先队列是什么：会"插队"的队列第 2 课 …
前面学的数组、链表、栈、队列、哈希表，数据都是"一条线"排开的。但现实里很多东西天生是分叉的：公司组织架构：一个 CEO 下面一堆 VP，每个 VP 下面又带几个总监……文件夹结构：一个目录里有子目录，子目录里还有子目录……网页的 HTML：<body> 里套 <div>，<div> 里又套 <p>……这些"一个上级、多个下级"的结构，用一条线表 …
想象一个游戏：我心里想一个 1 到 100 之间的数，让你猜，我只能回答"大了""小了""对了"。你怎么猜最快？绝大多数人第一次会从 1 开始：1？2？3？……最倒霉要猜 100 次。聪明人这么猜：先猜 50。"大了"→ 说明在 1~49，"小了"→ 说明在 51~100。每次猜中间那个数，每猜一次，范围砍掉一半。100 个数，最多 7 次就锁定答案。这个"每次砍一半"的策略，就是二分查找（b …
- « 前一页
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 后一页 »