LeetCode数学相关算法题(1)【C语言版】

2520. 统计能整除数字的位数

给你一个整数 num ，返回 num 中能整除 num 的数位的数目。

如果满足 nums % val == 0 ，则认为整数 val 可以整除 nums 。

示例 1：

输入：num = 7
输出：1
解释：7 被自己整除，因此答案是 1 。

示例 2：

输入：num = 121
输出：2
解释：121 可以被 1 整除，但无法被 2 整除。由于 1 出现两次，所以返回 2 。

示例 3：

输入：num = 1248
输出：4
解释：1248 可以被它每一位上的数字整除，因此答案是 4 。

```
#include <cstdio>// 函数：计算整数 num 中有多少个数位能够整除 num
int countDigits(int num) {int temp = num; // 用于操作的临时变量，避免直接修改 numint n = 0;      // 用于存储当前数位的值int count = 0;  // 用于计数，记录能整除 num 的数位个数// 遍历整数 num 的每一位数字while (temp != 0) {n = temp % 10; // 提取 temp 的最低位数字if (n != 0 && num % n == 0) { // 检查当前数位是否能整除 numcount++; // 如果能整除，计数器加1}temp /= 10; // 去掉 temp 的最低位数字，继续处理下一位}return count; // 返回计数结果
}int main() {// 测试函数，输入 num = 121printf("%d", countDigits(121)); // 输出结果return 0;
}
```

 2469. 温度转换

给你一个四舍五入到两位小数的非负浮点数 celsius 来表示温度，以 摄氏度（Celsius）为单位。

你需要将摄氏度转换为 开氏度（Kelvin）和 华氏度（Fahrenheit），并以数组 ans = [kelvin, fahrenheit] 的形式返回结果。

返回数组 ans 。与实际答案误差不超过 10-5 的会视为正确答案。

注意：

• 开氏度 = 摄氏度 + 273.15
• 华氏度 = 摄氏度 * 1.80 + 32.00

示例 1 ：

输入：celsius = 36.50
输出：[309.65000,97.70000]
解释：36.50 摄氏度：转换为开氏度是 309.65 ，转换为华氏度是 97.70 。

示例 2 ：

输入：celsius = 122.11
输出：[395.26000,251.79800]
解释：122.11 摄氏度：转换为开氏度是 395.26 ，转换为华氏度是 251.798 。

```
#include <cstdio>  // 包含标准输入输出库
#include <cstdlib> // 包含动态内存分配和释放的函数// 函数：将摄氏温度转换为开尔文温度和华氏温度
// 参数：
//   celsius：摄氏温度
//   returnSize：指向一个整数的指针，用于存储返回数组的大小
// 返回值：
//   返回一个指向动态分配的数组的指针，数组包含两个元素：开尔文温度和华氏温度
double* convertTemperature(double celsius, int* returnSize) {// 计算开尔文温度：摄氏温度 + 273.15double kelvin = celsius + 273.15;// 计算华氏温度：摄氏温度 * 1.80 + 32.00double fahrenheit = celsius * 1.80 + 32.00;// 为结果数组分配内存，数组包含两个double类型的元素double* ans = (double*)malloc(2 * sizeof(double));// 检查内存分配是否成功if (ans == NULL) {printf("Memory allocation failed.\n"); // 如果失败，输出错误信息exit(1); // 退出程序}// 将计算结果存储到动态分配的数组中ans[0] = kelvin;           // 存储开尔文温度ans[1] = fahrenheit;       // 存储华氏温度// 设置返回数组的大小，这里返回的数组包含两个元素*returnSize = 2;// 返回指向动态分配数组的指针return ans;
}int main() {int returnSize;            // 用于存储返回数组的大小double celsius;            // 用于存储用户输入的摄氏温度// 提示用户输入摄氏温度printf("Enter temperature in Celsius: ");// 从标准输入读取摄氏温度scanf("%lf", &celsius);// 调用函数，将摄氏温度转换为开尔文和华氏温度// returnSize用于存储返回数组的大小double* p = convertTemperature(celsius, &returnSize);// 遍历返回的数组并输出结果for (int i = 0; i < returnSize; ++i) {printf("%.2f\n", p[i]); // 输出结果，保留两位小数}// 释放动态分配的内存，避免内存泄漏free(p);return 0; // 程序正常结束
}
```

