爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。
爱丽丝的分数不超过 n 的概率是多少？
与实际答案误差不超过 10^-5 的答案将被视为正确答案。
示例 1：
输入：n = 10, k = 1, maxPts = 10
输出：1.00000
解释：爱丽丝得到一张牌，然后停止。示例 2：
输入：n = 6, k = 1, maxPts = 10
输出：0.60000
解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。示例 3：
输入：n = 21, k = 17, maxPts = 10
输出：0.73278说明：
给你一个仅由数字 6 和 9 组成的正整数 num。
你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
请返回你可以得到的最大数字。
示例 1：
输入：num = 9669
输出：9969
解释：
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。示例 2：
输入：num = 9996
输出：9999
解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。示例 3：
输入：num = 9999
输出：9999
解释：无需改变就已经是最大的数字了。说明：
有一个由 6 和 9 组成的数字，可以最多将一个 6 变成 9，返回可以得到的最大数字。
将左边第一个 6 变为 9 得到的数字最大。
/**
* @date 2025-08-16 17:09
*/
public class Maximum69Number1323 {
public int maximum69Number(int num) {
int l = String.valueOf(num).length();
int pow10 = (int) Math.pow(10, l - 1);
int n = num;
while (pow10 > 0) {
if (n / pow10 == 6) {
return num + 3 * pow10;
}
n -= 9 * pow10;
pow10 /= 10;
}
return num;
}
}
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4^x
示例 1：
输入：n = 16
输出：true示例 2：
输入：n = 5
输出：false示例 3：
输入：n = 1
输出：true说明：
进阶：你能不使用循环或者递归来完成本题吗？
判断一个整数是否是 4 的幂。
参考 231.2的幂。
负数的二进制表示中前导零的个数为 0，而 4 的幂的前导零个数为奇数，恰好排除掉了负数。
/**
* @date 2025-08-15 8:43
*/
public class IsPowerOfFour342 {
public boolean isPowerOfFour(int n) {
return (n & (n - 1)) == 0 && Integer.numberOfLeadingZeros(n) % 2 == 1;
}
}
给你一个整数 n ，如果你可以将 n 表示成若干个 不同的 三的幂之和，请你返回 true ，否则请返回 false 。
对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。
示例 1：
输入：n = 12
输出：true
解释：12 = 31 + 32示例 2：
输入：n = 91
输出：true
解释：91 = 30 + 32 + 34示例 3：
输入：n = 21
输出：false提示：
判断一个整数 n 能否用若干个 不同的 3 的幂之和表示。
直接的想法是使用 dfs 从小到大判断 3 的幂选或者不选。
从数学的角度考虑，如果 n 的三进制表示中包含 2 那么就无法用不同的三的幂之和表示。
/**
* @date 2025-08-14 9:54
*/
public class CheckPowersOfThree1780 {
class Solution {
public boolean checkPowersOfThree(int n) {
while (n > 0) {
if (n % 3 == 2) {
return false;
}
n /= 3;
}
return true;
}
}
public boolean checkPowersOfThree(int n) {
return dfs(1, 0, n);
}
public boolean dfs(int d, int num, int n) {
if (num == n) {
return true;
} else if (num > n || d > n) {
return false;
}
return dfs(d * 3, num, n) || dfs(d * 3, num + d, n);
}
}
给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x
示例 1：
输入：n = 27
输出：true示例 2：
输入：n = 0
输出：false示例 3：
输入：n = 9
输出：true示例 4：
输入：n = 45
输出：false说明：
进阶：你能不使用循环或者递归来完成本题吗？
判断给定整数 n 是否是 3 的幂。
进阶解法是判断是否为最大的 3 的幂的约数，Integer 范围内最大的 3 的幂为 3^19 = 1162261467，如果 n 是 3 的幂那么一定可以被它整除。
/**
* @date 2025-08-13 8:40
*/
public class IsPowerOfThree326 {
public boolean isPowerOfThree(int n) {
int base = 3;
long num = 1;
while (num <= n) {
if (num == n) {
return true;
}
num *= base;
}
return false;
}
}
给你两个 正 整数 n 和 x 。
请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1^x + n2^x + ... + nk^x 。
由于答案可能非常大，请你将它对 10^9 + 7 取余后返回。
比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 2^3 + 3^3 + 5^3 。
示例 1：
输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 3^2 + 1^2 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。示例 2：
输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 4^1 = 4 。
- n = 3^1 + 1^1 = 4 。说明：
求正整数的 x 次幂之和为 n 的组合数，要求组合中的数字不能重复。
最大正整数 max = n^(1/x)，问题转换为使用 1^x, 2^x, ……, max^x 组成 n 的组合数。
恰好型 0-1 背包。
/**
* @date 2025-08-12 9:08
*/
public class NumberOfWays2787 {
public int numberOfWays(int n, int x) {
int mod = 1000000007;
int max = (int) Math.ceil(Math.pow(n, 1.0 / x));
long[] dp = new long[n + 1];
dp[0] = 1;
for (int i = 1; i <= max; i++) {
int pow = (int) Math.pow(i, x);
for (int j = n; j >= pow; j--) {
dp[j] += dp[j - pow];
}
}
return (int)(dp[n] % mod);
}
}
给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含 最少 数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。
同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。
请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 10^9 + 7 取余 。
示例 1：
输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案：powers[2] = 4 。
第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 10^9 + 7 得到的结果都相同，所以返回 [2,4,64] 。示例 2：
输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 10^9 + 7 取余后结果相同，所以返回 [2] 。说明：
给定一个正整数，将其拆分成最少数目的 2 的幂，即二进制表示中每一个 1 所表示的 2 的幂，按照从小到大的顺序放入 nums。有一个查询数组 queries，queries[i] = [from, to] 表示查询 nums 从 from 到 to 的乘积，返回对应的结果数组。
由于 nums 长度最大 31，因此可以提前预处理所有子数组的乘积，或值直接暴力计算查询范围内的元素乘积。
注意不能计算前缀乘积，为了防止溢出存的是余数，相除后取余并不满足分配律。或者换一种思路计算幂次的前缀和，然后再计算 2 的幂对 mod 取余。
/**
* @date 2025-08-11 9:52
*/
public class ProductQueries2438 {
public int[] productQueries(int n, int[][] queries) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 31; i++) {
int p = 1 << i;
if ((n & p) == p) {
list.add(p);
}
}
int mod = 1000000007;
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int from = queries[i][0];
int to = queries[i][1];
res[i] = 1;
for (int j = from; j <= to; j++) {
res[i] = (int) ((long) res[i] * list.get(j) % mod);
}
}
return res;
}
}
给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：n = 1
输出：true示例 2：
输入：n = 10
输出：false说明：
判断数字重新排列后能否变成 2 的幂。
统计所有数位上数字的出现次数，如果与 2 的幂完全相同则返回 true。
/**
* @date 2025-08-10 13:49
*/
public class ReorderedPowerOf2_869 {
public static int[][] nums = new int[31][10];
static {
for (int i = 0; i < 31; i++) {
int num = 1 << i;
while (num > 0) {
int d = num % 10;
nums[i][d]++;
num /= 10;
}
}
}
public boolean reorderedPowerOf2(int n) {
int[] digits = new int[10];
while (n > 0) {
int d = n % 10;
digits[d]++;
n /= 10;
}
here:
for (int[] num : nums) {
for (int i = 0; i < num.length; i++) {
if (num[i] != digits[i]) {
continue here;
}
}
return true;
}
return false;
}
}
给你一个整数 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提示：
进阶：你能够不使用循环/递归解决此问题吗？
判断数字是不是 2 的幂。
提前预处理 2 的幂。
进阶做法是判断 n & (n - 1) == 0。
/**
* @date 2025-08-09 20:33
*/
public class IsPowerOfTwo231 {
static Set<Integer> set = new HashSet<>();
static {
for (int i = 0; i < 31; i++) {
set.add(1 << i);
}
}
public boolean isPowerOfTwo(int n) {
return set.contains(n);
}
}
你有两种汤，A 和 B，每种初始为 n 毫升。在每一轮中，会随机选择以下四种服务操作中的一种，每种操作的概率为 0.25，且与之前的所有轮次 无关：
注意：
操作过程在任何回合中任一汤被用完后立即停止。
返回汤 A 在 B 前耗尽的概率，加上两种汤在 同一回合 耗尽概率的一半。返回值在正确答案 10^-5 的范围内将被认为是正确的。
示例 1:
输入：n = 50
输出：0.62500
解释：
如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。示例 2:
输入：n = 100
输出：0.71875
解释：
如果我们选择第一个操作，A 首先将变为空。
如果我们选择第二个操作，A 将在执行操作 [1, 2, 3] 时变为空，然后 A 和 B 在执行操作 4 时同时变空。
如果我们选择第三个操作，A 将在执行操作 [1, 2] 时变为空，然后 A 和 B 在执行操作 3 时同时变空。
如果我们选择第四个操作，A 将在执行操作 1 时变为空，然后 A 和 B 在执行操作 2 时同时变空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.71875。说明: