图源：文心一言

上机题目练习整理~🥝🥝

本篇作为基础练习，提供了3种解法以及函数的详细解释，供小伙伴们参考~🥝🥝

  • 第1版：在力扣新手村刷题的记录，方法一是自己写的，方法二与方法三是力扣的官方解法~🧩🧩
  • 第2版：默默增加了一些小细节，便于理解~🧩🧩
  • 第3班：增加了题目 3的幂，关于浮点数有些小细节需要讲一下，可以与2的幂对比参考~🧩🧩

编辑：梅头脑🌸

题目1：231. 2 的幂 - 力扣（LeetCode）

题目2：326. 3 的幂 - 力扣（LeetCode）

📇目录

📇目录

🧵2的幂

🧩题目

🌰方法一：取对数后幂运算

🌰方法二：位运算

🌰方法三：枚举法

🧵3的幂

🧩题目

🌰方法一：取对数后幂运算

🌰方法二：循环除法

🌰方法三：枚举法

🔚结语

🧵2的幂

🧩题目

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

示例 4：

输入：n = 4
输出：true

示例 5：

输入：n = 5
输出：false

🌰方法一：取对数后幂运算

📇算法思路

  • 算法思想：一个整数n，取对数后且再次以2为底的幂运算后记为a，若n==a，则说明这个数字是2的约数。
  • 时间复杂度：O(1)。
  • 空间复杂度：O(1)。

 ⌨️算法代码

class Solution {
public:
    bool isPowerOfTwo(int n) {
        int a = 0;
        if (n > 0) {
            a = log2(n);     // 取余运算
        } else {
            return false;
        }
        int a1 = pow(2, a);  // 以2为底的幂运算
        if (a1 == n)
            return true;
        else
            return false;
    }
};

⌨️温馨提示

可能问题：请注意，以下写法可能会导致下图的执行错误：

  • 第5行直接写为：  if (n > =0) ，而非“if (n > 0) ”

问题所在：这个错误是因为我试图将一个负无穷大的值赋给一个整数变量。在代码中，log2(n) 函数在 n 小于等于0时会返回负无穷大，这是由于log函数的定义所决定的。使用以下代码简单测试：

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int a = log2(0);       // 结果是-2147483648
    // int a = log2(0.5);  // 结果是-1
    // int a = log2(1);    // 结果是0
    cout << a << endl;
}

🌰方法二：位运算

📇算法思路1

  • 算法思想：如果某数是二进制的幂次，则n 的二进制表示中仅包含 1 个 1。我们此处以打表法浅显举栗：
    • 十进制二进制是否为二进制数
      00...00000否，不含1
      10...00001是，含1个1
      20...00010是，含1个1
      30...00011否，含2个1
      40...00100是，含1个1
      50...00101否，含2个1
      60...00110否，含2个1
      70...00111否，含3个1
      80...01000是，含1个1
      90...01001否，含2个1
      100...01010否，含2个1
      110...01011否，含3个1
      120...01100否，含2个1
      130...01101否，含3个1
      140...0111​​​​​​​0否，含3个1
      150...0​​​​​​​111​​​​​​​1否，含3个1
      160...1​​​​​​​00​​​​​​​00是，含1个1
    • 为什么会出现这个现象？十进制转二进制，1=2^0，即2进制的第0位为1；2=2^1，即2进制的第1位为1；4=2^2，即4进制的第2位为2...；按照归纳法，就可以得到若n为2的幂次，则n的二进制只有1位为1；
    • 所以问题的核心就在于怎么判断这个数字的二进制只含1个1。
  • 力扣官方解法1： (n & (n - 1)) ，即减去1后，如果位数与原数均不相同（即按位与运算为0），则原数仅含1个1；
  • 代入数据：
    • n=1，则n的二进制 0...00001，n-1的二进制 0...00000，按位与运算0...00000，判断条件 n > 0 && (n & (n - 1)) == 0 为真；
    • n=16，则n的二进制 0...10000，n-1的二进制 0...01111，按位与运算0...00000，判断条件 n > 0 && (n & (n - 1)) == 0 为真；
    • n=3，则n的二进制 0...00011，n-1的二进制 0...00010，按位与运算0...00010，判断条件 n > 0 && (n & (n - 1)) == 0 为假；
    • n=0，未满足条件n>0，跳过后续按位相与判定，为假。
  • 时间复杂度：O(1)；
  • 空间复杂度：O(1)；

 ⌨️算法代码1

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

