京公网安备11010502063487号给定一个未排序的整数数组，找出其中没有出现的最小的正整数，要求时间 O(n)、额外空间 O(1)。如果没有空间限制，用一个集合从 1 开始逐个查就行。要做到 O(1) 额外空间，需要把数组本身当作哈希表：长度为 n 的数组，答案一定落在 1 到 n + 1 之间，所以只关心 1
给定一排宽度为 1 的柱子的高度，计算下雨之后能接多少单位的雨水。每一格能存的水，等于它左边最高的柱子和右边最高的柱子里较矮的那个，减去它自己的高度（不足则为 0）。直接按定义算，每一格要扫描左右两边，是 O(n²)。这道题是经典的一题多解：前后缀最大值数组、单调栈、双指针。本文
给定两个用字符串表示的非负整数，返回它们乘积的字符串表示。题目禁止直接使用大整数类型，也不允许把输入直接转成整数相乘，所以要自己实现竖式乘法。做法是：结果最多有 m + n 位（m、n 是两个数的位数），用一个长度 m + n 的数组，让第一个数的第 i 位乘第二个数的第 j 位
给定一个字符串 s 和一个含有通配符的模式 p：`?` 匹配任意单个字符，`*` 匹配任意长度的字符串（包括空串），判断整个 s 是否被 p 完全匹配。它常见的解法是动态规划，O(nm) 时间和空间。还有一种贪心加回退的双指针做法，只用 O(1) 额外空间：遇到 `*` 先让它匹
给定一个非负整数数组，你站在下标 0，每个元素表示从这个位置最多能向前跳的步数，保证能到达最后一个位置，求到达末尾的最少跳数。动态规划是 O(n²)：`dp[j]` 是到达 j 的最少跳数，每个位置更新它能到的所有位置。更好的做法是贪心加"分层"：第 k 跳能到达的所有位置构成第
给定一个元素互不相同的数组，返回它的所有排列，顺序不限。这是回溯最经典的一题：每一层从还没用过的元素里选一个放进当前路径，路径长度达到数组长度就收集一份，返回时把这一步撤销。这道题的结果个数就是 n!，所以耗时主要由结果规模决定，而不是算法细节。本文用真实运行展示回溯里最常见的一
给定一个可能有重复元素的数组，返回所有不重复的全排列。相比上一题，多了去重：`[1, 1, 2]` 有 6 种排法，但只有 3 种不同的排列。做法是先排序，让相同的数挨在一起，然后规定：相同的数字必须按下标顺序使用，也就是当前的数字如果与前一个相同，而前一个在这一层还没被用过，就
给定一个 n × n 的二维矩阵，把它原地顺时针旋转 90 度，不允许另外开一个二维数组。最直接的想法是找出每个位置旋转后的落点，但落点的对应关系（`(i, j)` 到 `(j, n-1-i)`）很容易写错。更简洁的做法是把旋转拆成两次翻转：先沿主对角线转置，再把每一行左右翻转。
给定一个字符串数组，把互为字母异位词（字母相同、排列不同）的字符串分到同一组。核心问题是"怎么判断两个字符串是异位词"：把每个字符串的字母排序，异位词排序后完全相同，把这个排序后的字符串当作哈希表的键，同一个键下的字符串就是一组。另一种键是 26 个字母各自出现的次数。本文用真实
实现 `pow(x, n)`：计算浮点数 x 的整数 n 次方，n 可能是负数。逐个相乘要 n 次乘法，n 最大到 21 亿，太慢。快速幂的思路是把 n 写成二进制：x 的 n 次方等于若干个 x 的 2^k 次方的乘积，其中 k 是 n 的二进制里为 1 的那些位；而 x 的
把 n 个皇后放到 n × n 的棋盘上，使任意两个皇后都不在同一行、同一列、同一条对角线上，返回所有不同的摆法（每种摆法用 n 个字符串表示棋盘，`Q` 是皇后，`.` 是空位）。做法是回溯：一行放一个皇后，逐行往下放，每放一个之前检查它所在的列和两条对角线有没有被占。判断对角
上一题要求列出所有摆法，这一题只要求数出有多少种。既然不需要保存每种摆法，就可以把"哪些列、哪些对角线被占"压缩成三个整数位掩码：一位对应一列。每往下一行，两条对角线的影响各移动一位：`\` 方向的掩码左移一位，`/` 方向的右移一位。"当前行能放的位置"就是三个掩码的并集取反，