231、2的幂

发表于 分类于 ， ， ， 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 1 分钟
简介：LeetCode第231题：2的幂

题目

https://leetcode-cn.com/problems/power-of-two/

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == $2^x$ ，则认为 n 是 2 的幂次方。

程序样例

1
2
3
bool isPowerOfTwo(int n){

}

方法一

一顿胡乱尝试后写出来的，不太美观，但是复杂度分析结果比较好。

关键代码

1
2
3
4
5
6
7
8
9
10
bool isPowerOfTwo(int n){
	if(n==1){
		return true;
	}else if(n%2!=0||n==0){
		return false;
	}else{
		isPowerOfTwo(n/2);
	}
  	return;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

bool isPowerOfTwo(int n){
	if(n==1){
		return true;
	}else if(n%2!=0||n==0){
		return false;
	}else{
		isPowerOfTwo(n/2);
	}
  	return;
}

main(){
	int n;
	scanf("%d",&n);
	bool flag = isPowerOfTwo(n);
	printf("--%d--",flag);
}

编译出错 以及 解决方法

编译出错

Snipaste_2021-08-24_19-06-12

原因是返回值，leetcode判断可能会有无返回值的情况，所以出错。

解决办法：

在方法的最后一行加return;，注意不要返回内容，否则可能会出错。

复杂度分析

执行用时: 0 ms

内存消耗: 5.3 MB

方法二

看了别人的解析后想出来的，虽然代码美观了一些，但是复杂度分析结果没那么好。

关键代码

1
2
3
4
5
6
7
8
9
bool isPowerOfTwo(int n){
	if(n==1){
		return true;
	}
	if(n%2!=0||n==0){
		return false;
	}
	return isPowerOfTwo(n/2);
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

bool isPowerOfTwo(int n){
	if(n==1){
		return true;
	}
	if(n%2!=0||n==0){
		return false;
	}
	return isPowerOfTwo(n/2);
}

main(){
	int n;
	scanf("%d",&n);
	bool flag = isPowerOfTwo(n);
	printf("--%d--",flag);
}

复杂度分析

执行用时: 4 ms

内存消耗: 5.4 MB