TechnicalNote经典算法难题汉诺塔、骰子问题与坐标压缩3个面试加分技巧一次讲透【免费下载链接】TechnicalNoteRepository to store what we have studied. :book: We want everyone to get a job through TechnicalNote.项目地址: https://gitcode.com/gh_mirrors/te/TechnicalNoteTechnicalNote是一个把真实面试与笔试经历整理成体系的开源技术笔记仓库涵盖算法、数据结构、数据库、操作系统、Web 等面试高频领域。本文带你精讲仓库中最经典的 3 道算法题汉诺塔递归、骰子问题均匀概率扩展、坐标压缩大范围数据重编号每题都给出核心思路与面试加分表达读完即可在面试中从容应对。 本文内容对应仓库文件algorithm/TowerOfHanoi.md、algorithm/DiceProblem.md、algorithm/CoordinateCompression.md一、汉诺塔如何用递归讲清楚 2ᴺ−1 这个答案1.1 题目与规则30秒看懂把 N 个大小不同的圆盘从 A 柱移动到 C 柱借助 B 柱规则只有两条规则说明①一次只能移动一个圆盘②大盘不能压在小盘上面1.2 核心思路递归的三步分解面试官真正想听的是你的分解能力。N 个盘的问题可以拆成先把上面 N−1 个盘从 A 借助 C 移到 B把最大的第 N 个盘从 A 直接移到 C再把 N−1 个盘从 B 借助 A 移到 C。对应的极简实现Python仅 5 行def hanoi(n, from_pos, to_pos, aux_pos): if n 1: print(from_pos, -, to_pos) return hanoi(n - 1, from_pos, aux_pos, to_pos) print(from_pos, -, to_pos) hanoi(n - 1, aux_pos, to_pos, from_pos)1.3 面试加分点推导总移动次数 ⏱️不要只背答案现场推导才能拿高分递推式A(N) 2 × A(N−1) 1展开求和A(N) 2ᴺ⁻¹ 2ᴺ⁻² … 2 1 2ᴺ − 1圆盘数 N最少移动次数 2ᴺ−11123376418,446,744,073,709,551,111约需 5850 亿年 加分话术「时间复杂度为 O(2ᴺ)所以汉诺塔是指数级问题的代表实际中 N 超过 30 就不可能用朴素递归硬算了。」 完整推导过程与 Java / C / Python 三语言实现见 algorithm/TowerOfHanoi.md二、骰子问题把 1~6 的公平骰子扩展成 1~182.1 题目一道被低估的概率设计题普通骰子掷出 1~6 的概率都是 1/6。现在要求只用标准骰子可以掷多次、掷多个但不能改造骰子本身构造出 1~18 且每个数概率严格相等1/18的结果。这是考察均匀随机源扩展的经典题仓库中给出了 3 种解法难度递进2.2 解法一染色分组法思路巧妙但有坑 ⚠️把骰子 6 面按颜色各涂 2 面红、黄、蓝掷两次第一次记录点数第二次按颜色乘以对应系数红×1、黄×2、蓝×3可得到 1~18。但这里有个经典错误1 只有 (1,红) 一种组合概率 1/18而 6 有 3 种组合概率 3/18 ——并不均匀。修正方式每面印 3 个数字 (1,7,13)、(2,8,14)…(6,12,18)再用颜色三选一概率即变为 1/6 × 1/3 1/18。✅2.3 解法二36 格配对法最直观连续掷两次骰子共有 6 × 6 36 种等概率组合概率各为 1/36。将这 36 种组合两两配对成 18 组每组对应一个数字 1~18每个数字恰好占 2/36 1/18。✅2.4 解法三取模映射法最简洁面试推荐 ⭐用一行数学直接映射结果 ((第一次点数 − 1) mod 3) × 6 第二次点数第一次点数mod 3 后 ×6第二次点数 1~6覆盖区间1, 401~61~62, 561~67~123, 6121~613~18每个数字都恰好有 2 种骰子组合命中概率严格 1/18。✅ 加分话术「这类问题的本质是构造均匀随机数——先保证样本空间大小是目标数字个数的整数倍36 18×2再做一一映射。这个思想可以推广到 Rejection Sampling 拒绝采样。」 三种解法的完整推导见 algorithm/DiceProblem.md三、坐标压缩数据范围巨大时的降维神技3.1 什么时候必须用它当坐标的相对顺序比坐标的绝对值更重要且数据范围远超数据量时。仓库中有一个震撼的例子直线上 3 个点的坐标为[0, -2147483647, 2147483647]。如果开数组按坐标值存储只需存 3 个点却要分配2³² 个空间3.2 核心思路保序重编号只要保持大小关系不变就可以把坐标重新编号原始坐标 0 -2147483647 2147483647 压缩后 1 0 2空间从 2³² 直接降到N数据个数且所有点的位置关系原封不动。这就是以排名代替数值的降维思想。3.3 标准四步实现面试白板必考步骤操作目的①收集全部坐标值建立候选集②去重消除重复值③升序排序确定排名④原坐标 → 排序后的下标完成压缩 加分话术「朴素实现第 ④ 步是 O(N log N) 的线性查找用哈希表把值 → 排名映射起来压缩过程可以降到 O(N)。LeetCode 1856、1861 等题目都是这个模板。」 完整实现代码见 algorithm/CoordinateCompression.md四、3 道题一张表总结你的面试答题清单题目核心思想复杂度/关键结论一句话加分点 汉诺塔递归分治三步分解O(2ᴺ)共 2ᴺ−1 步现场推导递推式不背答案 骰子问题均匀随机源扩展36 18×2一一映射点出拒绝采样通用思想 坐标压缩以排名代替数值空间 O(2³²) → O(N)主动提哈希优化到 O(N)如何继续深入 TechnicalNoteTechnicalNote 的价值在于面试题 真实推导的组合拳algorithm/ 目录下还有冒泡、快排、拓扑排序、Kruskal 等 14 篇算法笔记配合 InterviewQuestions.md 中的真实面试题单一起刷复习效率更高。其他目录还覆盖了 C 虚函数原理、数据库事务隔离级别、操作系统内存结构等笔试硬知识建议按目录系统性过一遍。 记住面试官问的从来不只是答案而是你如何把大问题拆成小问题。这 3 道题恰好是递归、概率、降维三种拆解能力的最佳演练。【免费下载链接】TechnicalNoteRepository to store what we have studied. :book: We want everyone to get a job through TechnicalNote.项目地址: https://gitcode.com/gh_mirrors/te/TechnicalNote创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 TechnicalNote经典算法难题：汉诺塔、骰子问题与坐标压缩，3个面试加分技巧一次讲透
TechnicalNote经典算法难题汉诺塔、骰子问题与坐标压缩3个面试加分技巧一次讲透【免费下载链接】TechnicalNoteRepository to store what we have studied. :book: We want everyone to get a job through TechnicalNote.项目地址: https://gitcode.com/gh_mirrors/te/TechnicalNoteTechnicalNote是一个把真实面试与笔试经历整理成体系的开源技术笔记仓库涵盖算法、数据结构、数据库、操作系统、Web 等面试高频领域。本文带你精讲仓库中最经典的 3 道算法题汉诺塔递归、骰子问题均匀概率扩展、坐标压缩大范围数据重编号每题都给出核心思路与面试加分表达读完即可在面试中从容应对。 本文内容对应仓库文件algorithm/TowerOfHanoi.md、algorithm/DiceProblem.md、algorithm/CoordinateCompression.md一、汉诺塔如何用递归讲清楚 2ᴺ−1 这个答案1.1 题目与规则30秒看懂把 N 个大小不同的圆盘从 A 柱移动到 C 柱借助 B 柱规则只有两条规则说明①一次只能移动一个圆盘②大盘不能压在小盘上面1.2 核心思路递归的三步分解面试官真正想听的是你的分解能力。N 个盘的问题可以拆成先把上面 N−1 个盘从 A 借助 C 移到 B把最大的第 N 个盘从 A 直接移到 C再把 N−1 个盘从 B 借助 A 移到 C。对应的极简实现Python仅 5 行def hanoi(n, from_pos, to_pos, aux_pos): if n 1: print(from_pos, -, to_pos) return hanoi(n - 1, from_pos, aux_pos, to_pos) print(from_pos, -, to_pos) hanoi(n - 1, aux_pos, to_pos, from_pos)1.3 面试加分点推导总移动次数 ⏱️不要只背答案现场推导才能拿高分递推式A(N) 2 × A(N−1) 1展开求和A(N) 2ᴺ⁻¹ 2ᴺ⁻² … 2 1 2ᴺ − 1圆盘数 N最少移动次数 2ᴺ−11123376418,446,744,073,709,551,111约需 5850 亿年 加分话术「时间复杂度为 O(2ᴺ)所以汉诺塔是指数级问题的代表实际中 N 超过 30 就不可能用朴素递归硬算了。」 完整推导过程与 Java / C / Python 三语言实现见 algorithm/TowerOfHanoi.md二、骰子问题把 1~6 的公平骰子扩展成 1~182.1 题目一道被低估的概率设计题普通骰子掷出 1~6 的概率都是 1/6。现在要求只用标准骰子可以掷多次、掷多个但不能改造骰子本身构造出 1~18 且每个数概率严格相等1/18的结果。这是考察均匀随机源扩展的经典题仓库中给出了 3 种解法难度递进2.2 解法一染色分组法思路巧妙但有坑 ⚠️把骰子 6 面按颜色各涂 2 面红、黄、蓝掷两次第一次记录点数第二次按颜色乘以对应系数红×1、黄×2、蓝×3可得到 1~18。但这里有个经典错误1 只有 (1,红) 一种组合概率 1/18而 6 有 3 种组合概率 3/18 ——并不均匀。修正方式每面印 3 个数字 (1,7,13)、(2,8,14)…(6,12,18)再用颜色三选一概率即变为 1/6 × 1/3 1/18。✅2.3 解法二36 格配对法最直观连续掷两次骰子共有 6 × 6 36 种等概率组合概率各为 1/36。将这 36 种组合两两配对成 18 组每组对应一个数字 1~18每个数字恰好占 2/36 1/18。✅2.4 解法三取模映射法最简洁面试推荐 ⭐用一行数学直接映射结果 ((第一次点数 − 1) mod 3) × 6 第二次点数第一次点数mod 3 后 ×6第二次点数 1~6覆盖区间1, 401~61~62, 561~67~123, 6121~613~18每个数字都恰好有 2 种骰子组合命中概率严格 1/18。✅ 加分话术「这类问题的本质是构造均匀随机数——先保证样本空间大小是目标数字个数的整数倍36 18×2再做一一映射。这个思想可以推广到 Rejection Sampling 拒绝采样。」 三种解法的完整推导见 algorithm/DiceProblem.md三、坐标压缩数据范围巨大时的降维神技3.1 什么时候必须用它当坐标的相对顺序比坐标的绝对值更重要且数据范围远超数据量时。仓库中有一个震撼的例子直线上 3 个点的坐标为[0, -2147483647, 2147483647]。如果开数组按坐标值存储只需存 3 个点却要分配2³² 个空间3.2 核心思路保序重编号只要保持大小关系不变就可以把坐标重新编号原始坐标 0 -2147483647 2147483647 压缩后 1 0 2空间从 2³² 直接降到N数据个数且所有点的位置关系原封不动。这就是以排名代替数值的降维思想。3.3 标准四步实现面试白板必考步骤操作目的①收集全部坐标值建立候选集②去重消除重复值③升序排序确定排名④原坐标 → 排序后的下标完成压缩 加分话术「朴素实现第 ④ 步是 O(N log N) 的线性查找用哈希表把值 → 排名映射起来压缩过程可以降到 O(N)。LeetCode 1856、1861 等题目都是这个模板。」 完整实现代码见 algorithm/CoordinateCompression.md四、3 道题一张表总结你的面试答题清单题目核心思想复杂度/关键结论一句话加分点 汉诺塔递归分治三步分解O(2ᴺ)共 2ᴺ−1 步现场推导递推式不背答案 骰子问题均匀随机源扩展36 18×2一一映射点出拒绝采样通用思想 坐标压缩以排名代替数值空间 O(2³²) → O(N)主动提哈希优化到 O(N)如何继续深入 TechnicalNoteTechnicalNote 的价值在于面试题 真实推导的组合拳algorithm/ 目录下还有冒泡、快排、拓扑排序、Kruskal 等 14 篇算法笔记配合 InterviewQuestions.md 中的真实面试题单一起刷复习效率更高。其他目录还覆盖了 C 虚函数原理、数据库事务隔离级别、操作系统内存结构等笔试硬知识建议按目录系统性过一遍。 记住面试官问的从来不只是答案而是你如何把大问题拆成小问题。这 3 道题恰好是递归、概率、降维三种拆解能力的最佳演练。【免费下载链接】TechnicalNoteRepository to store what we have studied. :book: We want everyone to get a job through TechnicalNote.项目地址: https://gitcode.com/gh_mirrors/te/TechnicalNote创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考