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

2024-02-10 21:28

本文主要是介绍力扣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;}
};

这篇关于力扣231. 2 的幂(数学,二分查找,位运算)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/698089

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c