2160. 拆分数位后四位数字的最小和

给你一个四位 正 整数 num 。请你使用 num 中的 数位 ，将 num 拆成两个新的整数 new1 和 new2 。new1 和 new2 中可以有 前导 0 ，且 num 中 所有 数位都必须使用。

• 比方说，给你 num = 2932 ，你拥有的数位包括：两个 2 ，一个 9 和一个 3 。一些可能的 [new1, new2] 数对为 [22, 93]，[23, 92]，[223, 9] 和 [2, 329] 。

请你返回可以得到的 new1 和 new2 的 最小 和。

示例 1：

输入：num = 2932
输出：52
解释：可行的 [new1, new2] 数对为 [29, 23] ，[223, 9] 等等。
最小和为数对 [29, 23] 的和：29 + 23 = 52 。

示例 2：

输入：num = 4009
输出：13
解释：可行的 [new1, new2] 数对为 [0, 49] ，[490, 0] 等等。
最小和为数对 [4, 9] 的和：4 + 9 = 13 

```
#include <cstdio>// 函数：计算使用 num 中的数位可以得到的最小和
int minimumSum(int num) {int t = num; // 用于操作的临时变量，避免直接修改 numint arr[4] = {0}; // 定义一个大小为4的数组，用于存储拆分后的数位// 从最低位开始提取 num 的每一位数字，并存储到数组中for (int i = 0; i < 4; ++i) {arr[4 - 1 - i] = t % 10; // 提取最低位数字并存储到数组的对应位置t /= 10; // 去掉最低位数字}// 对数组进行排序，使用插入排序算法int high, low, mid, temp;for (int i = 1; i < 4; ++i) { // 从第二个元素开始遍历数组low = 0; // 定义查找范围的下界high = i - 1; // 定义查找范围的上界temp = arr[i]; // 保存当前需要插入的元素// 使用二分查找确定当前元素应该插入的位置while (low <= high) {mid = (low + high) / 2; // 计算中间位置if (arr[mid] > temp) { // 如果中间位置的元素大于当前元素high = mid - 1; // 调整上界} else {low = mid + 1; // 调整下界}}// 将从插入位置开始到当前元素位置的所有元素向后移动一位for (int j = i - 1; j >= low; --j) {arr[j + 1] = arr[j];}// 将当前元素插入到正确的位置arr[low] = temp;}// 构造两个新的整数，使得它们的和最小// 选择最小的两个数位作为十位数，剩下的两个数位作为个位数int num1 = arr[0] * 10 + arr[2]; // 构造第一个整数int num2 = arr[1] * 10 + arr[3]; // 构造第二个整数// 返回两个整数的和return num1 + num2;
}int main() {// 测试函数，输入 num = 4009printf("%d", minimumSum(4009)); // 输出结果return 0;
}
```

2413. 最小偶倍数

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

示例 1：

输入：n = 5
输出：10
解释：5 和 2 的最小公倍数是 10 。

示例 2：

输入：n = 6
输出：6
解释：6 和 2 的最小公倍数是 6 。注意数字会是它自身的倍数。

#include <cstdio>int smallestEvenMultiple(int n) {if (n%2 == 0){return n;} else{return 2*n;}
}int main(){printf("%d",smallestEvenMultiple(121));
}

1688. 比赛中的配对次数

给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：

• 如果当前队伍数是 偶数 ，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
• 如果当前队伍数为 奇数 ，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。

