当前位置: 首页 > news >正文

力扣231. 2 的幂(数学,二分查找,位运算)

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;}
};
http://www.lryc.cn/news/297662.html

相关文章:

  • Maven私服部署与JAR文件本地安装
  • 【MySQL】字符串函数的学习
  • AI助力农作物自动采摘,基于YOLOv5全系列【n/s/m/l/x】参数模型开发构建作番茄采摘场景下番茄成熟度检测识别计数分析系统
  • 记录下ibus-libpinyin输入法的重新安装
  • 第三百一十八回
  • 破除Github API接口的访问次数限制
  • 蓝桥杯嵌入式第8届真题(完成) STM32G431
  • 第二节 zookeeper基础应用与实战
  • 改变AI服务器:探索界面互连芯片技术的创新突破
  • 【P1506 拯救oibh总部】
  • 应用层 HTTP协议(1)
  • Linux学习笔记(centOS)—— 文件系统
  • 华视 CVR-100UC 身份证读取 html二次开发模板
  • ubuntu彻底卸载cuda 重新安装cuda
  • 【Java】学习笔记:关于java.sql;
  • python web 框架Django学习笔记
  • ubuntn20 搭建 redmine
  • 每日五道java面试题之java基础篇(三)
  • 如何升级 gpt4?快速升级至ChatGPT Plus指南,爆火的“ChatGPT”到底是什么?
  • 【实习】深信服防火墙网络安全生产实习
  • 怎么把视频音乐提取成mp3?分享详细工具和方法!
  • 代码随想录算法训练营第44天 | 完全背包理论基础 518.零钱兑换II 377.组合总和 Ⅳ
  • 深度解析与推荐:主流Web前端开发框架
  • 【React】如何使antd禁用状态的表单输入组件响应点击事件?
  • Apache Flink
  • SpringMVC速成(一)
  • 通过nginx学习linux进程名的修改
  • 【PyTorch】实现迁移学习框架DANN
  • thinkphp6入门(18)-- 中间件中除了handle函数,还可以有其它函数吗
  • Java stream 流的基本使用