leetcode Power of Four

leetcode Power of Four

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

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

题目地址:leetcode Power of Four

题意: 给定一个有符号整形,让你判断它是不是4的次方数

思路:

方法一:

直接循环求解(每次看看能不能整除,每次除以4),这里就不贴代码了。

方法二

power of two的时候,我们用 n &(n-1) ==0 来判断是否是2的次方数,这里也先判断一下是否为2的次方数。然后再把不是4的次方数排除掉,比如8.

我们来看看2的次方数的规律:

我们发现,每次不过是将1向左移动一个位置,然后低位补0(这不是废话么= =|||)

那么4的次方数就是将1向左移动两个位置喽 (还是废话(╯-_-)╯╧╧)

观察一下位置,4的次方中的1只出现在奇数的位置上!就是说,上面的二进制从右往左,第1,3,5,……位置上。

So,如果我们与上一个可以在奇数上面选择位置的数,也就是 0101 0101 ……那么就把不是4次方的排除掉啦

0101 0101 …… 十六进制表示为: 0x55555555

 

C++

Java

Python

 

本题是leetcode 342 Power of Four solution 题解,

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

 

 


 

 

附带上power of two题解

leetcode 231 Power of Two

Given an integer, write a function to determine if it is a power of two.

题目地址:leetcode Power of Two

题意: 给定一个整形,让你判断它是不是2的次方数

思路:

方法一:

直接循环求解(每次看看能不能整除,每次除以2)

方法二

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Power of Four
本文地址:https://www.hrwhisper.me/leetcode-power-four/

您的支持将鼓励我继续创作!

Leetcode , , , , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *