力扣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.rhkb.cn/news/254791.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C语言操作符超详细总结

文章目录 1. 操作符的分类2. 二进制和进制转换2.1 2进制转10进制2.1.1 10进制转2进制数字 2.2 2进制转8进制和16进制2.2.1 2进制转8进制2.2.2 2进制转16进制 3. 原码、反码、补码4.移位操作符4.1 左移操作符4.2 右移操作符 5. 位操作符&#xff1a;&、|、^、~6. 逗号表达式…

LabVIEW多任务实时测控系统

LabVIEW多任务实时测控系统 面对现代化工业生产的复杂性和多变性&#xff0c;传统的测控系统已难以满足高效、精准、可靠的监控和控制需求。因此&#xff0c;开发一种基于LabVIEW的智能测控系统&#xff0c;能够提高生产效率&#xff0c;保证生产安全&#xff0c;是解决现代工…

12 ABC串口接收原理与思路

1. 串口接收原理 基本原理&#xff1a;通过数据起始位判断要是否要开始接收的数据&#xff0c;通过采样的方式确定每一位数据是0还是1。 如何判断数据起始位到来&#xff1a;通过边沿检测电路检测起始信号的下降沿 如何采样&#xff1a;一位数据采多次&#xff0c;统计得到高…

SpringBoot和SpringMVC

目录 一、springboot项目 &#xff08;1&#xff09;创建springboot项目 &#xff08;2&#xff09;目录介绍 &#xff08;3&#xff09;项目启动 &#xff08;4&#xff09;运行一个程序 &#xff08;5&#xff09;通过其他方式创建和运行springboot项目 二、SpringMVC…

掌握虚拟化与网络配置之道:深入浅出VMware及远程管理技巧