返回在比赛中进行的配对次数，直到决出获胜队伍为止。

示例 1：

输入：n = 7
输出：6
解释：比赛详情：
- 第 1 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。
- 第 2 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 3 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 3 + 2 + 1 = 6

示例 2：

输入：n = 14
输出：13
解释：比赛详情：
- 第 1 轮：队伍数 = 14 ，配对次数 = 7 ，7 支队伍晋级。
- 第 2 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。 
- 第 3 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 4 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 7 + 3 + 2 + 1 = 13

#include <cstdio>// 函数：计算在一场锦标赛中总共进行了多少场比赛
// 参数：
//   n：参赛队伍的数量
// 返回值：
//   比赛的总场数
int numberOfMatches(int n) {int temp = n; // 用于操作的临时变量，避免直接修改 nint count = 0; // 用于计数，记录比赛的总场数// 当参赛队伍数量大于1时，继续比赛while (temp != 1) {// 如果当前队伍数量是偶数if (temp % 2 == 0) {temp = temp / 2; // 每场比赛淘汰一半的队伍count += temp; // 累加比赛场数} else {// 如果当前队伍数量是奇数int n = (temp - 1) / 2; // 计算需要进行的比赛场数temp = temp - n; // 淘汰一半的队伍（向下取整）count += n; // 累加比赛场数}}return count; // 返回比赛的总场数
}int main() {// 测试函数，输入 n = 14printf("%d", numberOfMatches(14)); // 输出结果return 0;
}

1281. 整数的各位积和之差

给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。

示例 1：

输入：n = 234
输出：15 
解释：
各位数之积 = 2 * 3 * 4 = 24 
各位数之和 = 2 + 3 + 4 = 9 
结果 = 24 - 9 = 15

示例 2：

输入：n = 4421
输出：21
解释： 
各位数之积 = 4 * 4 * 2 * 1 = 32 
各位数之和 = 4 + 4 + 2 + 1 = 11 
结果 = 32 - 11 = 21

#include <cstdio>// 函数：计算整数 n 的各位数字之积与各位数字之和的差
int subtractProductAndSum(int n) {int temp = n; // 用于操作的临时变量，避免直接修改 nint sum = 0;  // 用于存储各位数字之和int ji = 1;   // 用于存储各位数字之积，初始化为1（乘法的单位元）// 遍历整数 n 的每一位数字while (temp != 0) {int m = temp % 10; // 获取当前最低位的数字sum += m;          // 将当前数字加到 sum 中ji *= m;           // 将当前数字乘到 ji 中temp /= 10;        // 去掉当前最低位数字，继续处理下一位}// 返回各位数字之积与各位数字之和的差return ji - sum;
}int main() {// 测试函数，输入 n = 4421printf("%d", subtractProductAndSum(4421)); // 输出结果return 0;
}

2427. 公因子的数目

给你两个正整数 a 和 b ，返回 a 和 b 的 公 因子的数目。

如果 x 可以同时整除 a 和 b ，则认为 x 是 a 和 b 的一个 公因子 。

示例 1：

输入：a = 12, b = 6
输出：4
解释：12 和 6 的公因子是 1、2、3、6 。

示例 2：

输入：a = 25, b = 30
输出：2
解释：25 和 30 的公因子是 1、5 。

#include <cstdio>// 函数：计算两个正整数 a 和 b 的公因数个数
int commonFactors(int a, int b) {int count = 0; // 用于计数公因数的个数// 遍历从1到较小数的所有整数for (int i = 1; i <= a && i <= b; ++i) {// 检查 i 是否是 a 和 b 的公因数if (a % i == 0 && b % i == 0) {count++; // 如果是公因数，计数器加1}}return count; // 返回公因数的个数
}int main() {// 测试函数，输入 a = 25 和 b = 30printf("%d", commonFactors(25, 30)); // 输出结果return 0;
}

728. 自除数

自除数 是指可以被它包含的每一位数整除的数。

