LeetCode题解342.power-of-four

题目地址

https://leetcode.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

LeetCode题解200.number-of-islands

题目地址 https://leetcode.com/problems/number-of-islands/description/ 题目描述 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by …

LeetCode题解1020.number-of-enclaves

题目地址 https://leetcode-cn.com/problems/number-of-enclaves/ 题目描述 给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。 移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。   示例 1： 输入…

LeetCode题解1297.maximum-number-of-occurrences-of-a-substring

题目地址（1297. 子串的最大出现次数） https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring 题目描述 给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数： 子串中不同字母的数目必须小于等于 maxLetters 。 子串的…

LeetCode题解201.bitwise-and-of-numbers-range

题目地址 https://leetcode.com/problems/bitwise-and-of-numbers-range/description/ 题目描述 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbe…

LeetCode题解30.substring-with-concatenation-of-all-words

题目地址（30. 串联所有单词的子串） https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/description/ 题目描述 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子…