目录 虚拟机介绍 虚拟机的关键字 服务器架构的发展 为什么用虚拟机VMware 虚拟机和阿里云的区别 功能角度 价格因素 应用场景 优势方面 找到windows的服务管理 配置VMware 关于VMware安装的几个服务 vmware如何修改各种网络配置 关于NAT的详细信息(了解) NAT(网…

2024年低压电工证模拟考试题库及低压电工理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年低压电工证模拟考试题库及低压电工理论考试试题是由安全生产模拟考试一点通提供&#xff0c;低压电工证模拟考试题库是根据低压电工最新版教材&#xff0c;低压电工大纲整理而成&#xff08;含2024年低压电工证…

嵌入式单片机中晶振的工作原理

晶振在单片机中是必不可少的元器件&#xff0c;只要用到CPU的地方就必定有晶振的存在&#xff0c;那么晶振是如何工作的呢&#xff1f; 什么是晶振 晶振一般指晶体振荡器&#xff0c;晶体振荡器是指从一块石英晶体上按一定方位角切下的薄片&#xff0c;简称为晶片。 石英晶体谐…

Three.js学习8:基础贴图

一、贴图 贴图&#xff08;Texture Mapping&#xff09;&#xff0c;也翻译为纹理映射&#xff0c;“贴图”这个翻译更直观。 贴图&#xff0c;就是把图片贴在 3D 物体材质的表面&#xff0c;让它具有一定的纹理&#xff0c;来为 3D 物体添加细节的一种方法。这使我们能够添加…

Git详细讲解

文章目录 一、Git相关概念二、本地分支中文件的添加 、提交2.1 文件状态2.2 创建Git仓库2.2.1 git init2.2.2 git clone 2.3 添加操作(git add)2.4 提交操作&#xff08;git commit&#xff09;2.5 撤销操作2.5.1 撤销 add操作2.5.2 撤销 commit操作2.5.3 覆盖上一次的commit操…

ElasticSearch之倒排索引

写在前面 本文看下es的倒排索引相关内容。 1&#xff1a;正排索引和倒排索引 正排索引就是通过文档id找文档内容&#xff0c;而倒排索引就是通过文档内容找文档id&#xff0c;如下图&#xff1a; 2&#xff1a;倒排索引原理 假定我们有如下的数据&#xff1a; 为了建立倒…

Java中JVM常用参数配置(提供配置示例)

目录 前言一、内存参数配置二、垃圾收集器配置三、GC策略配置3.1、基础通用配置3.2、Parallel 和 Parallel Old 常用参数配置3.3、CMS 常用参数配置3.4、G1 常用参数配置 四、GC日志配置五、dump 日志参数配置5.1、OutOfMemory异常时生成dump文件5.2、发生Full GC时生成dump文件…

PySpark(三)RDD持久化、共享变量、Spark内核制度,Spark Shuffle、Spark执行流程

目录 RDD持久化 RDD 的数据是过程数据 RDD 缓存 RDD CheckPoint 共享变量 广播变量 累加器 Spark 内核调度 DAG DAG 的宽窄依赖和阶段划分 内存迭代计算 Spark是怎么做内存计算的? DAG的作用?Stage阶段划分的作用? Spark为什么比MapReduce快&#xff1f; Spa…

Android Graphics 图像显示系统 - 开篇

“ 随着学习的不断深入和工作经验的积累&#xff0c;欲将之前在博客中整理的Android Graphics知识做进一步整理&#xff0c;并纠正一些理解上的错误&#xff0c;故开设Graphics主题系列文章 ” 序言 由于工作需要&#xff0c;也源于个人兴趣&#xff0c;终于下决心花时间整理一…

Mac 下JDK环境变量配置 及 JDK多版本切换

一、推荐官网下载&#xff1a; 二、环境变量配置 1、查看JDK地址&#xff0c;在终端输入以下命令&#xff1a; /usr/libexec/java_home -V 我的路径&#xff1a; /Library/Java/JavaVirtualMachines/jdk-17.jdk/Contents/Home /Library/Java/JavaVirtualMachines/zulu-11.j…

ffmpeg命令生成器

FFmpeg 快速入门&#xff1a;命令行详解、工具、教程、电子书 – 码中人的博客FFmpeg 是一个强大的命令行工具&#xff0c;可以用来处理音频、视频、字幕等多媒体文件。本文介绍了 FFmpeg 的基本用法、一些常用的命令行参数&#xff0c;以及常用的可视化工具。https://blog.mzh…

nvm安装node后,npm无效

类似报这种问题&#xff0c;是因为去github下载npm时下载失败&#xff0c; Please visit https://github.com/npm/cli/releases/tag/v6.14.17 to download npm. 第一种方法&#xff1a;需要复制这里面的地址爬梯子去下载&#xff08;github有时不用梯子能直接下载&#xff0c;有…

机器学习系列——(二十二)结语

随着我们的机器学习系列的探索画上句号&#xff0c;我们不禁感慨于这一领域的广阔和深邃。从最初的基础概念到复杂的算法&#xff0c;从理论的探讨到实际应用的示例&#xff0c;我们一起经历了一段非凡的旅程。机器学习不仅是当前技术创新的核心驱动力之一&#xff0c;也是塑造…

电脑通电自启动设置

首先要进入BIOS&#xff0c;以华硕为例&#xff0c;按下电源键&#xff0c;在开机之前按下delete键&#xff0c;其他电脑可能是esc或者某个f键&#xff0c;请自行查找。 进入BIOS后要找到电源管理&#xff0c;可以在高级选项中找一找&#xff0c;如上图右下角选择高级模式。 …

基于华为云欧拉操作系统(HCE OS)容器化部署传统应用(Redis+Postgresql+Git+SpringBoot+Nginx)

写在前面 博文内容为 华为云欧拉操作系统入门级开发者认证(HCCDA – Huawei Cloud EulerOS)实验笔记整理认证地址&#xff1a;https://edu.huaweicloud.com/certificationindex/developer/9bf91efb086a448ab4331a2f53a4d3a1博文内容涉及一个传统 Springboot 应用HCE部署&#x…

软件价值7-万花筒

模拟一个万花筒&#xff0c;鼠标点击可以变换图形 import pygame import sys import math import randompygame.init()# 设置窗口大小 WIDTH, HEIGHT 800, 600 CENTER (WIDTH // 2, HEIGHT // 2)# 设置颜色 BLACK (0, 0, 0)# 初始化屏幕 screen pygame.display.set_mode((…