函数体中的逻辑如下：

  1. return n > 0 && (n & (n - 1)) == 0;

这里使用了位运算和逻辑运算来判断n是否为2的幂次方。

  • n > 0：首先判断n是否大于0，因为负数和0都不是2的幂次方。
  • (n & (n - 1)) == 0：这是核心的判断逻辑。
    • 位与运算(&)会比较n和n-1的每一位，如果结果为0，说明这两个数的相应位都为0；如果结果不为0，说明至少有一位不相同。
    • 因此，如果n是2的幂次方，那么n-1会在二进制表示中至少有一位是1（除了最低位），而与运算的结果会是非零值。
    • 反之，如果n-1的二进制表示都是0（除了可能的最高位），那么与运算的结果就是0，说明n是2的幂次方。

📇算法思路2

  • 算法思想：
    • ​​​​​​​力扣官方解法2： (n & -n) ，负数是按照补码规则在计算机中存储的，−n 的二进制表示为 n 的二进制表示的每一位取反再加上 1。​​​​​​​
  • 补码规则：
    • ​​​​​​​n的原码转-n的原码：int为有符号数字，符号位为最高位，符号为变负即最高位取反，其余不变；
    • -n的原码转-n的反码：由于-n一定是负数，按照负数的反码规则，除了符号位（最高1位）不变，数值位（除了最高位）全部取反；
    • -n的反码转-n的补码：反码+1；
    • 按位与运算：若二进制对应位均为1，则按位与运算结果为1，否则为0；
  • 代入数据：
    • n=1
      • n的二进制原码： 0...00001；
      • -n的二进制原码：1...00001；
      • -n的二进制反码 ：1...11110；
      • -n的二进制补码 1...11111；
      • 按位与运算n & (-n)：0...00001；
      • 判断条件 n > 0 && (n & (-n) =n ) == 0 为真；
    • n=16
      • n的二进制原码：0...10000；
      • -n的二进制原码：1...10000；
      • -n的二进制反码：1...01111；
      • -n的二进制补码：1...10000；
      • 按位与运算n & (-n)：0...10000；
      • 判断条件 n > 0 && (n & (-n) =n ) == 0 为真；
    • n=3
      • n的二进制原码：0...00011；
      • -n的二进制原码：1...00011；
      • -n的二进制反码： 1...11100；
      • -n的二进制补码： 1...11101；
      • 按位与运算n & (-n)：0...00001；
      • 判断条件n > 0 && (n & (-n) =n ) == 0 为假；
    • n=0，未满足条件n>0，跳过后续按位相与判定，为假。

⌨️算法代码2

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};

⌨️知识扩展

思维导图：emmm...补码规则听起来有点绕对不对，而且正数负数的存储规则是不一样的，这就涉及到计组的知识了，正好是我来不及整理和发布的那一篇，稍等我Po一下草稿——

备注：

🌰方法三：枚举法

📇算法思路

算法思想：再次看向这个粗糙打表，二进制正数每次x2时，表示所有位数左移1位，右端补0；

十进制

二进制备注
00...00000——
10...00001——
20...000101左移1位
30...00011——
40...00100

2左移1位

1左移2位

50...00101——
60...001103左移1位
70...00111——
80...01000

4左移1位

​​​​​​​1左移3位

90...0100​​​​​​​1——
100...0​​​​​​​10​​​​​​​10​​​​​​​5左移1位
110...0​​​​​​​10​​​​​​​11——
120...0​​​​​​​11​​​​​​​006左移1位
130...0​​​​​​​11​​​​​​​01——
140...0​​​​​​​111​​​​​​​07左移1位
150...0​​​​​​​111​​​​​​​1——
160...1​​​​​​​00​​​​​​​00

8左移1位

1左移4位

