LeetCode：题目解答复盘（4）

4的幂 破冰游戏在这里记录一下这两道题的题目分析、难点以及解题思路希望能和大家一起交流进步题目一4的幂 (Power of Four) 题目分析给定一个整数 n编写一个函数来判断它是否是 4 的幂次方。如果是返回 true否则返回 false。整数 n 是 4 的幂次方需要满足存在整数 x 使得 n等于x的4次方⚠️ 题目难点边界条件处理负数和 0 不可能是 4 的幂需要优先排除。停止条件判断在不断除以 4 的过程中如何准确判断最终结果是否为 1。进阶难点如果面试官要求不使用循环或者递归如何利用位运算或数学规律实现 O(1) 的时间复杂度 题目解答思路常规循环/递归法截图中的解法击败 100%首先判断 n 0如果是直接返回 false。使用 while 循环只要 n % 4 0就让 n / 4不断缩小规模。循环结束后判断 n 是否等于 1。如果是说明原数字是 4 的幂否则不是。题目二破冰游戏 (Ice Breaking Game) 题目分析社团共有 num 位成员参与破冰游戏编号为 0 ~ num-1。成员们按照编号顺序围绕一个圆桌坐下从 0 号成员开始报数报到 target 的成员离开圆桌下一位成员重新从 1 开始报数。直到圆桌上只剩最后一位成员求这位成员的编号。这其实就是经典的约瑟夫环问题。⚠️ 题目难点模拟法容易超时或内存溢出如果使用数组、链表或队列去真实模拟删除的过程时间复杂度高达 O(N×M)且代码冗长极易在数据量大的时候超时。数学推导理解门槛高如何通过逆向思维推导出索引位置的变化规律是本题最大的难点。 题目解答思路约瑟夫环数学递推逆向思维截图中的解法我们可以采用倒推法。当圆桌上只剩下 1 个人时他的索引一定是 0。那么如何从剩下 1 个人的索引反推出剩下 2 个人时的索引直到反推回剩下 num 个人时的索引递推公式f(n, m) (f(n - 1, m) m) % n其中 f(n, m) 表示有 n 个人每次报数 m 淘汰时最终幸存者的索引。已知 f(1, m) 0。我们可以从小到大枚举人数 i从 2 到 num逐步递推最终幸存者的位置这样空间复杂度只有 O(1)时间复杂度为 O(N)。“4的幂”考察了对边界条件的处理以及循环的收敛进阶解法更是位运算的经典应用。“破冰游戏”则是数学之美在算法中的完美体现将复杂的模拟过程压缩成了几行代码的数学递推。