• 例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。

自除数 不允许包含 0 。

给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right]（包括两个端点）内所有的 自除数 。

示例 1：

输入：left = 1, right = 22
输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

示例 2:

输入：left = 47, right = 85
输出：[48,55,66,77]

#include <stdio.h>
#include <stdlib.h>// 函数：找出一个范围内所有的自除数
// 参数：
//   left：范围的起始值
//   right：范围的结束值
//   returnSize：返回数组的大小
// 返回值：
//   指向动态分配数组的指针，数组包含范围内的所有自除数
int* selfDividingNumbers(int left, int right, int* returnSize) {int count = 0; // 用于计数自除数的数量int* arr = (int*)malloc((right - left + 1) * sizeof(int)); // 分配足够的内存空间// 遍历范围内的每一个数字for (int i = left; i <= right; ++i) {int temp = i; // 用于操作的临时变量，避免直接修改 ibool flag = true; // 标志位，用于判断当前数字是否为自除数// 检查当前数字的每一位是否满足自除数的条件while (temp != 0) {int digit = temp % 10; // 提取最低位数字if (digit == 0 || i % digit != 0) { // 如果当前位为0或不能整除flag = false; // 设置标志位为 falsebreak; // 退出循环}temp /= 10; // 去掉最低位数字}// 如果当前数字是自除数if (flag) {arr[count++] = i; // 将其存储到数组中，并更新计数器}}*returnSize = count; // 设置返回数组的大小return arr; // 返回指向动态分配数组的指针
}int main() {int returnSize = 0; // 用于存储返回数组的大小int* arr = selfDividingNumbers(1, 22, &returnSize); // 调用函数，获取自除数数组// 打印结果for (int i = 0; i < returnSize; ++i) {printf("%d ", arr[i]);}printf("\n");free(arr); // 释放动态分配的内存return 0;
}

2119. 反转两次的数字

反转 一个整数意味着倒置它的所有位。

• 例如，反转 2021 得到 1202 。反转 12300 得到 321 ，不保留前导零 。

给你一个整数 num ，反转 num 得到 reversed1 ，接着反转 reversed1 得到 reversed2 。如果 reversed2 等于 num ，返回 true ；否则，返回 false 。

示例 1：

输入：num = 526
输出：true
解释：反转 num 得到 625 ，接着反转 625 得到 526 ，等于 num 。

示例 2：

输入：num = 1800
输出：false
解释：反转 num 得到 81 ，接着反转 81 得到 18 ，不等于 num 。 

示例 3：

输入：num = 0
输出：true
解释：反转 num 得到 0 ，接着反转 0 得到 0 ，等于 num 。

#include <stdio.h>// 函数：判断一个整数在两次反转后是否与原数相同
bool isSameAfterReversals(int num) {// 如果 num 为 0，两次反转后仍然是 0，满足条件// 如果 num 的最后一位不是 0，那么两次反转后不会丢失任何数字，也满足条件// 如果 num 的最后一位是 0，第一次反转后会丢失这个 0，第二次反转后无法恢复，不满足条件return num == 0 || num % 10 != 0;
}int main() {// 测试函数，输入 num = 1800bool flag = isSameAfterReversals(1800); // 调用函数，判断 1800 是否满足条件// 根据返回值输出结果if (flag) {printf("true");} else {printf("false");}return 0;
}

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

#include <stdio.h>// 函数：计算斐波那契数列的第 n 项
// 斐波那契数列定义：
// F(0) = 0, F(1) = 1
// F(n) = F(n-1) + F(n-2) for n > 1
int fib(int n) {// 基础情况：F(0) = 0if (n == 0) {return 0;}// 基础情况：F(1) = 1if (n == 1) {return 1;}// 递归情况：F(n) = F(n-1) + F(n-2)return fib(n - 1) + fib(n - 2);
}int main() {// 测试函数，计算斐波那契数列的第 4 项printf("%d", fib(4)); // 输出结果return 0;
}