题目给定的最大范围是2^30，即为1左移30位的结果。理论上逐个判断1左移1~30次是否与n相同即可。

⌨️算法代码1

class Solution {
    static constexpr int BIG = 1 << 30; 

public:
    bool isPowerOfTwo(int n) {
        return n > 0 && BIG % n == 0;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/power-of-two/solutions/796201/2de-mi-by-leetcode-solution-rny3/

⌨️算法解释1

  • 这段代码是一个C++类，名为Solution，它包含一个私有静态常量整型成员BIG和一个公有成员函数isPowerOfTwo。

  • 这里定义了一个名为BIG的静态常量整型变量，并使用左移操作符将其初始化为1向左移30位的结果，即2^30。这实际上是2的幂次方的最大值。
static constexpr int BIG = 1 << 30;
  • 接下来，我们来看公有成员函数isPowerOfTwo：
    • 这个函数接受一个整数参数n，并返回一个布尔值。函数首先检查n是否大于0，因为负数和0都不是2的幂次方。
    • 然后，它使用模运算符（%）来检查BIG是否能被n整除。如果可以，说明n是一个2的幂次方，函数返回true；否则，返回false。
bool isPowerOfTwo(int n) {  
    return n > 0 && BIG % n == 0;  
}

⌨️函数扩展

constexpr 是 C++11 引入的一个关键字，用于声明常量表达式。它有两个主要用途：

  1. 编译时常量：当你在类中定义一个 constexpr 成员变量时，该变量的初始化表达式必须是编译时常量。这意味着该表达式的值在编译时必须是已知的，并且不能包含任何运行时才能确定的表达式。

class MyClass {  
public:  
    constexpr static int value = 42;  // 编译时常量  
};

  1. 函数修饰符：当你在函数定义前加上 constexpr 关键字时，该函数必须满足以下条件：

    • 函数体必须非常小，只包含一个返回语句。

    • 参数类型必须为编译时常量类型。

    • 返回类型必须是 void 或 const 类型。使用 constexpr 函数可以在编译时计算值，这可以用于优化和常量表达式的计算。

constexpr int add(int a, int b) {  
    return a + b;  
}

使用 constexpr 可以帮助编译器进行更多的优化，因为它知道变量的值在编译时是确定的，并且可以用于编译时的常量计算。然而，使用 constexpr 时需要确保你的代码满足其严格的条件，否则编译器会报错。

⌨️算法代码2

class Solution {
    public boolean isPowerOfTwo(int n) {
        switch (n) {
            case 1:
            case 2:
            case 4:
            case 8:
            case 16:
            case 32:
            case 64:
            case 128:
            case 256:
            case 512:
            case 1024:
            case 2048:
            case 4096:
            case 8192:
            case 16384:
            case 32768:
            case 65536:
            case 131072:
            case 262144:
            case 524288:
            case 1048576:
            case 2097152:
            case 4194304:
            case 8388608:
            case 16777216:
            case 33554432:
            case 67108864:
            case 134217728:
            case 268435456:
            case 536870912:
            case 1073741824:
            return true;
        }
        return false;
    }
}

作者：Zhuuuu - 力扣（LeetCode）

备注：大佬的沙雕之作，仅供娱乐~~

🧵3的幂

🧩题目

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

  • -2^31 <= n <= 2^31 - 1

🌰方法一：取对数后幂运算

📇算法思路

  • 算法思想：一个整数n，取对数后且再次以3为底的幂运算后记为a，若n==a，则说明这个数字是3的约数。
  • 时间复杂度：O(1)。
  • 空间复杂度：O(1)。

 ⌨️算法代码1

#include <cmath>  
  
class Solution {  
public:  
    bool isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }

        double log3n = log10(n) / log10(3); // 计算以3为底n的对数  
        int exponent = static_cast<int>(log3n); // 取整数部分，注意这里是去尾法而非四舍五入  

        // 检查n是否是3的exponent次幂  
        // 使用一个很小的正数epsilon来允许一定的浮点数误差  
        double epsilon = 1e-15;
        double sub = fabs(n - pow(3, exponent));
        if (sub < epsilon * n)
            return true;
        else
            return false;
    }
};

