鸽巢原理
鸽巢原理
-
如果有n+1个鸽子飞进了n个鸽巢中，那么必定有鸽巢中至少飞进了2只鸽子。
-
常被用于证明存在性证明，和求最坏情况下的解。
-
存在性证明：连最坏情况都不存在解，所以情况也就肯定不存在解。
证明
将 n+1 个苹果，放到 n个抽屉中，那么有至少一个抽屉有两个（或以上）的苹果。
这个定理看起来比较显然，证明方法考虑反证法：
假如每个抽屉有最多 1 个苹果，那么最多有 n 个苹果，而实际上有 n+1个苹果，矛盾。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 笺札！
相关推荐
2025-11-10
单调栈
单调栈算法 单调栈是一种特殊的数据结构，分为单调递增栈和单调递减栈，保证元素从栈顶到栈底的单调性。单调栈常用于在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 单调递减栈 单调递减栈的特点是从栈顶到栈底的元素是单调递减的。只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。这样就保证了栈中保留的都是比当前入栈元素小的值。 代码示例 123456789101112...
2025-11-21
哈希函数
哈希函数 哈希的过程中需要使用哈希函数进行计算。 哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。 表示为： address=H[key]address = H [key] address=H[key] 几种常见的哈希函数（散列函数）构造方法 直接定址法 除留余数法 数字分析法 平方取中法 折叠法（叠加法） 随机数法 哈希冲突的解决 选用哈希函数计算哈希值时，可能不同的 key 会得到相同的结果，一个地址怎么存放多个数据呢？这就是冲突。 解决方法： 将所有关键字为同义词的结点链接在同一个单链表中 开放定址法 当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。 线性探查法 二次探查法 双重散列法
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}+⋯+𝑛_12^1+...