70. 爬楼梯😱

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

有点难看视频：带你学透动态规划-爬楼梯（对应力扣70.爬楼梯）| 动态规划经典入门题目_哔哩哔哩_bilibili

#include <stdio.h>int climbStairs(int n) {// 特殊情况处理：如果只有 1 级台阶，只有一种方法if (n == 1) {return 1;}// 特殊情况处理：如果有 2 级台阶，有两种方法（1+1 或 2）if (n == 2) {return 2;}// 动态规划数组 arr，用于存储到达每一级台阶的方法数int arr[n];// 初始化数组的前两个元素arr[0] = 1; // 只有1种方法到达第1级台阶（1步）arr[1] = 2; // 有2种方法到达第2级台阶（1+1步 或 2步）// 动态规划：从第3级台阶开始，每一级台阶的方法数等于前两级台阶的方法数之和for (int i = 2; i < n; ++i) {arr[i] = arr[i - 1] + arr[i - 2]; // 当前级数的方法数 = 前一级数的方法数 + 前两级数的方法数}// 返回到达第 n 级台阶的方法数return arr[n - 1];
}int main() {// 测试函数，计算爬 3 级台阶的方法数printf("%d", climbStairs(3)); // 输出结果return 0;
}

7. 整数反转 (中)

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

#include <stdio.h>
#include <limits.h> // 包含 INT_MAX 和 INT_MIN 的定义int reverse(int x) {int reversed = 0;while (x != 0) {int pop = x % 10; // 取最后一位x /= 10; // 去掉最后一位// 检查是否会导致溢出if (reversed > INT_MAX / 10 || (reversed == INT_MAX / 10 && pop > 7)) {return 0; // 正数溢出}if (reversed < INT_MIN / 10 || (reversed == INT_MIN / 10 && pop < -8)) {return 0; // 负数溢出}reversed = reversed * 10 + pop; // 累加到反转结果中}return reversed;
}int main() {printf("%d\n", reverse(-2147483412)); // 输出: 0 (溢出)return 0;
}

 原来反转不需要计算位数啊！！！之前的错误的写法就不展示了！这道题是AI写的我是在是没写出来！

在计算机中，整数类型（如 int）有一个固定的位数（通常是 32 位），因此它能够表示的范围是有限的。对于 32 位的有符号整数 int，其范围是 -2,147,483,648 到 2,147,483,647。如果计算结果超出了这个范围，就会发生溢出。

        // 检查是否会导致溢出if (reversed > INT_MAX / 10 || (reversed == INT_MAX / 10 && pop > 7)) {return 0; // 正数溢出}

• INT_MAX / 10 是 214748364，即 INT_MAX 除以 10。
• pop 是当前要添加到 reversed 的个位数。

这段代码的意思是：

