鸽巢原理
鸽巢原理
-
如果有n+1个鸽子飞进了n个鸽巢中，那么必定有鸽巢中至少飞进了2只鸽子。
-
常被用于证明存在性证明，和求最坏情况下的解。
-
存在性证明：连最坏情况都不存在解，所以情况也就肯定不存在解。
证明
将 n+1 个苹果，放到 n个抽屉中，那么有至少一个抽屉有两个（或以上）的苹果。
这个定理看起来比较显然，证明方法考虑反证法：
假如每个抽屉有最多 1 个苹果，那么最多有 n 个苹果，而实际上有 n+1个苹果，矛盾。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 笺札！
相关推荐
2025-11-10
单调栈
单调栈算法 123 单调栈是一种特殊的数据结构，分为单调递增栈和单调递减栈，保证元素从栈顶到栈底的单调性。单调栈常用于在O(n)O(n)O(n)的时间复杂度内寻找序列中某些元素的相邻元素，如左侧第一个更大/更小的元素等。 单调递增栈 单调递增栈的特点是从栈顶到栈底的元素是单调递增的。只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈。这样就保证了栈中保留的都是比当前入栈元素大的值。 代码示例 1234567891011121314def monotoneIncreasingStack(nums):stack = []for num in nums:while stack and num >= stack[-1]:stack.pop()stack.append(num)return stack 单调递减栈 单调递减栈的特点是从栈顶到栈底的元素是单调递减的。只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。这样就保证了栈中保留的都是比当前入栈元素小的值。 代码示例 12345678910...
2025-11-20
快速幂
快速幂(参考OI Wiki) 背景 计算 𝑎 的 𝑛 次方表示将 𝑛 个 𝑎 乘在一起：𝑎𝑛 =𝑎×𝑎⋯×𝑎(𝑛 个a)𝑎^𝑛 =𝑎×𝑎⋯×𝑎(𝑛 个a)an =a×a⋯×a(n 个a)。然而当 𝑛 太大或单次乘法开销太大的时侯，这种方法就不太适用了 基本思想 将取幂的任务按照指数的 二进制表示 来分割成更小的任务。 具体实现 迭代版本 设 𝑛 的二进制表示为 (𝑛𝑡𝑛𝑡−1⋯𝑛1𝑛0)2(𝑛_𝑡𝑛_{𝑡−1}⋯𝑛_1𝑛_0)_2(ntnt−1⋯n1n0)2，也就是说，有 𝑛=𝑛𝑡2𝑡+𝑛𝑡−12𝑡−1+⋯+𝑛121+𝑛020𝑛=𝑛_𝑡2^𝑡+𝑛_{𝑡−1}2^{𝑡−1}+⋯+𝑛_12^1+𝑛_02^0 n=nt2t+nt−12t−1+⋯+n121+n020 其中，𝑛𝑖 ∈{0,1}。那么，就有 𝑎𝑛=𝑎𝑛𝑡2𝑡+𝑛𝑡−12𝑡−1+⋯+𝑛121+𝑛020𝑎^𝑛=𝑎^{𝑛_𝑡2^𝑡+𝑛_{𝑡−1}2^{𝑡−1}+⋯+...
2026-10-12
1141. 查询近30天活跃用户数
1141. 查询近30天活跃用户数 难度：简单 | 题号：1141 | 链接：1141. 查询近30天活跃用户数 - 力扣（LeetCode） | 数据结构：SQL 关联：订单最多的用户（同为「按维度分组计数」）· 每月交易 I（同为日期函数 + 分组聚合）· 可对照 SQL原理_02（日期函数 / 分组聚合）。 🎯 问题描述 描述：写一条 SQL 查询，求出截至 2019-07-27（含）的近 30 天内，每天的活跃用户数。活跃用户指当天至少进行一次活动的用户，返回结果表的列名须为 day 和 active_users，且每天都可能出现重复用户（同一用户一天多次活动只算一次）。 表：Activity 1234567891011+---------------+---------+| Column Name | Type |+---------------+---------+| user_id | int || session_id | int || activity_date | date || activity_t...
2026-10-12
1193. 每月交易 I
1193. 每月交易 I 难度：中等 | 题号：1193 | 链接：1193. 每月交易 I - 力扣（LeetCode） | 数据结构：SQL 关联：查询近30天活跃用户数（同为日期函数 + 分组聚合）· 订单最多的用户（分组计数）· 可对照 SQL原理_02（日期格式化 / 条件聚合）。 🎯 问题描述 描述：写一条 SQL 查询，找出每个月、每个国家/地区的：① 交易总数；② 交易总金额；③ 已批准（state = 'approved'）的交易数；④ 已批准交易的总额。结果以任意顺序返回。 表：Transactions 123456789101112+---------------+---------+| Column Name | Type |+---------------+---------+| id | int || country | varchar || state | enum || amount | int || trans_date | date ...
2026-10-03
漏斗题
漏斗题 类型：自编场景题（漏斗转化）| 题号：— | 链接：— 关联：SQL原理_04（漏斗章节）· SQL分析场景模板 · 好友申请 II ：谁有最多的好友（同为列转行+聚合） 🎯 问题描述 表结构 1event_log(user_id, event_name, event_time) 事件名：view、cart、order、pay。 需求 统计从"浏览 → 加购 → 下单 → 支付"的漏斗人数。 要求每一步必须发生在第一步之后，即按时间顺序： 1view_time < cart_time < order_time < pay_time 输出：view_users、cart_users、order_users、pay_users。 说明：每个用户可能多次触发同一事件，需按最早时间归并成一行再比较顺序。 💻 解题思路 思路1：MIN(CASE WHEN) 归并 + 时间递增计数（用户解法） 核心逻辑 ① 子查询 person_log：按 user_id 分组，用 MIN(CASE WHEN event_name = 'xx'...
2026-10-12
1341. 电影评分
1341. 电影评分 难度：中等 | 题号：1341 | 链接：1341. 电影评分 - 力扣（LeetCode） | 数据结构：SQL 关联：订单最多的用户（同为「分组计数取 Top-1」）· 分数排名（同为「排名 / 并列处理」）· 部门工资最高的员工（分组最值）· 可对照 SQL原理_02（多表连接 / 排序 / UNION ALL）。 🎯 问题描述 描述：写一个解决方案，同时完成两件事： 找出评论电影数量最多的用户名。若并列，返回字典序较小的用户名。 找出 2020 年 2 月里平均评分最高的电影名称。若并列，返回字典序较小的电影名称。 返回结果表的列名为 results。 表：Movies / 表：Users / 表：MovieRating 12345678910+---------------+---------+ +---------------+---------+ +---------------+---------+| Column Name | Type | | Column Name | Type ...