📇温馨提示

问题所在：

  • 代码在数学逻辑上可能是成立的，但是在计算机运行上不成立；在计算机运算时，浮点数运算可能会引入精度问题，导致结果不准确。
  • 因此在浮点数的比较时，我们很少用 == 直接判断，而是用两数相减，其误差在一个很小的正数范围内时表示相等。

测试用例：

  • n=1162261467，即2^19测试结果，返回真（a=1），是正确的~

  • n=1162261468，即2^19测试结果+1，返回真（a=1），是错误的（这里不晓得是不是意外）~不过我们把epsilon调到-15以后，结果就正确了~

  • 至于为什么下面是sub上面是s，因为有个傻缺博主，她的代码类命名和局部变量命名都是s，emm....后来局部命名改为sub了~

📇知识扩展

  • 在C++中，<cmath>库提供了几种对数运算函数，其中最常见的是log和log10。这两个函数分别用于计算自然对数（以e为底）和常用对数（以10为底）。 
    • double log(double x);    // 以e为底
double log2(double x);   // 以2为底
double log10(double x);  // 以10为底
  • 此外，<cmath>库还提供了一个更通用的对数函数logb，但它不是用来计算任意底数的对数，而是返回一个浮点数的二进制对数（以2为底的对数，但结果是一个整数或浮点数的缩放版本，具体取决于实现）。这通常用于分析浮点数的表示，而不是进行通用的数学计算。
  • 对于需要计算任意底数b的对数log_b(x)，可以使用换底公式将其转换为以已知底数（如e或10）的对数来计算。换底公式是： 
    • log_b(x) = log_a(x) / log_a(b)
    • 其中a可以是任何正数，但不等于1。在C++中，通常会选择a为e（使用log函数）或10（使用log10函数），因为这两个底数的对数函数是标准库直接提供的。
  • 需要注意的是，由于浮点数的精度限制，这些对数函数可能无法提供完全准确的结果，特别是对于极大或极小的数值。在实际应用中，可能需要考虑这些限制，并采取相应的措施来处理潜在的精度问题。

 ⌨️算法代码2

在答案中看到的，确实忘记是哪位大佬提供的算法了，仿佛更简单一些：

#include <cmath>  
  
class Solution {
public:
    bool isPowerOfThree(int n) {
    if(n <= 0) return false;
    double a = log10(n) / log10(3) ;        //换底
    return  a == floor(a);         //判断换底后的log3n是否为整数，即n是否为3的倍数
    }
};

🌰方法二：循环除法

📇算法思路1

  • 算法思想：如果某数是三进制的幂次，那么一直除以3，再取余后，若为0，则满足幂为3的要求~
  • 时间复杂度：O(log₃n)。循环法的时间复杂度取决于输入数字n的大小。在最坏的情况下，我们需要循环除以3直到结果变为1。
  • 空间复杂度：O(1)。

 ⌨️算法代码1

#include <cmath>  
  
class Solution {  
public:  
    bool isPowerOfThree(int n) {  
        if (n <= 0) {  
            return false;  
        }  
          
        while (n % 3 == 0) {  
            n /= 3;  
        }  
          
        return n == 1;  
    }  
};

🌰方法三：枚举法

📇算法思路

  • 算法思想：
    • ​​​​​​​在题目给定的 323232 位有符号整数的范围内，最大的 3的幂为 3^{19} = 11622614673；
    • 因此，我们只需要判断 n是否是 3^{19} 的约数即可。
  • 时间复杂度：O(1)。
  • 空间复杂度：O(1)。

⌨️算法代码1

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/power-of-three/solutions/1011809/3de-mi-by-leetcode-solution-hnap/

🔚结语

博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等，博主会顶锅前来修改~~😶‍🌫️😶‍🌫️

我是梅头脑，本片博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下，感谢点赞小伙伴对于博主的支持~~🌟🌟

同系列的博文：🌸数据结构_梅头脑_的博客-CSDN博客

同博主的博文：🌸随笔03 笔记整理-CSDN博客

# c++ # 开发语言
Logo
天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

avatar 天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

avatar 天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

avatar 天工造物局