• 如果 reversed 已经大于 INT_MAX / 10，那么再乘以 10 并加上 pop 肯定会溢出。
• 如果 reversed 等于 INT_MAX / 10，那么只有当 pop 大于 7 时才会溢出（因为 INT_MAX 的个位数是 7）。假设2,147,483,645个位数是5也是没有溢出哦。

        if (reversed < INT_MIN / 10 || (reversed == INT_MIN / 10 && pop < -8)) {return 0; // 负数溢出}

• INT_MIN / 10 是 -214748364，即 INT_MIN 除以 10。

这段代码的意思是：

• 如果 reversed 已经小于 INT_MIN / 10，那么再乘以 10 并加上 pop 肯定会溢出。
• 如果 reversed 等于 INT_MIN / 10，那么只有当 pop 小于 -8 时才会溢出（因为 INT_MIN 的个位数是 -8）。

231. 2 的幂 

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：n = 3
输出：false

第一种对但是超时了！

bool isPowerOfTwo(int n) {// 如果 n 等于 1，说明它是 2 的 0 次幂，返回 trueif (n == 1) {return true;}// 如果 n 是负数，不可能是 2 的幂，返回 falseif (n < 0) {return false;}// 如果 n 是奇数且不等于 1，不可能是 2 的幂，返回 falseif (n % 2 == 1) {return false;}// 递归调用，将 n 除以 2，继续判断return isPowerOfTwo(n / 2);
}

第二种是位运算，比较简单速度也快

bool isPowerOfTwo(int n) {if (n<=0){return false;}return (n&(n-1))==0;
}

一个数是 2 的幂，当且仅当它的二进制表示中只有 一个 1，且这个 1 出现在最高位。例如：

• 1 的二进制是 1。
• 2的二进制是 10。
• 4 的二进制是 100。
• 8 的二进制是 1000。

根据这个特性，我们可以通过以下方法判断一个数是否是 2 的幂：

1. 如果 n≤0n≤0，直接返回 false，因为 2 的幂必须是正整数。
2. 利用位运算 n & (n - 1)：
   • 如果 n 是 2 的幂，则 n & (n - 1) 的结果为 0。
   • 例如：8 的二进制是 1000，7 的二进制是 0111，1000 & 0111 = 0000。

342. 4的幂

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

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

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

提示：

• -231 <= n <= 231 - 1

#include <cstdio>// 判断一个整数是否是 4 的幂
bool isPowerOfFour(int n) {// 如果 n 小于等于 0，直接返回 false// 因为 4 的幂必须是正整数if (n <= 0) {return false;}// 判断 n 是否是 2 的幂// 2 的幂的二进制表示中只有一个 1// 例如：1 (1), 2 (10), 4 (100), 8 (1000)// n & (n - 1) 会将最低位的 1 置为 0// 如果 n 是 2 的幂，则 n & (n - 1) == 0if ((n & (n - 1)) != 0) {return false;}// 判断 n 是否是 4 的幂// 4 的幂的二进制表示中，1 只出现在偶数位// 例如：4 (100), 16 (10000), 64 (1000000)// 0xAAAAAAAA 的二进制表示是 10101010...1010// 如果 n & 0xAAAAAAAA == 0，说明 n 的 1 只出现在偶数位return (0xAAAAAAAA & n) == 0;
}int main() {// 测试 isPowerOfFour 函数bool flag = isPowerOfFour(2);// 根据返回值输出结果if (flag) {puts("true");  // 如果是 4 的幂，输出 true} else {puts("false"); // 如果不是 4 的幂，输出 false}return 0;
}

判断 4 的幂的原理

4 的幂的二进制表示中，1 只出现在 奇数位。例如：

• =4，二进制是 100，1 出现在位位置 2（偶数位）。
• =16，二进制是 10000，1 出现在位位置 4（偶数位）。
• =64，二进制是 1000000，1 出现在位位置 6（偶数位）。

4 的幂的二进制表示中，1 只出现在 偶数位。因此，我们可以通过以下步骤判断：

判断是否是 2 的幂：

• 4 的幂一定是 2 的幂，因此首先判断 n 是否是 2 的幂。
• 2 的幂的判断方法：n > 0 && (n & (n - 1)) == 0。

判断 1 是否出现在偶数位：

• 使用掩码 0xAAAAAAAA（二进制为 10101010...1010）提取偶数位。
• 如果 n & 0xAAAAAAAA == 0，说明 1 只出现在偶数位。

0xaaaaaaaa = 10101010101010101010101010101010 (偶数位为1，奇数位为0）

0x55555555 = 1010101010101010101010101010101 (偶数位为0，奇数位为1）

0x33333333 = 110011001100110011001100110011 (1和0每隔两位交替出现)

0xcccccccc = 11001100110011001100110011001100 (0和1每隔两位交替出现)

0x0f0f0f0f = 00001111000011110000111100001111 (1和0每隔四位交替出现)

0xf0f0f0f0 = 11110000111100001111000011110000 (0和1每隔四位交替出现)

 326. 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

直接使用的递归函数哈哈也通过了。

#include <cstdio>// 判断一个整数是否是 3 的幂
bool isPowerOfThree(int n) {// 如果 n 小于等于 0，直接返回 false// 因为 3 的幂必须是正整数if (n <= 0) {return false;}// 如果 n 等于 1，直接返回 true// 因为 3^0 = 1，1 是 3 的幂if (n == 1) {return true;}// 递归调用 isPowerOfThree(n / 3)// 判断 n 是否能被 3 整除，并且 n / 3 也是 3 的幂// 例如：// - 对于 n = 9：9 / 3 = 3，3 是 3 的幂，且 9 % 3 == 0，返回 true// - 对于 n = 10：10 / 3 = 3，3 是 3 的幂，但 10 % 3 != 0，返回 falsereturn isPowerOfThree(n / 3) && n % 3 == 0;
}int main() {// 测试 isPowerOfThree 函数bool flag = isPowerOfThree(45);// 根据返回值输出结果if (flag) {puts("true");  // 如果是 3 的幂，输出 true} else {puts("false"); // 如果不是 3 的幂，输出 false}return 0;
}

504. 七进制数

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

示例 1:

输入: num = 100
输出: "202"

示例 2:

输入: num = -7
输出: "-10"

提示：

• -107 <= num <= 107

#include <cstdio>
#include <cstdlib>// 数组元素逆置函数
void reverse(char* arr, int i) {char temp;// 遍历数组的前半部分，交换元素for (int j = 0; j < i / 2; ++j) {temp = arr[i - j - 1];  // 保存后半部分的元素arr[i - j - 1] = arr[j]; // 将前半部分的元素放到后半部分arr[j] = temp;          // 将保存的后半部分元素放到前半部分}
}// 将整数转换为 7 进制字符串
char* convertToBase7(int num) {// 动态分配一个字符数组，用于存储结果char* arr = (char*)malloc(100 * sizeof(char));int temp = num >= 0 ? num : (0 - num); // 取 num 的绝对值int i = 0; // 用于记录当前字符数组的索引// 如果 num 为 0，直接存储 '0'if (temp == 0) {arr[i++] = '0';}// 将 num 转换为 7 进制while (temp != 0) {int a = temp % 7; // 取当前位的值arr[i++] = a + '0'; // 将数字转换为字符并存储temp /= 7; // 继续处理下一位}// 如果 num 是负数，添加负号并逆置数组if (num < 0) {arr[i] = '-'; // 添加负号arr[i + 1] = '\0'; // 添加字符串结束符reverse(arr, i + 1); // 逆置数组} else {arr[i] = '\0'; // 添加字符串结束符reverse(arr, i); // 逆置数组}return arr; // 返回结果字符串
}int main() {// 测试 convertToBase7 函数char* p = convertToBase7(0);puts(p); // 输出结果// 释放动态分配的内存free(p);return 0;
}

263. 丑数

丑数 就是只包含质因数 2、3 和 5 的 正 整数。

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3

示例 2：

输入：n = 1
输出：true
解释：1 没有质因数。

示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7。

#include <cstdio>// 判断一个整数是否是丑数
bool isUgly(int n) {// 如果 n 小于等于 0，直接返回 false// 因为丑数必须是正整数if (n <= 0) {return false;}// 如果 n 等于 1，直接返回 true// 1 没有质因数，通常认为 1 是丑数if (n == 1) {return true;}int temp = n; // 用 temp 保存 n 的值，避免直接修改 nint flag = 0; // 用于标记是否进行了除法操作// 不断将 temp 除以 2、3 和 5，直到 temp 不能被这些数整除while (temp != 0) {// 如果 temp 能被 2 整除，就除以 2if (temp % 2 == 0) {flag++; // 标记进行了除法操作temp /= 2;}// 如果 temp 能被 3 整除，就除以 3if (temp % 3 == 0) {flag++; // 标记进行了除法操作temp /= 3;}// 如果 temp 能被 5 整除，就除以 5if (temp % 5 == 0) {flag++; // 标记进行了除法操作temp /= 5;}// 如果 flag 为 0，说明 temp 不能被 2、3 或 5 整除，跳出循环if (flag == 0) {break;}flag = 0; // 重置 flag，继续下一轮循环}// 如果最终 temp 等于 1，说明 n 只包含质因数 2、3 和 5，是丑数// 否则，n 不是丑数return temp == 1;
}int main() {bool flag = isUgly(14);if (flag){puts("true");} else{puts("false");}
}

• 如果 flag 为 0，说明 temp 不能被 2、3 或 5 整除，跳出循环。

191. 位1的个数

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 

设置位的个数（也被称为汉明重量）。

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

#include <stdio.h>// 计算一个整数的二进制表示中 1 的个数（汉明重量）
int hammingWeight(int n) {int temp = n; // 用 temp 保存 n 的值，避免直接修改 nint count = 0; // 用于记录 1 的个数// 不断将 temp 除以 2，直到 temp 变为 0while (temp != 0) {int a = temp % 2; // 取 temp 除以 2 的余数if (a == 1) { // 如果余数为 1，说明当前二进制位是 1count++; // 1 的个数加 1}temp /= 2; // 将 temp 右移一位，相当于除以 2}return count; // 返回 1 的个数
}int main() {// 测试 hammingWeight 函数hammingWeight(2147483645); // 2147483645 的二进制表示中有 30 个 1return 0;
}

476. 数字的补数

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

• 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

给你一个整数 num ，输出它的补数。

示例 1：

输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

示例 2：

输入：num = 1
输出：0
解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

#include <cstdio>
#include <cmath>// 找到一个整数的补数
int findComplement(int num) {int temp = num; // 用 temp 保存 num 的值，避免直接修改 numint sum = 0;    // 用于存储补数的结果int a, b;       // a 用于存储当前二进制位，b 用于存储补数位int i = 0;      // 用于记录当前位的权重（2^i）// 不断将 temp 除以 2，直到 temp 变为 0while (temp != 0) {a = temp % 2; // 取 temp 除以 2 的余数，即当前二进制位b = a == 1 ? 0 : 1; // 计算补数位：如果 a 是 1，补数位是 0；否则是 1sum += b * pow(2, i++); // 将补数位乘以 2^i 并累加到 sum 中temp /= 2; // 将 temp 右移一位，相当于除以 2}return sum; // 返回补数的结果
}int main() {// 测试 findComplement 函数printf("%d ", findComplement(1)); // 输出 1 的补数return 0;
}

461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

#include <cstdio>
#include <cmath>// 计算两个整数之间的汉明距离
int hammingDistance(int x, int y) {int a = x ^ y; // 对 x 和 y 进行异或运算，得到 aint n, count = 0; // n 用于存储 a 的二进制位，count 用于记录 1 的个数// 不断将 a 除以 2，直到 a 变为 0while (a != 0) {n = a % 2; // 取 a 除以 2 的余数，即当前二进制位if (n == 1) { // 如果当前二进制位是 1count++; // 1 的个数加 1}a /= 2; // 将 a 右移一位，相当于除以 2}return count; // 返回 1 的个数，即汉明距离
}int main() {// 测试 hammingDistance 函数printf("%d ", hammingDistance(3, 1)); // 输出 3 和 1 之间的汉明距离return 0;
}

异或运算：

• 对 x 和 y 进行异或运算，得到 a。
• 异或运算的特性是：如果两个位相同，结果为 0；如果两个位不同，结果为 1。
• 因此，a 的二进制表示中，1 的个数就是 x 和 y 的汉明距离。