网页游戏排行选择,东莞网站推广及优化,小米应用商店安装下载,店铺首页设计Problem: 231. 2 的幂 文章目录 题目描述思路即解法复杂度Code 题目描述 思路即解法
思路1#xff1a;位运算 1.易验证2的幂为正数#xff1b; 2.易得2的幂用二进制表示只能有一个位为数字1 3.即将其转换为二进制统计其二进制1的个数 思路2#xff1a;数学 当给定数n大于1时… Problem: 231. 2 的幂 文章目录 题目描述思路即解法复杂度Code 题目描述 思路即解法
思路1位运算 1.易验证2的幂为正数 2.易得2的幂用二进制表示只能有一个位为数字1 3.即将其转换为二进制统计其二进制1的个数 思路2数学 当给定数n大于1时每次当n模2等于0时此时是2的幂每次将n除以2最后判断n是否为1 思路3二分查找 我们从0到 n n n开始二分查找每次取出当前的中间数mid当 2 mid 2^{\text{mid}} 2mid,等于 n n n时则返回true否则继续二分查找 复杂度
思路1 时间复杂度: O ( 1 ) O(1) O(1) 空间复杂度: O ( 1 ) O(1) O(1) 思路2 时间复杂度: O ( 1 ) O(1) O(1)因为在int范围内2的最大的幂为 2 30 2^{\text{30}} 230 空间复杂度: O ( 1 ) O(1) O(1) 思路 时间复杂度: O ( l o g n ) O(logn) O(logn) 空间复杂度: O ( 1 ) O(1) O(1) Code
思路1
class Solution {
public:/*** Bit operation* param n Given number* return bool*/bool isPowerOfTwo(int n) {if (n 0) {return false;}int mask 1;int count 0;for (int i 0; i 32; i) {if ((n mask) ! 0) {count;}mask 1;}if (count 1) {return true;}return false;}
};思路2
class Solution {
public:/*** Math* param n Given number* return bool*/bool isPowerOfTwo(int n) {if (n 0) {return false;}if (n 1) {while (n % 2 0) {n / 2;}}return n 1 ? true : false;}
};
思路3
class Solution {
public:/*** Binary Search* param n Given number* return bool*/bool isPowerOfTwo(int n) {if (n 1) {return false;}int start 0;int end n;while (start end) {int mid start (end - start) / 2;double result (double)(pow(2, mid));if (result n) {return true;} else if (result n) {end mid - 1;} else {start mid 1;}}return false;}
};
