Tag: tech
All the articles with the tag "tech".
-
赛马问题——25匹马5条跑道找前三需几场？
通过分组赛缩小候选范围，冠军赛确定第一名，淘汰逻辑压缩候选集，最终决赛解决余量，共需 7 场。
-
蓝眼睛悖论——Common Knowledge的归纳推理
蓝眼睛悖论揭示公共知识的建立为数学归纳法提供了 base case，游客的话将已知信息转化为公共共识。
-
海盗分金币——逆向归纳法的博弈论经典
通过逆向归纳法从最后一轮往前推导，每轮提案者以最低成本收买在自己被否决后过得最差的选民。
-
水桶取水——扩展欧几里得算法的编程题转化
水桶取水问题的数学本质是贝祖定理判断可解性，扩展欧几里得算法求解通解，BFS 求最小步数。
-
不均匀硬币如何公平决策——抛两次的巧妙解法
利用抛两次硬币取正反/反正序列的对称概率巧妙实现公平决策，揭示伯努利试验的数学之美。
-
Rand5生成Rand7——拒绝采样的原理与应用
用两次 rand5 构造 25 种等概率结果放大到 7 以上，截断 21 后模 7 映射，22~25 拒绝重试，拒绝采样保证严格均匀分布
-
合并K个升序链表——小顶堆与分治归并
合并 K 个升序链表的两大解法：小顶堆每次取 K 个链表的当前最小头节点，分治法两两归并逐步合并，时间复杂度对比分析。
-
单调栈与滑动窗口——三个模板解决80%的数组区间问题
单调栈维护有序性解决下一个更大元素问题，单调队列维护时效性解决滑动窗口最大值，有序性与时效性的经典博弈。