专栏首页脑洞前端【LeetCode】342. 4的幂

【LeetCode】342. 4的幂

题目地址

https://leetcode-cn.com/problems/power-of-four/description/

题目描述

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16
Output: true
Example 2:

Input: 5
Output: false
Follow up: Could you solve it without loops/recursion?

思路

符合直觉的做法是不停除以 4 直到不能整除,然后判断是否为 1 即可。代码如下:

while (num && num % 4 == 0) {
  num /= 4;
}
return num == 1;

但是这道题目有一个 follow up: “你是否可以不使用循环/递归完成”。因此我们需要换种思路。

我们先来看下,4 的幂次方用 2 进制表示是什么样的.

发现规律:4 的幂次方的二进制表示 1 的位置都是在奇数位(且不在最低位),其他位置都为 0

我们还可以发现:2 的幂次方的特点是最低位之外,其他位置有且仅有一个 1(1 可以在任意位置)

我们进一步分析,如果一个数字是四的幂次方,那么只需要满足:

  1. 是 2 的幂次方, 就能保证最低位之外,其他位置有且仅有一个 1
  2. 这个 1 不在偶数位置,一定在奇数位置

对于第一点,如果保证一个数字是 2 的幂次方呢?显然不能不停除以 2,看结果是否等于 1,这样就循环了。我们可以使用一个 trick, 如果一个数字 n 是 2 的幂次方,那么 n & (n - 1) 一定等于 0, 这个可以作为思考题,大家思考一下。

对于第二点,我们可以取一个特殊数字,这个特殊数字,奇数位置都是 1,偶数位置都是 0,然后和这个特殊数字求与, 如果等于本身,那么毫无疑问,这个 1 不再偶数位置,一定在奇数位置,因为如果在偶数位置,求与的结果就是 0 了 题目要求 n 是 32 位有符号整形,那么我们的特殊数字就应该是01010101010101010101010101010101(不用数了,一共 32 位)。

如上图,64和这个特殊数字求与,得到的是本身。8 是 2的次方,但是不是4的次方,我们求与结果就是0了。

为了体现自己的逼格,我们可以使用计算器,来找一个逼格比较高的数字,这里我选了十六进制,结果是0x55555555

代码见下方代码区。

说实话,这种做法不容易想到,其实还有一种方法。如果一个数字是 4 的幂次方,那么只需要满足:

  1. 是二的倍数
  2. 减去 1 是三的倍数

代码如下:

return num > 0 && num & (num - 1 === 0) && (num - 1) % 3 === 0;

关键点

  • 数论
  • 2的幂次方特点(数学性质以及二进制表示)
  • 4的幂次方特点(数学性质以及二进制表示)

代码

语言支持:JS, Python

JavaScript Code:

/*
 * @lc app=leetcode id=342 lang=javascript
 *
 * [342] Power of Four
 */
/**
 * @param {number} num
 * @return {boolean}
 */
var isPowerOfFour = function(num) {
  // tag: 数论

  if (num === 1) return true;
  if (num < 4) return false;

  if ((num & (num - 1)) !== 0) return false;

  return (num & 0x55555555) === num;
};

Python Code:

class Solution:
    def isPowerOfFour(self, num: int) -> bool:
        if num == 1:
            return True
        elif num < 4:
            return False
        else:
            if not num & (num-1) == 0:
                return False
            else:
                return num & 0x55555555 == num

    # 另一种解法:将数字转化为二进制表示的字符串,利用字符串的相关操作进行判断
    def isPowerOfFour(self, num: int) -> bool:
        binary_num = bin(num)[2:]
        return binary_num.strip('0') == '1' and len(binary_num) % 2 == 1

本文分享自微信公众号 - 脑洞前端(fe_lucifer),作者:一个脑洞很大的程序员

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 263. 丑数

    1 是丑数。输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。

    lucifer210
  • 342. 4的幂

    给定一个整数 (32 位有符号整数),请编写一个函数来判断它是否是 4 的幂次方。

    lucifer210
  • 349. 两个数组的交集

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/intersection-of-two-arrays 著...

    lucifer210
  • 【每天一道编程系列-2018.2.11】(Ans)[补]

    The number of daffodils refers to an n-digit number (n≥3), the sum of the n-th ...

    yesr
  • <递归>汉诺塔 | 斐波那契数列 | 阶乘 (附python实现源码)汉诺塔问题求斐波那契数列背景故事:求阶乘

    经典递归 汉诺塔问题 背景故事 传说印度某间寺院有三根柱子,上串64个金盘。寺院里的僧侣依照一个古老的预言,以上述规则移动这些盘子;预言说当这些盘子移动完毕,世...

    zhaoolee
  • 【USACO 2.1】Sorting A Three-Valued Sequence

    TASK: n个数的序列,值只有1、2、3,通过几次互换可以变成升序。 num[i][j]为排完序后为数字i,原来是数字j的位置的个数, 所有i!=j的min...

    饶文津
  • BugkuCTF 矛盾

    Angel_Kitty
  • leetcode-507-Perfect Number

    chenjx85
  • C++ 动态捕获整型数列

    假设有这样一个要求,输入两列数字,第一行是数组中数字的个数,第二行数数组中的数字,中间以空格隔开,我们可以写出这样的一段代码: int num; ...

    chaibubble
  • 浅谈python多线程和多线程变量共享问题介绍

    执行结果可以看到函数 sing、dance和类在同时执行,执行效果太长就不方截图了

    砸漏

扫码关注云+社区

领取腾讯云代金券