两分钟看完一道投机取巧的算法题

点击关注上方“五分钟学算法”,设为“置顶或星标”,第一时间送达干货。

取巧一时爽,一直取巧一直爽~

3 的幂

题目来源于 LeetCode 上第 326 号问题:3 的幂。题目难度为 Easy,目前通过率为 43.5% 。

题目描述

给定一个整数,写一个函数来判断它是否是 3 的幂次方。

示例 1:

输入: 27
输出: true

示例 2:

输入: 0
输出: false

进阶:
你能不使用循环或者递归来完成本题吗?

题目解析

正常的思路是不停地去除以 3,看最后的迭代商是否为 1。这种思路的代码使用到了循环,逼格不够高。

这里取巧的方法 用到了数论的知识:3 的幂次的质因子只有 3

题目要求输入的是 int 类型,正数范围是 0 – 231,在此范围中允许的最大的 3 的次方数为 319 = 1162261467 ,那么只要看这个数能否被 n 整除即可。

代码实现

class Solution {
    public boolean isPowerOfThree(int n) {
         return n > 0 && 1162261467 % n == 0;
    }
}

推荐阅读

拜托,面试官别问我「布隆」了

有点难度,几道和「滑动窗口」有关的算法面试题

数据结构与算法:三十张图弄懂「图的两种遍历方式」

昨天,终于拿到了腾讯 offer

几道和「二叉树」有关的算法面试题

几道和散列(哈希)表有关的面试题

一道看完答案你会觉得很沙雕的「动态规划算法题」

几道和「堆栈、队列」有关的面试算法题

链表算法面试问题?看我就够了!


我就知道你在看!


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 两分钟看完一道投机取巧的算法题

我还会在以下平台发布内容

GitHub 哔哩哔哩