每日一题-24 点游戏🔴

2025年8月18日 00:00

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法，而不是整数除法。
- 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
- 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
- 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。

如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

示例 1:

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24

示例 2:

输入: cards = [1, 2, 1, 2]
输出: false

提示:

cards.length == 4
1 <= cards[i] <= 9

Java 回溯, 经典面试题

LeetCode 每日一题题解

作者 airmelt

2021年6月9日 14:14

微软一面平行面出了这个题, 比这个还麻烦, 给的输入是 n 个数字
用的 Java 回溯解决的, 第一轮已经通过
提一下需要注意的细节

不要使用魔法数字 24, 1e-6 等, 需要使用有意义的变量代替
double 类型不能使用 "==", 需要用做差和一个较小的值比较判断
将函数拆分成几个小的函数分别求解, 可以先提出思路和写一个空函数
从 2 个数字开始逐步扩展
注意不能产生除 0 错误
一旦回溯有一条路能产生 true 需要立即返回

###Java

class Solution {
    private static final double TARGET = 24;
    private static final double EPISLON = 1e-6;
    
    public boolean judgePoint24(int[] cards) {
        return helper(new double[]{ cards[0], cards[1], cards[2], cards[3] });
    }
    
    private boolean helper(double[] nums) {
        if (nums.length == 1) return Math.abs(nums[0] - TARGET) < EPISLON;
        // 每次选择两个不同的数进行回溯
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                // 将选择出来的两个数的计算结果和原数组剩下的数加入 next 数组
                double[] next = new double[nums.length - 1];
                for (int k = 0, pos = 0; k < nums.length; k++) if (k != i && k != j) next[pos++] = nums[k];
                for (double num : calculate(nums[i], nums[j])) {
                    next[next.length - 1] = num;
                    if (helper(next)) return true;
                }
            }
        }
        return false;
    }
    
    private List<Double> calculate(double a, double b) {
        List<Double> list = new ArrayList<>();
        list.add(a + b);
        list.add(a - b);
        list.add(b - a);
        list.add(a * b);
        if (!(Math.abs(b) < EPISLON)) list.add(a / b);
        if (!(Math.abs(a) < EPISLON)) list.add(b / a);
        return list;
    }
}

Python一行大法好!

###Python

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        return sorted(nums) in [[1, 1, 1, 8], [1, 1, 2, 6], [1, 1, 2, 7], [1, 1, 2, 8], [1, 1, 2, 9], [1, 1, 3, 4], [1, 1, 3, 5], [1, 1, 3, 6], [1, 1, 3, 7], [1, 1, 3, 8], [1, 1, 3, 9], [1, 1, 4, 4], [1, 1, 4, 5], [1, 1, 4, 6], [1, 1, 4, 7], [1, 1, 4, 8], [1, 1, 4, 9], [1, 1, 5, 5], [1, 1, 5, 6], [1, 1, 5, 7], [1, 1, 5, 8], [1, 1, 6, 6], [1, 1, 6, 8], [1, 1, 6, 9], [1, 1, 8, 8], [1, 2, 2, 4], [1, 2, 2, 5], [1, 2, 2, 6], [1, 2, 2, 7], [1, 2, 2, 8], [1, 2, 2, 9], [1, 2, 3, 3], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 8], [1, 2, 3, 9], [1, 2, 4, 4], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4, 7], [1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5, 5], [1, 2, 5, 6], [1, 2, 5, 7], [1, 2, 5, 8], [1, 2, 5, 9], [1, 2, 6, 6], [1, 2, 6, 7], [1, 2, 6, 8], [1, 2, 6, 9], [1, 2, 7, 7], [1, 2, 7, 8], [1, 2, 7, 9], [1, 2, 8, 8], [1, 2, 8, 9], [1, 3, 3, 3], [1, 3, 3, 4], [1, 3, 3, 5], [1, 3, 3, 6], [1, 3, 3, 7], [1, 3, 3, 8], [1, 3, 3, 9], [1, 3, 4, 4], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4, 7], [1, 3, 4, 8], [1, 3, 4, 9], [1, 3, 5, 6], [1, 3, 5, 7], [1, 3, 5, 8], [1, 3, 5, 9], [1, 3, 6, 6], [1, 3, 6, 7], [1, 3, 6, 8], [1, 3, 6, 9], [1, 3, 7, 7], [1, 3, 7, 8], [1, 3, 7, 9], [1, 3, 8, 8], [1, 3, 8, 9], [1, 3, 9, 9], [1, 4, 4, 4], [1, 4, 4, 5], [1, 4, 4, 6], [1, 4, 4, 7], [1, 4, 4, 8], [1, 4, 4, 9], [1, 4, 5, 5], [1, 4, 5, 6], [1, 4, 5, 7], [1, 4, 5, 8], [1, 4, 5, 9], [1, 4, 6, 6], [1, 4, 6, 7], [1, 4, 6, 8], [1, 4, 6, 9], [1, 4, 7, 7], [1, 4, 7, 8], [1, 4, 7, 9], [1, 4, 8, 8], [1, 4, 8, 9], [1, 5, 5, 5], [1, 5, 5, 6], [1, 5, 5, 9], [1, 5, 6, 6], [1, 5, 6, 7], [1, 5, 6, 8], [1, 5, 6, 9], [1, 5, 7, 8], [1, 5, 7, 9], [1, 5, 8, 8], [1, 5, 8, 9], [1, 5, 9, 9], [1, 6, 6, 6], [1, 6, 6, 8], [1, 6, 6, 9], [1, 6, 7, 9], [1, 6, 8, 8], [1, 6, 8, 9], [1, 6, 9, 9], [1, 7, 7, 9], [1, 7, 8, 8], [1, 7, 8, 9], [1, 7, 9, 9], [1, 8, 8, 8], [1, 8, 8, 9], [2, 2, 2, 3], [2, 2, 2, 4], [2, 2, 2, 5], [2, 2, 2, 7], [2, 2, 2, 8], [2, 2, 2, 9], [2, 2, 3, 3], [2, 2, 3, 4], [2, 2, 3, 5], [2, 2, 3, 6], [2, 2, 3, 7], [2, 2, 3, 8], [2, 2, 3, 9], [2, 2, 4, 4], [2, 2, 4, 5], [2, 2, 4, 6], [2, 2, 4, 7], [2, 2, 4, 8], [2, 2, 4, 9], [2, 2, 5, 5], [2, 2, 5, 6], [2, 2, 5, 7], [2, 2, 5, 8], [2, 2, 5, 9], [2, 2, 6, 6], [2, 2, 6, 7], [2, 2, 6, 8], [2, 2, 6, 9], [2, 2, 7, 7], [2, 2, 7, 8], [2, 2, 8, 8], [2, 2, 8, 9], [2, 3, 3, 3], [2, 3, 3, 5], [2, 3, 3, 6], [2, 3, 3, 7], [2, 3, 3, 8], [2, 3, 3, 9], [2, 3, 4, 4], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4, 7], [2, 3, 4, 8], [2, 3, 4, 9], [2, 3, 5, 5], [2, 3, 5, 6], [2, 3, 5, 7], [2, 3, 5, 8], [2, 3, 5, 9], [2, 3, 6, 6], [2, 3, 6, 7], [2, 3, 6, 8], [2, 3, 6, 9], [2, 3, 7, 7], [2, 3, 7, 8], [2, 3, 7, 9], [2, 3, 8, 8], [2, 3, 8, 9], [2, 3, 9, 9], [2, 4, 4, 4], [2, 4, 4, 5], [2, 4, 4, 6], [2, 4, 4, 7], [2, 4, 4, 8], [2, 4, 4, 9], [2, 4, 5, 5], [2, 4, 5, 6], [2, 4, 5, 7], [2, 4, 5, 8], [2, 4, 5, 9], [2, 4, 6, 6], [2, 4, 6, 7], [2, 4, 6, 8], [2, 4, 6, 9], [2, 4, 7, 7], [2, 4, 7, 8], [2, 4, 7, 9], [2, 4, 8, 8], [2, 4, 8, 9], [2, 4, 9, 9], [2, 5, 5, 7], [2, 5, 5, 8], [2, 5, 5, 9], [2, 5, 6, 6], [2, 5, 6, 7], [2, 5, 6, 8], [2, 5, 6, 9], [2, 5, 7, 7], [2, 5, 7, 8], [2, 5, 7, 9], [2, 5, 8, 8], [2, 5, 8, 9], [2, 6, 6, 6], [2, 6, 6, 7], [2, 6, 6, 8], [2, 6, 6, 9], [2, 6, 7, 8], [2, 6, 7, 9], [2, 6, 8, 8], [2, 6, 8, 9], [2, 6, 9, 9], [2, 7, 7, 8], [2, 7, 8, 8], [2, 7, 8, 9], [2, 8, 8, 8], [2, 8, 8, 9], [2, 8, 9, 9], [3, 3, 3, 3], [3, 3, 3, 4], [3, 3, 3, 5], [3, 3, 3, 6], [3, 3, 3, 7], [3, 3, 3, 8], [3, 3, 3, 9], [3, 3, 4, 4], [3, 3, 4, 5], [3, 3, 4, 6], [3, 3, 4, 7], [3, 3, 4, 8], [3, 3, 4, 9], [3, 3, 5, 5], [3, 3, 5, 6], [3, 3, 5, 7], [3, 3, 5, 9], [3, 3, 6, 6], [3, 3, 6, 7], [3, 3, 6, 8], [3, 3, 6, 9], [3, 3, 7, 7], [3, 3, 7, 8], [3, 3, 7, 9], [3, 3, 8, 8], [3, 3, 8, 9], [3, 3, 9, 9], [3, 4, 4, 4], [3, 4, 4, 5], [3, 4, 4, 6], [3, 4, 4, 7], [3, 4, 4, 8], [3, 4, 4, 9], [3, 4, 5, 5], [3, 4, 5, 6], [3, 4, 5, 7], [3, 4, 5, 8], [3, 4, 5, 9], [3, 4, 6, 6], [3, 4, 6, 8], [3, 4, 6, 9], [3, 4, 7, 7], [3, 4, 7, 8], [3, 4, 7, 9], [3, 4, 8, 9], [3, 4, 9, 9], [3, 5, 5, 6], [3, 5, 5, 7], [3, 5, 5, 8], [3, 5, 5, 9], [3, 5, 6, 6], [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9], [3, 5, 7, 8], [3, 5, 7, 9], [3, 5, 8, 8], [3, 5, 8, 9], [3, 5, 9, 9], [3, 6, 6, 6], [3, 6, 6, 7], [3, 6, 6, 8], [3, 6, 6, 9], [3, 6, 7, 7], [3, 6, 7, 8], [3, 6, 7, 9], [3, 6, 8, 8], [3, 6, 8, 9], [3, 6, 9, 9], [3, 7, 7, 7], [3, 7, 7, 8], [3, 7, 7, 9], [3, 7, 8, 8], [3, 7, 8, 9], [3, 7, 9, 9], [3, 8, 8, 8], [3, 8, 8, 9], [3, 8, 9, 9], [3, 9, 9, 9], [4, 4, 4, 4], [4, 4, 4, 5], [4, 4, 4, 6], [4, 4, 4, 7], [4, 4, 4, 8], [4, 4, 4, 9], [4, 4, 5, 5], [4, 4, 5, 6], [4, 4, 5, 7], [4, 4, 5, 8], [4, 4, 6, 8], [4, 4, 6, 9], [4, 4, 7, 7], [4, 4, 7, 8], [4, 4, 7, 9], [4, 4, 8, 8], [4, 4, 8, 9], [4, 5, 5, 5], [4, 5, 5, 6], [4, 5, 5, 7], [4, 5, 5, 8], [4, 5, 5, 9], [4, 5, 6, 6], [4, 5, 6, 7], [4, 5, 6, 8], [4, 5, 6, 9], [4, 5, 7, 7], [4, 5, 7, 8], [4, 5, 7, 9], [4, 5, 8, 8], [4, 5, 8, 9], [4, 5, 9, 9], [4, 6, 6, 6], [4, 6, 6, 7], [4, 6, 6, 8], [4, 6, 6, 9], [4, 6, 7, 7], [4, 6, 7, 8], [4, 6, 7, 9], [4, 6, 8, 8], [4, 6, 8, 9], [4, 6, 9, 9], [4, 7, 7, 7], [4, 7, 7, 8], [4, 7, 8, 8], [4, 7, 8, 9], [4, 7, 9, 9], [4, 8, 8, 8], [4, 8, 8, 9], [4, 8, 9, 9], [5, 5, 5, 5], [5, 5, 5, 6], [5, 5, 5, 9], [5, 5, 6, 6], [5, 5, 6, 7], [5, 5, 6, 8], [5, 5, 7, 7], [5, 5, 7, 8], [5, 5, 8, 8], [5, 5, 8, 9], [5, 5, 9, 9], [5, 6, 6, 6], [5, 6, 6, 7], [5, 6, 6, 8], [5, 6, 6, 9], [5, 6, 7, 7], [5, 6, 7, 8], [5, 6, 7, 9], [5, 6, 8, 8], [5, 6, 8, 9], [5, 6, 9, 9], [5, 7, 7, 9], [5, 7, 8, 8], [5, 7, 8, 9], [5, 8, 8, 8], [5, 8, 8, 9], [6, 6, 6, 6], [6, 6, 6, 8], [6, 6, 6, 9], [6, 6, 7, 9], [6, 6, 8, 8], [6, 6, 8, 9], [6, 7, 8, 9], [6, 7, 9, 9], [6, 8, 8, 8], [6, 8, 8, 9], [6, 8, 9, 9], [7, 8, 8, 9]]

【详解】递归回溯，考察基本功 | 679. 24点游戏

LeetCode 每日一题题解

作者 xiao_ben_zhu

2020年8月22日 08:17

思路

游戏的第一步是挑出两个数，算出一个新数替代这两个数。
然后，在三个数中玩 24 点，再挑出两个数，算出一个数替代它们。
然后，在两个数中玩 24 点……

很明显的递归思路。每次递归都会挑出两个数，我们尝试挑出不同的两数组合：

挑 1、2，基于它，继续递归。
挑 1、3，基于它，继续递归。
挑 ……

即通过两层 for 循环，枚举所有的两数组合，展开出不同选择所对应的递归分支。

挑出的每一对数，我们…

枚举出所有可能的运算操作：加减乘除…——（对应不同的递归调用）
逐个尝试每一种运算——（选择进入一个递归分支）
传入长度变小的新数组继续递归——（递归计算子问题）
当递归到只剩一个数——（到达了递归树的底部），看看是不是 24 。
- 是就返回 true——结束当前递归，并且控制它不进入别的递归分支，整个结束掉。
- 否则返回 false，离开错误的分支，进入别的递归分支，尝试别的运算。

剪枝小技巧

当递归返回 true，代表游戏成功，不用继续探索了，剩下的搜索分支全部砍掉。怎么做到？

代码如下。标识变量isValid初始为 false，默认会执行||后面的递归。
一旦某个递归返回真，isValid就变为真，由于||的短路特性，后面的递归不会执行。
所有递归子调用都这么写，isValid就像一个开关，避免写很多判断语句。

###js

isValid = isValid || judgePoint24([...newNums, n1 + n2]);
isValid = isValid || judgePoint24([...newNums, n1 - n2]);
isValid = isValid || judgePoint24([...newNums, n2 - n1]);
isValid = isValid || judgePoint24([...newNums, n1 * n2]);
// ...

代码

const judgePoint24 = (nums) => {
    const len = nums.length;
    if (len == 1) {                // 递归的出口
        return Math.abs(nums[0] - 24) < 1e-9;
    }
    let isValid = false;           // 用于控制是否进入递归

    for (let i = 0; i < len; i++) { // 两层循环，枚举出所有的两数组合
        for (let j = i + 1; j < len; j++) {
            const n1 = nums[i];
            const n2 = nums[j];     // 选出的两个数 n1 n2
            const newNums = [];     // 存放剩下的两个数
            for (let k = 0; k < len; k++) {
                if (k != i && k != j) {  // 剔除掉选出的两个数
                    newNums.push(nums[k]);
                }
            }
            // 加
            isValid = isValid || judgePoint24([...newNums, n1 + n2]);
            // 减与被减
            isValid = isValid || judgePoint24([...newNums, n1 - n2]);
            isValid = isValid || judgePoint24([...newNums, n2 - n1]);
            // 乘
            isValid = isValid || judgePoint24([...newNums, n1 * n2]);
            if (n2 !== 0) { // 除
                isValid = isValid || judgePoint24([...newNums, n1 / n2]);
            }
            if (n1 !== 0) { // 被除
                isValid = isValid || judgePoint24([...newNums, n2 / n1]);
            }
            if (isValid) {
                return true;
            }
        }
    }
    return false; // 遍历结束，始终没有返回真，则返回false
};

func judgePoint24(nums []int) bool {
floatNums := make([]float64, len(nums))
for i := range floatNums {
floatNums[i] = float64(nums[i])
}
return dfs(floatNums)
}

func dfs(nums []float64) bool {
if len(nums) == 1 {
return math.Abs(nums[0]-24) < 1e-9
}
flag := false
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
n1, n2 := nums[i], nums[j]
newNums := make([]float64, 0, len(nums))
for k := 0; k < len(nums); k++ {
if k != i && k != j {
newNums = append(newNums, nums[k])
}
}
flag = flag || dfs(append(newNums, n1+n2))
flag = flag || dfs(append(newNums, n1-n2))
flag = flag || dfs(append(newNums, n2-n1))
flag = flag || dfs(append(newNums, n1*n2))
if n1 != 0 {
flag = flag || dfs(append(newNums, n2/n1))
}
if n2 != 0 {
flag = flag || dfs(append(newNums, n1/n2))
}
if flag {
return true
}
}
}
return false
}

执行情况

Runtime: 68 ms, faster than 100.00% of JavaScript online submissions for 24 Game.
Runtime: 0 ms, faster than 100.00% of Go online submissions for 24 Game.

感谢阅读，文字经过反复修改打磨，希望你能感受到这份真诚。欢迎提出建议。

最后修改于：2022-01-10

24 点游戏

LeetCode 每日一题题解

作者 LeetCode-Solution

2020年8月21日 23:25

方法一：回溯

一共有 $4$ 个数和 $3$ 个运算操作，因此可能性非常有限。一共有多少种可能性呢？

首先从 $4$ 个数字中有序地选出 $2$ 个数字，共有 $4 \times 3=12$ 种选法，并选择加、减、乘、除 $4$ 种运算操作之一，用得到的结果取代选出的 $2$ 个数字，剩下 $3$ 个数字。

然后在剩下的 $3$ 个数字中有序地选出 $2$ 个数字，共有 $3 \times 2=6$ 种选法，并选择 $4$ 种运算操作之一，用得到的结果取代选出的 $2$ 个数字，剩下 $2$ 个数字。

最后剩下 $2$ 个数字，有 $2$ 种不同的顺序，并选择 $4$ 种运算操作之一。

因此，一共有 $12 \times 4 \times 6 \times 4 \times 2 \times 4=9216$ 种不同的可能性。

可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 $2$ 个数字，再选择一种运算操作，用计算得到的结果取代选出的 $2$ 个数字，这样列表中的数字就减少了 $1$ 个。重复上述步骤，直到列表中只剩下 $1$ 个数字，这个数字就是一种可能性的结果，如果结果等于 $24$，则说明可以通过运算得到 $24$。如果所有的可能性的结果都不等于 $24$，则说明无法通过运算得到 $24$。

实现时，有一些细节需要注意。

除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 $24$ 时应考虑精度误差，这道题中，误差小于 $10^{-6}$ 可以认为是相等。
进行除法运算时，除数不能为 $0$，如果遇到除数为 $0$ 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 $0$ 时应考虑精度误差，这道题中，当一个数字的绝对值小于 $10^{-6}$ 时，可以认为该数字等于 $0$。

还有一个可以优化的点。

加法和乘法都满足交换律，因此如果选择的运算操作是加法或乘法，则对于选出的 $2$ 个数字不需要考虑不同的顺序，在遇到第二种顺序时可以不进行运算，直接跳过。

###Java

class Solution {
    static final int TARGET = 24;
    static final double EPSILON = 1e-6;
    static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<Double>();
        for (int num : nums) {
            list.add((double) num);
        }
        return solve(list);
    }

    public boolean solve(List<Double> list) {
        if (list.size() == 0) {
            return false;
        }
        if (list.size() == 1) {
            return Math.abs(list.get(0) - TARGET) < EPSILON;
        }
        int size = list.size();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i != j) {
                    List<Double> list2 = new ArrayList<Double>();
                    for (int k = 0; k < size; k++) {
                        if (k != i && k != j) {
                            list2.add(list.get(k));
                        }
                    }
                    for (int k = 0; k < 4; k++) {
                        if (k < 2 && i > j) {
                            continue;
                        }
                        if (k == ADD) {
                            list2.add(list.get(i) + list.get(j));
                        } else if (k == MULTIPLY) {
                            list2.add(list.get(i) * list.get(j));
                        } else if (k == SUBTRACT) {
                            list2.add(list.get(i) - list.get(j));
                        } else if (k == DIVIDE) {
                            if (Math.abs(list.get(j)) < EPSILON) {
                                continue;
                            } else {
                                list2.add(list.get(i) / list.get(j));
                            }
                        }
                        if (solve(list2)) {
                            return true;
                        }
                        list2.remove(list2.size() - 1);
                    }
                }
            }
        }
        return false;
    }
}

###C++

class Solution {
public:
    static constexpr int TARGET = 24;
    static constexpr double EPSILON = 1e-6;
    static constexpr int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

    bool judgePoint24(vector<int> &nums) {
        vector<double> l;
        for (const int &num : nums) {
            l.emplace_back(static_cast<double>(num));
        }
        return solve(l);
    }

    bool solve(vector<double> &l) {
        if (l.size() == 0) {
            return false;
        }
        if (l.size() == 1) {
            return fabs(l[0] - TARGET) < EPSILON;
        }
        int size = l.size();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i != j) {
                    vector<double> list2 = vector<double>();
                    for (int k = 0; k < size; k++) {
                        if (k != i && k != j) {
                            list2.emplace_back(l[k]);
                        }
                    }
                    for (int k = 0; k < 4; k++) {
                        if (k < 2 && i > j) {
                            continue;
                        }
                        if (k == ADD) {
                            list2.emplace_back(l[i] + l[j]);
                        } else if (k == MULTIPLY) {
                            list2.emplace_back(l[i] * l[j]);
                        } else if (k == SUBTRACT) {
                            list2.emplace_back(l[i] - l[j]);
                        } else if (k == DIVIDE) {
                            if (fabs(l[j]) < EPSILON) {
                                continue;
                            }
                            list2.emplace_back(l[i] / l[j]);
                        }
                        if (solve(list2)) {
                            return true;
                        }
                        list2.pop_back();
                    }
                }
            }
        }
        return false;
    }
};

###C

const int TARGET = 24;
const double EPSILON = 1e-6;
const int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

bool solve(double *l, int l_len) {
    if (l_len == 0) {
        return false;
    }
    if (l_len == 1) {
        return fabs(l[0] - TARGET) < EPSILON;
    }
    int size = l_len;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (i != j) {
                double list2[20];
                int l2_len = 0;
                for (int k = 0; k < size; k++) {
                    if (k != i && k != j) {
                        list2[l2_len++] = l[k];
                    }
                }
                for (int k = 0; k < 4; k++) {
                    if (k < 2 && i > j) {
                        continue;
                    }
                    if (k == ADD) {
                        list2[l2_len++] = l[i] + l[j];
                    } else if (k == MULTIPLY) {
                        list2[l2_len++] = l[i] * l[j];
                    } else if (k == SUBTRACT) {
                        list2[l2_len++] = l[i] - l[j];
                    } else if (k == DIVIDE) {
                        if (fabs(l[j]) < EPSILON) {
                            continue;
                        }
                        list2[l2_len++] = l[i] / l[j];
                    }
                    if (solve(list2, l2_len)) {
                        return true;
                    }
                    l2_len--;
                }
            }
        }
    }
    return false;
}

bool judgePoint24(int *nums, int numsSize) {
    double l[20];
    int l_len = 0;
    for (int i = 0; i < numsSize; i++) {
        l[l_len++] = nums[i];
    }
    return solve(l, l_len);
}

###Python

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        TARGET = 24
        EPSILON = 1e-6
        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3

        def solve(nums: List[float]) -> bool:
            if not nums:
                return False
            if len(nums) == 1:
                return abs(nums[0] - TARGET) < EPSILON
            for i, x in enumerate(nums):
                for j, y in enumerate(nums):
                    if i != j:
                        newNums = list()
                        for k, z in enumerate(nums):
                            if k != i and k != j:
                                newNums.append(z)
                        for k in range(4):
                            if k < 2 and i > j:
                                continue
                            if k == ADD:
                                newNums.append(x + y)
                            elif k == MULTIPLY:
                                newNums.append(x * y)
                            elif k == SUBTRACT:
                                newNums.append(x - y)
                            elif k == DIVIDE:
                                if abs(y) < EPSILON:
                                    continue
                                newNums.append(x / y)
                            if solve(newNums):
                                return True
                            newNums.pop()
            return False

        return solve(nums)

###golang

const (
    TARGET = 24
    EPSILON = 1e-6
    ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3
)

func judgePoint24(nums []int) bool {
    list := []float64{}
    for _, num := range nums {
        list = append(list, float64(num))
    }
    return solve(list)
}

func solve(list []float64) bool {
    if len(list) == 0 {
        return false
    }
    if len(list) == 1 {
        return abs(list[0] - TARGET) < EPSILON
    }
    size := len(list)
    for i := 0; i < size; i++ {
        for j := 0; j < size; j++ {
            if i != j {
                list2 := []float64{}
                for k := 0; k < size; k++ {
                    if k != i && k != j {
                        list2 = append(list2, list[k])
                    }
                }
                for k := 0; k < 4; k++ {
                    if k < 2 && i < j {
                        continue
                    }
                    switch k {
                    case ADD:
                        list2 = append(list2, list[i] + list[j])
                    case MULTIPLY:
                        list2 = append(list2, list[i] * list[j])
                    case SUBTRACT:
                        list2 = append(list2, list[i] - list[j])
                    case DIVIDE:
                        if abs(list[j]) < EPSILON {
                            continue
                        } else {
                            list2 = append(list2, list[i] / list[j])
                        }
                    }
                    if solve(list2) {
                        return true
                    }
                    list2 = list2[:len(list2) - 1]
                }
            }
        }
    }
    return false
}

func abs(x float64) float64 {
    if x < 0 {
        return -x
    }
    return x
}

复杂度分析

时间复杂度：$O(1)$。一共有 $9216$ 种可能性，对于每种可能性，各项操作的时间复杂度都是 $O(1)$，因此总时间复杂度是 $O(1)$。
空间复杂度：$O(1)$。空间复杂度取决于递归调用层数与存储中间状态的列表，因为一共有 $4$ 个数，所以递归调用的层数最多为 $4$，存储中间状态的列表最多包含 $4$ 个元素，因此空间复杂度为常数。

LeetCode 每日一题题解
滑动窗口优化 DP，简洁写法（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2025年8月17日 07:20

滑动窗口优化 DP，简洁写法（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2025年8月17日 07:20

寻找子问题

我们要解决的问题（原问题）是：

从 $0$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。

用「枚举选哪个」思考，即枚举我们获得多少分：

有 $\dfrac{1}{\textit{maxPts}}$ 的概率获得 $1$ 分，问题变成从 $1$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。
有 $\dfrac{1}{\textit{maxPts}}$ 的概率获得 $2$ 分，问题变成从 $2$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。
有 $\dfrac{1}{\textit{maxPts}}$ 的概率获得 $3$ 分，问题变成从 $3$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。
……
有 $\dfrac{1}{\textit{maxPts}}$ 的概率获得 $\textit{maxPts}$ 分，问题变成从 $\textit{maxPts}$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。

这些问题都是和原问题相似的、规模更小的子问题。

状态定义与状态转移方程

根据上面的讨论，定义 $f[i]$ 表示从 $i$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。

在当前回合，我们等概率地发生以下 $\textit{\textit{maxPts}}$ 种事件：

获得 $1$ 分。问题变成从 $i+1$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率，即 $f[i+1]$。
获得 $2$ 分。问题变成从 $i+2$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率，即 $f[i+2]$。
获得 $3$ 分。问题变成从 $i+3$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率，即 $f[i+3]$。
……
获得 $\textit{maxPts}$ 分。问题变成从 $i+\textit{maxPts}$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率，即 $f[i+\textit{maxPts}]$。

由于上述 $\textit{\textit{maxPts}}$ 种事件互斥且等概率地被选择，因此最终到达闭区间 $[k,n]$ 的概率为上述 $\textit{\textit{maxPts}}$ 个状态值的平均值，即

$$
f[i] = \dfrac{f[i+1] + f[i+2] + f[i+3] + \dots + f[i+\textit{maxPts}]}{\textit{maxPts}}
$$

由于转移来源比 $i$ 大，所以要倒序枚举 $i$。

由于转移方程中的分子是一个长度固定为 $\textit{maxPts}$ 的连续子数组的元素和，所以可以用定长滑动窗口 $\mathcal{O}(1)$ 计算，原理讲解请看【套路】教你解决定长滑窗！适用于所有定长滑窗题目！

初始值：

当 $k\le i\le n$ 时，游戏结束，由于到达闭区间 $[k,n]$，所以 $f[i]=1$。
当 $i > n$ 时，游戏结束，由于在闭区间 $[k,n]$ 外，所以 $f[i]=0$。代码实现时，可以直接创建大小为 $n+1$ 的 $f$ 数组，下标出界就表示 $f[i]=0$。

答案：$f[0]$，即原问题。

答疑

问：为什么滑动窗口的计算顺序不是「入-计算-出」，而是「计算-入-出」？

答：当我们遍历到 $i$ 时，窗口的左端点是 $i+1$ 而不是 $i$。所以 $f[i]$ 并不在窗口中，得先把 $f[i]$ 计算出来，然后下个循环 $f[i]$ 才在窗口中。

注：$n$ 可以与 $k+\textit{maxPts}$ 取 $\min$，但测试发现这个优化不显著。

###py

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        f = [0.0] * (n + 1)
        s = 0.0
        for i in range(n, -1, -1):
            f[i] = 1.0 if i >= k else s / maxPts
            # 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
            # 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
            s += f[i]
            if i + maxPts <= n:
                s -= f[i + maxPts]
        return f[0]

###java

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        double[] f = new double[n + 1];
        double s = 0;
        for (int i = n; i >= 0; i--) {
            f[i] = i >= k ? 1 : s / maxPts;
            // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
            // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
            s += f[i];
            if (i + maxPts <= n) {
                s -= f[i + maxPts];
            }
        }
        return f[0];
    }
}

###cpp

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        vector<double> f(n + 1);
        double s = 0;
        for (int i = n; i >= 0; i--) {
            f[i] = i >= k ? 1 : s / maxPts;
            // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
            // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
            s += f[i];
            if (i + maxPts <= n) {
                s -= f[i + maxPts];
            }
        }
        return f[0];
    }
};

###c

double new21Game(int n, int k, int maxPts) {
    double* f = malloc((n + 1) * sizeof(double));
    double s = 0;

    for (int i = n; i >= 0; i--) {
        f[i] = i >= k ? 1 : s / maxPts;
        // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
        // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
        s += f[i];
        if (i + maxPts <= n) {
            s -= f[i + maxPts];
        }
    }

    double ans = f[0];
    free(f);
    return ans;
}

###go

func new21Game(n, k, maxPts int) float64 {
f := make([]float64, n+1)
s := 0.0
for i := n; i >= 0; i-- {
if i >= k {
f[i] = 1 // 初始值
} else {
f[i] = s / float64(maxPts)
}
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i]
if i+maxPts <= n {
s -= f[i+maxPts]
}
}
return f[0]
}

###js

var new21Game = function(n, k, maxPts) {
    const f = new Array(n + 1).fill(0);
    let s = 0;
    for (let i = n; i >= 0; i--) {
        f[i] = i >= k ? 1 : s / maxPts;
        // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
        // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
        s += f[i];
        if (i + maxPts <= n) {
            s -= f[i + maxPts];
        }
    }
    return f[0];
};

###rust

impl Solution {
    pub fn new21_game(n: i32, k: i32, max_pts: i32) -> f64 {
        let n = n as usize;
        let k = k as usize;
        let max_pts = max_pts as usize;
        let mut f = vec![0.0; n + 1];
        let mut s = 0.0;
        for i in (0..=n).rev() {
            f[i] = if i >= k { 1.0 } else { s / max_pts as f64 };
            // 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
            // 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
            s += f[i];
            if i + max_pts <= n {
                s -= f[i + max_pts];
            }
        }
        f[0]
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面动态规划题单的「十五、概率/期望 DP」和「§11.1 前缀和优化 DP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

每日一题-新 21 点🟡

LeetCode 每日一题题解

2025年8月17日 00:00

爱丽丝参与一个大致基于纸牌游戏 “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

提示：

0 <= k <= n <= 10⁴
1 <= maxPts <= 10⁴

还有比这更简单的题解吗？填格子游戏开始

LeetCode 每日一题题解

作者 Mcdull0921

2020年6月3日 11:25

解题思路

老实说，一开始没懂题目意思，后面才知道是求爱丽丝的胜率。
规则是这样：

她可以从牌面为 [1,W] 的牌中选择任意一张，这张牌是可以无限重复的，也就是说无论她取多少次，每次取到 2（假如 2 在 [1,W] 范围内）的概率都是 1/W;
如果她手上牌的总额小于 K，她就会抽牌，大于等于 K 时，就停止抽牌;
停止抽牌后，她的牌面小于等于 N 时，她就获胜了，求她获胜的概率。

假设 dp[x] 为她手上牌面为x时，能获胜的概率，那么这个概率应该是：
dp[x]=1/w * (dp[x+1]+dp[x+2]+dp[x+3]...+dp[x+w])
因为抽取的牌面机会都是均等的，她能抽取的面值在 [1,W] 之间，所以将概率之和平均一下就是 dp[x] 的概率。

强插一段解释：
x代表爱丽丝手上的牌面值，dp[x]代表爱丽丝手上持有的牌面值为x时，她获胜的概率（游戏结束时她所持牌面值小于等于N的概率）。
这个概率是怎么来的？x分2种情况:

当x>=K时，爱丽丝会停止抽牌，这个时候游戏已经结束了，她是赢是输也已经确定了，所以此时赢的概率要么1，要么0

当x<K时，爱丽丝会继续抽牌，抽牌是有概率的，所以她是赢是输也有概率。
她能抽到的牌面值在 [1,W] 之间，所以抽完后她的牌面在[x+1,x+w]之间，因为每张牌机率均等，所以抽完后牌面在[x+1,x+w]之间的每个面值概率都是相等的，而假如我们已知当牌面是[x+1,x+w]的胜率(即dp[x+1]...dp[x+w]的值)，那么可以推导：
dp[x]=1/w * dp[x+1]+ 1/w * dp[x+2] + 1/w * dp[x+3]...+ 1/w * dp[x+w]
这个实际上就是动态规划的状态转移方程，不过本例是反着来转移的。

x 最多能到 K-1，因为当大于等于 K 时，爱丽丝会停止抽牌，所以当游戏结束时，即爱丽丝停止抽牌时，她可能达到的最大牌面是 K+W-1，而一开始她的牌面是 0，所以我们用一个长度为 K+W 的 dp 数组来保存她在所有面值下的胜率。
最后 dp[0]，也就是最开始爱丽丝还没有抽牌，她的牌面为 0 时的胜率，这个就是我们的答案。

填格子游戏开始

我将这个格子分成了 2 部分 [0,K-1] 和 [K,K+W-1]，区别就是 [0,K-1] 爱丽丝可以抽牌，[K,K+W-1] 时不能抽牌，那么不能抽牌时她获胜的概率是多少呢，此时已不能抽牌，要么赢要么输，很显然牌面小于等于N时，概率就是 1，大于 N 概率就是 0，所以先直接填满图中蓝色的格子。

接下来，从 K-1 开始填图中的橘色部分，这个值根据我们前面提到的计算方式，实际上就相当于它后面 W 个格子的总和除以 W，
这时聪明的你一定会想到不用每轮都累加的方法吧，用一个 s 变量来保存累加结果，而下一轮只是减去右边的格子，加上左边的格子即可。

所以这题你要做的就是，先初始化蓝色格子，然后从最右边的橘色格子开始，填到最左边的格子，就是这么简单，不仅简单，而且你连动态规划的思想都学会了。
相信这么厉害的你，看到这里给我点个赞一定不是件很困难的事吧。

代码

###Python3

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp=[None]*(K+W)
        s=0
        for i in range(K,K+W):          # 填蓝色的格子
            dp[i] = 1 if i<=N else 0
            s+=dp[i]
        for i in range(K-1,-1,-1):      # 填橘黄色格子
            dp[i]=s/W
            s=s-dp[i+W]+dp[i]
        return dp[0]

时间复杂度=格子长度 $O(K+W)$
空间复杂度=格子长度 $O(K+W)$

怎样得到官方题解中的状态转移方程

LeetCode 每日一题题解

作者 sour-e

2020年6月3日 05:56

怎样推导出官方题解中的状态转移方程

按照官方题解的说明，$dp[x]$ 表示从得分为$x$的情况开始游戏并且获胜的概率，如果我们引入 $x_t=x$ 表示$t$ 时刻的总分是 $x$，那么 $dp[x]$ 用条件概率可以写作
$$
dp[x] = P(win | x_t = x)
$$
我们怎么利用这个条件概率来得到题解中的状态转移方程呢？从条件概率可以联想到全概率公式。拿总分 $x=K - 1$ 为例，
$$
dp[K - 1] = P(win | x_t = K - 1) \
= \sum_{i=1}^{W} P(win | x_{t+1} = K - 1 + i) P(x_{t + 1} = K - 1 + i | x_t = K - 1)
$$
其中，$P(x_{t + 1} = K - 1 + i | x_t = K - 1)$ 表示，在 $t$ 时刻，一次抽取后，总分从 $K - 1$ 变成 $K - 1 + i$ 的概率，这实际上就是当前抽到数字 $i$ 的概率，根据题目

抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率

我们知道在任意时刻抽取得到 ${1, 2, .., W}$ 的概率相同（抽取的数字服从离散型均匀分布），即
$$
P(x_{t + 1} = K - 1 + i | x_t = K - 1) = P(\Delta x_t = i) = \frac{1}{W}
$$
另外，$P(win | x_{t+1} = K - 1 + i) = dp[K - 1 + i]$，我们就得到了官方题解里的状态转移方程
$$
dp[K - 1] = P(win | x_t = K - 1) \
= \sum_{i=1}^{W} P(x_{t + 1} = K - 1 + i | x_t = K - 1) P(win | x_{t+1} = K - 1 + i) \
= \sum_{i=1}^{W} \frac{1}{W} \cdot dp[K - 1 + i]\
= \frac{dp[K] + dp[K + 1] + ... + dp[K - 1 + W]}{W}
$$

延申

我们定义的$t$时刻总分$x_t$其实是一个马尔科夫链
- 它有马尔可夫性$P(x_{t+1}| x_{t}, x_{t - 1}, ..., x_{1}) = P(x_{t+1} | x_{t})$，即下一状态（抽一次后的总分）的分布只与当前状态（当前总分）有关，而与之前的状态（之前的总分）无关。
- 在题目中我们仅关心抽取一次后的总分概率$P(x_{t+1} = j| x_{t} = i)$，这个概率与当前时间$t$无关，这样的马尔科夫链叫齐次马尔科夫链。
- 我们进而可以把上述概率写作$P(x_{t+1} = j| x_{t} = i) = p_{i,j}$，$p_{i,j}$也被称作一步转移概率，相应地也有$n$步转移概率$P(x_{t+n} = j| x_{t} = i) = p_{i,j}^{(n)}$，即抽取n次后总分$x_{t+n}$的分布，$n$步转移概率需要用C-K方程求解。
题目中，抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率的条件对玩家每一次抽取到数字的分布做出了假设，即假设 “无论玩家当前总分是多少，玩家抽到任意数字的概率都相等”，用转移概率表示就是 $P(x_{t + 1} = x + i | x_t = x) = \frac{1}{W}$，其中 $i \in {1,2,..,W}$，考虑以下两种情况
- 假设玩家当前收到数字的概率与其当前总分有关，即 $P(x_{t + 1} = x + i | x_t = x) = f(x, W)$，比如在一些赌场，玩家当前总分越高，发牌器中混入更多大牌，给玩家发到小牌的概率越小，玩家更容易爆掉。
- 假设玩家当前收到数字的概率不仅与其当前总分有关，还和玩家游玩时间有关，即 $P(x_{t + 1} = x + i | x_t = x) = f(x, W, t)$，比如在一些赌场，玩家游玩时间越久，发牌器中混入的大牌越多，给玩家发到小牌的概率越小，让玩家更容易爆掉。
第一种情况和原题类似，同属于齐次马尔可夫链（即转移概率不随时间变化而变化），第二种情况属于非齐次马尔科夫链，求解更加复杂。
如果我们把上面 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率 的条件改为 抽取时，她从 [0, 1] 两个数字中抽取W次，以W次抽取结果的和作为分数进行累计，其中 W 是整数，那么每一次增加的分数将服从$n=M$, $p=0.5$的二项分布，状态转移方程也将随之改变为
$$
dp[K - 1]
= \sum_{i=0}^{W} C^{i}_{W} (\frac{1}{2})^{W-i} (\frac{1}{2})^{i} \cdot dp[K - 1 + i]\
= \frac{dp[K - 1] + W \cdot dp[K] + \frac{W(W-1)}{2} \cdot dp[K + 1] + ... + dp[K - 1 + W]}{2^W}
$$

新21点

LeetCode 每日一题题解

作者 LeetCode-Solution

2020年6月2日 19:02

📺视频题解

837. 新21点 4.mp4

📖文字题解

方法一：动态规划

爱丽丝获胜的概率只和下一轮开始前的得分有关，因此根据得分计算概率。

令 $\textit{dp}[x]$ 表示从得分为 $x$ 的情况开始游戏并且获胜的概率，目标是求 $\textit{dp}[0]$ 的值。

根据规则，当分数达到或超过 $k$ 时游戏结束，游戏结束时，如果分数不超过 $n$ 则获胜，如果分数超过 $n$ 则失败。因此当 $k \le x \le \min(n, k+\textit{maxPts}-1)$ 时有 $\textit{dp}[x]=1$，当 $x>\min(n, k+\textit{maxPts}-1)$ 时有 $\textit{dp}[x]=0$。

为什么分界线是 $\min(n, k+\textit{maxPts}-1)$？首先，只有在分数不超过 $n$ 时才算获胜；其次，可以达到的最大分数为 $k+\textit{maxPts}-1$，即在最后一次抽取数字之前的分数为 $k-1$，并且抽到了 $\textit{maxPts}$。

当 $0 \le x < k$ 时，如何计算 $\textit{dp}[x]$ 的值？注意到每次在范围 $[1, \textit{maxPts}]$ 内随机抽取一个整数，且每个整数被抽取到的概率相等，因此可以得到如下状态转移方程：

$$
\textit{dp}[x]=\frac{\sum_{i=1}^\textit{maxPts} \textit{dp}[x+i]}{\textit{maxPts}}
$$

根据状态转移方程，可以实现如下简单的动态规划：

###Java

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + maxPts];
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        for (int i = k - 1; i >= 0; i--) {
            for (int j = 1; j <= maxPts; j++) {
                dp[i] += dp[i + j] / maxPts;
            }
        }
        return dp[0];
    }
}

###C#

public class Solution {
    public double New21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + maxPts];
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        for (int i = k - 1; i >= 0; i--) {
            for (int j = 1; j <= maxPts; j++) {
                dp[i] += dp[i + j] / maxPts;
            }
        }
        return dp[0];
    }
}

###C++

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        vector<double> dp(k + maxPts);
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        for (int i = k - 1; i >= 0; i--) {
            for (int j = 1; j <= maxPts; j++) {
                dp[i] += dp[i + j] / maxPts;
            }
        }
        return dp[0];
    }
};

###Python

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0:
            return 1.0
        dp = [0.0] * (k + maxPts)
        for i in range(k, min(n, k + maxPts - 1) + 1):
            dp[i] = 1.0
        for i in range(k - 1, -1, -1):
            for j in range(1, maxPts + 1):
                dp[i] += dp[i + j] / maxPts
        return dp[0]

###golang

func new21Game(n int, k int, maxPts int) float64 {
    if k == 0 {
        return 1.0
    }
    dp := make([]float64, k + maxPts)
    for i := k; i <= n && i < k + maxPts; i++ {
        dp[i] = 1.0
    }
    for i := k - 1; i >= 0; i-- {
        for j := 1; j <= maxPts; j++ {
            dp[i] += dp[i + j] / float64(maxPts)
        }
    }
    return dp[0]
}

上述解法的时间复杂度是 $O(n+k \times \textit{maxPts})$，会超出时间限制，因此需要优化。

考虑对 $\textit{dp}$ 的相邻项计算差分，有如下结果：

$$
\textit{dp}[x] - \textit{dp}[x+1]=\frac{\textit{dp}[x+1] - \textit{dp}[x+\textit{maxPts}+1]}{\textit{maxPts}}
$$

其中 $0 \le x<k-1$。

因此可以得到新的状态转移方程：

$$
\textit{dp}[x]=\textit{dp}[x+1]-\frac{\textit{dp}[x+\textit{maxPts}+1]-\textit{dp}[x+1]}{\textit{maxPts}}
$$

其中 $0 \le x<k-1$。

注意到上述状态转移方程中 $x$ 的取值范围，当 $x=k-1$ 时不适用。因此对于 $\textit{dp}[k-1]$ 的值，需要通过

$$
\textit{dp}[k-1]=\frac{\sum_{i=0}^{\textit{maxPts}-1} \textit{dp}[k+i]}{\textit{maxPts}}
$$

计算得到。注意到只有当 $k \le x \le \min(n, k+\textit{maxPts}-1)$ 时才有 $\textit{dp}[x]=1$，因此

$$
\textit{dp}[k-1]=\frac{\min(n, k+\textit{maxPts}-1) - k + 1}{\textit{maxPts}} = \frac{\min(n-k+1,\textit{maxPts})}{\textit{maxPts}}
$$

可在 $O(1)$ 时间内计算得到 $\textit{dp}[k-1]$ 的值。

对于 $\textit{dp}[k-2]$ 到 $\textit{dp}[0]$ 的值，则可通过新的状态转移方程得到。

###Java

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + maxPts];
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        dp[k - 1] = 1.0 * Math.min(n - k + 1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        return dp[0];
    }
}

###C#

public class Solution {
    public double New21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + maxPts];
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        dp[k - 1] = 1.0 * Math.Min(n - k + 1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        return dp[0];
    }
}

###C++

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        vector<double> dp(k + maxPts);
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        dp[k - 1] = 1.0 * min(n - k + 1, maxPts) / maxPts;
        for (int i = k - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        return dp[0];
    }
};

###Python

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0:
            return 1.0
        dp = [0.0] * (k + maxPts)
        for i in range(k, min(n, k + maxPts - 1) + 1):
            dp[i] = 1.0
        dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts
        for i in range(k - 2, -1, -1):
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts
        return dp[0]

###golang

func new21Game(n int, k int, maxPts int) float64 {
    if k == 0 {
        return 1.0
    }
    dp := make([]float64, k + maxPts)
    for i := k; i <= n && i < k + maxPts; i++ {
        dp[i] = 1.0
    }

    dp[k - 1] = 1.0 * float64(min(n - k + 1, maxPts)) / float64(maxPts)
    for i := k - 2; i >= 0; i-- {
        dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / float64(maxPts) 
    }
    return dp[0]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

复杂度分析

时间复杂度：$O(\min(n, k+\textit{maxPts}))$。即需要计算的 $\textit{dp}$ 值的数量 $\min(n, k+\textit{maxPts}-1)$。
空间复杂度：$O(k+\textit{maxPts})$。创建了一个长度为 $k+\textit{maxPts}$ 的数组 $\textit{dp}$。

每日一题-6 和 9 组成的最大数字🟢

LeetCode 每日一题题解

2025年8月16日 00:00

给你一个仅由数字 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
解释：无需改变就已经是最大的数字了。

提示：

1 <= num <= 10^4
num 每一位上的数字都是 6 或者 9 。

LeetCode 每日一题题解
两种方法：用字符串/不用字符串（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2025年8月8日 13:13

两种方法：用字符串/不用字符串（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2025年8月8日 13:13

分析

要想把数字变大，只能把 $6$ 改成 $9$。

比如 $\textit{num}=9669$：

改高位的 $6$，得到 $9969$。
改低位的 $6$，得到 $9699$。
$9969 > 9699$。

改高位的 $6$ 比改低位的 $6$ 更好。由于至多改一次，所以改最高位的 $6$。若 $\textit{num}$ 无 $6$，则 $\textit{num}$ 不变。

方法一：用字符串

###py

class Solution:
    def maximum69Number(self, num: int) -> int:
        s = str(num).replace('6', '9', 1)  # 替换第一个 6
        return int(s)

###py

class Solution:
    def maximum69Number(self, num: int) -> int:
        s = str(num)
        i = s.find('6')
        if i < 0:
            return num
        return int(s[:i] + '9' + s[i + 1:])

###java

class Solution {
    public int maximum69Number(int num) {
        String s = String.valueOf(num).replaceFirst("6", "9"); // 替换第一个 6
        return Integer.parseInt(s);
    }
}

###java

class Solution {
    public int maximum69Number(int num) {
        String s = Integer.toString(num);
        int i = s.indexOf('6');
        if (i < 0) {
            return num;
        }
        s = s.substring(0, i) + "9" + s.substring(i + 1);
        return Integer.parseInt(s);
    }
}

###cpp

class Solution {
public:
    int maximum69Number(int num) {
        string s = to_string(num);
        int i = s.find('6');
        if (i == string::npos) {
            return num;
        }
        s[i] = '9';
        return stoi(s);
    }
};

###c

int maximum69Number(int num) {
    char s[6];
    sprintf(s, "%d", num);
    char* p = strchr(s, '6');
    if (p == NULL) {
        return num;
    }
    *p = '9';
    return atoi(s);
}

###go

func maximum69Number(num int) int {
s := strconv.Itoa(num)
s = strings.Replace(s, "6", "9", 1) // 替换第一个 6
ans, _ := strconv.Atoi(s)
return ans
}

###js

var maximum69Number = function(num) {
    const s = String(num).replace('6', '9'); // 替换第一个 6
    return parseInt(s);
};

###rust

impl Solution {
    pub fn maximum69_number(num: i32) -> i32 {
        num.to_string()
           .replacen("6", "9", 1) // 替换第一个 6
           .parse()
           .unwrap()
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(\log \textit{num})$。
空间复杂度：$\mathcal{O}(\log \textit{num})$。

方法二：不用字符串

可以不用转成字符串处理，而是不断取最低位（模 $10$），去掉最低位（除以 $10$），直到数字为 $0$。

例如 $\textit{num}=9669$：

初始化 $x=\textit{num}$。
通过 $x\bmod 10$ 取到个位数 $9$，然后把 $x$ 除以 $10$（下取整），得到 $x=966$。
再次 $x\bmod 10$ 取到十位数 $6$，然后把 $x$ 除以 $10$（下取整），得到 $x=96$。
再次 $x\bmod 10$ 取到百位数 $6$，然后把 $x$ 除以 $10$（下取整），得到 $x=9$。
最后 $x\bmod 10$ 取到千位数 $9$，然后把 $x$ 除以 $10$（下取整），得到 $x=0$。此时完成了遍历 $\textit{num}$ 的每个数位，退出循环。

在这个过程中，维护一个变量 $\textit{base}$，初始值为 $1$，在循环末尾把 $\textit{base}$ 乘以 $10$。每当我们遍历到一个等于 $6$ 的数位，就保存此刻的 $\textit{base}$，即更新 $\textit{maxBase} = \textit{base}$。其中 $\textit{maxBase}$ 初始值为 $0$。由于我们从低位往高位遍历，所以最终的 $\textit{maxBase}$ 就是最高位的 $6$ 对应的 $\textit{base}$。在上面的例子中，我们可以得到 $\textit{maxBase} = 100$。

最终答案为

$$
\textit{num} + \textit{maxBase}\cdot 3
$$

在上面的例子中，答案为 $9669 + 100\cdot 3 = 9969$。

注：如果 $\textit{num}$ 中没有 $6$，由于我们初始化 $\textit{maxBase}=0$，最终答案为 $\textit{num}$。

###py

class Solution:
    def maximum69Number(self, num: int) -> int:
        max_base = 0
        base = 1
        x = num
        while x:
            x, d = divmod(x, 10)
            if d == 6:
                max_base = base
            base *= 10
        return num + max_base * 3

###java

class Solution {
    public int maximum69Number(int num) {
        int maxBase = 0;
        int base = 1;
        for (int x = num; x > 0; x /= 10) {
            if (x % 10 == 6) {
                maxBase = base;
            }
            base *= 10;
        }
        return num + maxBase * 3;
    }
}

###cpp

class Solution {
public:
    int maximum69Number(int num) {
        int max_base = 0;
        int base = 1;
        for (int x = num; x > 0; x /= 10) {
            if (x % 10 == 6) {
                max_base = base;
            }
            base *= 10;
        }
        return num + max_base * 3;
    }
};

###c

int maximum69Number(int num) {
    int max_base = 0;
    int base = 1;
    for (int x = num; x > 0; x /= 10) {
        if (x % 10 == 6) {
            max_base = base;
        }
        base *= 10;
    }
    return num + max_base * 3;
}

###go

func maximum69Number(num int) int {
maxBase := 0
base := 1
for x := num; x > 0; x /= 10 {
if x%10 == 6 {
maxBase = base
}
base *= 10
}
return num + maxBase*3
}

###js

var maximum69Number = function(num) {
    let maxBase = 0;
    let base = 1;
    for (let x = num; x > 0; x = Math.floor(x / 10)) {
        if (x % 10 === 6) {
            maxBase = base;
        }
        base *= 10;
    }
    return num + maxBase * 3;
};

###rust

impl Solution {
    pub fn maximum69_number(num: i32) -> i32 {
        let mut max_base = 0;
        let mut base = 1;
        let mut x = num;
        while x > 0 {
            if x % 10 == 6 {
                max_base = base;
            }
            base *= 10;
            x /= 10;
        }
        num + max_base * 3
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(\log \textit{num})$。
空间复杂度：$\mathcal{O}(1)$。

思考题

改成求最小数字。
额外输入一个正整数 $k$，至多翻转 $k$ 个数，返回可以得到的最大数字。
给定正整数 $\textit{low}$ 和 $\textit{high}$，计算闭区间 $[\textit{low},\textit{high}]$ 中的所有整数 $x$ 的 $\texttt{maximum69Number}(x)$ 之和。

欢迎在评论区分享你的思路/代码。

专题训练

见下面贪心题单的「§3.1 字典序最小/最大」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

6 和 9 组成的最大数字

LeetCode 每日一题题解

作者 LeetCode-Solution

2020年2月18日 20:58

方法一：贪心 + 字符串

思路与算法

此题要求将一个由数字 $6$ 和 $9$ 构成的十进制数 $\textit{num}$ 进行至多一次 $6$ 和 $9$ 之间的翻转得到的最大数字。由十进制数的性质易知：贪心的选择数位最高的一个 $6$ 变成 $9$，得到的答案就是最大的。如果不存在这样的 $6$，则说明这个数字全由数字 $9$ 构成。根据题意，此时不对 $\textit{num}$ 做任何更改即为最优解。

对于算法实现，我们使用字符数组来处理 $\textit{num}$ 较为方便。首先将 $\textit{num}$ 转为字符数组，然后从左到遍历字符，按上述算法处理。最后将修改后的字符数组转回数字即为所求。

代码

###C++

class Solution {
public:
    int maximum69Number (int num) {
        string s = to_string(num);
        for (char &c : s) {
            if (c == '6') {
                c = '9';
                break;
            }
        }
        return stoi(s);
    }
};

###Java

public class Solution {
    public int maximum69Number (int num) {
        char[] chars = Integer.toString(num).toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '6') {
                chars[i] = '9';
                break;
            }
        }
        return Integer.parseInt(new String(chars));
    }
}

###C#

public class Solution {
    public int Maximum69Number (int num) {
        char[] chars = num.ToString().ToCharArray();
        for (int i = 0; i < chars.Length; i++) {
            if (chars[i] == '6') {
                chars[i] = '9';
                break;
            }
        }
        return int.Parse(new string(chars));
    }
}

###Go

func maximum69Number(num int) int {
    s := strconv.Itoa(num)
    chars := []byte(s)
    for i := 0; i < len(chars); i++ {
        if chars[i] == '6' {
            chars[i] = '9'
            break
        }
    }
    result, _ := strconv.Atoi(string(chars))
    return result
}

###Python

class Solution:
    def maximum69Number (self, num: int) -> int:
        s = list(str(num))
        for i in range(len(s)):
            if s[i] == '6':
                s[i] = '9'
                break
        return int(''.join(s))

###C

int maximum69Number(int num) {
    char s[20];
    sprintf(s, "%d", num);
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '6') {
            s[i] = '9';
            break;
        }
    }
    return atoi(s);
}

###Rust

impl Solution {
    pub fn maximum69_number (num: i32) -> i32 {
        let mut s = num.to_string().chars().collect::<Vec<char>>();
        for i in 0..s.len() {
            if s[i] == '6' {
                s[i] = '9';
                break;
            }
        }
        s.iter().collect::<String>().parse().unwrap()
    }
}

###JavaScript

var maximum69Number = function (num) {
    let charArray = [...num.toString()];

    for (let i = 0; i < charArray.length; i++) {
        if (charArray[i] === '6') {
            charArray[i] = '9';
            break;
        }
    }

    return Number(charArray.join(''));
};

###TypeScript

function maximum69Number(num: number): number {
    let charArray = [...num.toString()];

    for (let i = 0; i < charArray.length; i++) {
        if (charArray[i] === '6') {
            charArray[i] = '9';
            break;
        }
    }

    return Number(charArray.join(''));
};

复杂度分析

时间复杂度：$O(\log \textit{num})$。
空间复杂度：$O(\log \textit{num})$。

方法二：贪心 + 数学

思路与算法

思想同方法一，但是不依赖字符串操作，而是通过纯数学的方式找到最高位的 $6$ 并更改为 $9$。

首先初始化一个基数 $\textit{digitBase} = 10^{\lfloor \log_{10}(\textit{num}) \rfloor}$，这个基数代表了 $\textit{num}$ 的最高位。然后从高位向低位遍历，每次将 $\textit{digitBase}$ 除以 $10$。在每一次循环中，通过 $\lfloor \textit{num} \div \textit{digitBase} \rfloor \bmod 10$ 来获取当前基数 $\textit{digitBase}$ 所在的十进制位上的数字。一旦这个数字等于 $6$，我们就可以确定这就是需要修改的最高位的 $6$。此时，我们将 $\textit{num}$ 加上 $3 \times \textit{digitBase}$，即可将该位的 $6$ 修改为 $9$，结果即为所求。

代码

###C++

class Solution {
public:
    int maximum69Number (int num) {
        int digitBase = pow(10, (int)log10(num));
        while (digitBase > 0) {
            if ((num / digitBase) % 10 == 6) {
                num += 3 * digitBase;
                return num;
            }
            digitBase /= 10;
        }
        
        return num;
    }
};

###Java

public class Solution {
    public int maximum69Number (int num) {
        int digitBase = (int)Math.pow(10, (int)Math.log10(num));
        while (digitBase > 0) {
            if ((num / digitBase) % 10 == 6) {
                num += 3 * digitBase;
                return num;
            }
            digitBase /= 10;
        }
        
        return num;
    }
}

###C#

public class Solution {
    public int Maximum69Number (int num) {
        int digitBase = (int)Math.Pow(10, (int)Math.Log10(num));
        while (digitBase > 0) {
            if ((num / digitBase) % 10 == 6) {
                num += 3 * digitBase;
                return num;
            }
            digitBase /= 10;
        }
        
        return num;
    }
}

###Go

func maximum69Number(num int) int {
    digitBase := int(math.Pow10(int(math.Log10(float64(num)))))
    for digitBase > 0 {
        if (num / digitBase) % 10 == 6 {
            num += 3 * digitBase
            return num
        }
        digitBase /= 10
    }
    
    return num
}

###Python

class Solution:
    def maximum69Number (self, num: int) -> int:
        digit_base = 10 ** int(math.log10(num)) if num != 0 else 0
        while digit_base > 0:
            if (num // digit_base) % 10 == 6:
                num += 3 * digit_base
                return num
            digit_base = digit_base // 10
        
        return num

###C

int maximum69Number(int num) {
    int digitBase = pow(10, (int)log10(num));
    while (digitBase > 0) {
        if ((num / digitBase) % 10 == 6) {
            num += 3 * digitBase;
            return num;
        }
        digitBase /= 10;
    }
    
    return num;
}

###Rust

impl Solution {
    pub fn maximum69_number (num: i32) -> i32 {
        let mut digit_base = 10i32.pow((num as f32).log10() as u32);
        let mut num = num;
        while digit_base > 0 {
            if (num / digit_base) % 10 == 6 {
                num += 3 * digit_base;
                return num;
            }
            digit_base /= 10;
        }
        
        num
    }
}

###JavaScript

var maximum69Number = function (num) {
    let digitBase = Math.pow(10, Math.trunc(Math.log10(num)));

    while (digitBase > 0) {
        if (Math.trunc(num / digitBase) % 10 === 6) {
            num += 3 * digitBase;
            return num;
        }
        digitBase = Math.trunc(digitBase / 10);
    }

    return num;
};

###TypeScript

function maximum69Number(num: number): number {
    let digitBase = Math.pow(10, Math.trunc(Math.log10(num)));

    while (digitBase > 0) {
        if (Math.trunc(num / digitBase) % 10 === 6) {
            num += 3 * digitBase;
            return num;
        }
        digitBase = Math.trunc(digitBase / 10);
    }

    return num;
};

复杂度分析

时间复杂度：$O(\log \textit{num})$。
空间复杂度：$O(1)$。

C 不转换字符串

LeetCode 每日一题题解

作者 logan-31

2020年1月23日 12:38

解题思路

循环看看哪个6最靠前，然后加上3的x次幂即可
（4ms, 61.64%; 6.8MB, 100.00%）

代码

###c

#include <Math.h>
int maximum69Number (int num){
    int count = 0, th = 0;          // count 记录除了多少次，th记录最大的6在第几位
    int re = num;
    while(re){
        count++;
        if(re%10==6)
           th = count;
        re /= 10;
    }
    return num+3*pow(10,th-1);
}

每日一题-判断一个数字是否可以表示成三的幂的和🟡

LeetCode 每日一题题解

2025年8月14日 00:00

给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 y == 3^x ，我们称这个整数 y 是三的幂。

示例 1：

输入：n = 12
输出：true
解释：12 = 3¹ + 3²

示例 2：

输入：n = 91
输出：true
解释：91 = 3⁰ + 3² + 3⁴

示例 3：

输入：n = 21
输出：false

提示：

1 <= n <= 10⁷

【爪哇缪斯】图解LeetCode

LeetCode 每日一题题解

作者 muse-77

2022年12月9日 09:01

解题思路

根据题目表述，我们要判断n是否满足三的幂之和，其实关于这道题，如果我们将三的幂之和改变为二的幂之和，就清晰多了。因为我们常用的二进制转成十进制，就是采用二的幂之和来计算获得了。那么，同理，我们采用三进制计算的方式，就可以获得这道题的答案了。

也就是说，我们通过对n进行除3取余操作，如果获得0或1，则表示满足三进制，依次类推，直到除完为止。如果在除3取余过程中，不满足0或者1，则直接返回false。具体逻辑，请参照下图所示：

代码实现

###java

class Solution {
    public boolean checkPowersOfThree(int n) {
        while (n != 0) {
            if (n % 3 == 0 || n % 3 == 1) n = n / 3; // 满足三进制
            else return false; // 不满足三进制，返回false
        }
        return true;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞 & 分享。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」

三进制

LeetCode 每日一题题解

作者 himymBen

2022年12月9日 07:31

Problem: 1780. 判断一个数字是否可以表示成三的幂的和

[TOC]

思路

一个数可以表示为不同的3的幂次的和，那么它的三进制每一位只能是1或0

解题方法

按三进制转换，确保三进制任意位中没有2

复杂度

时间复杂度:

$O(log_{3}n)$

空间复杂度:

$O(1)$

Code

###Python3


class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        while n:
            if n % 3 == 2:
                return False
            n //= 3
        return True

###Go

func checkPowersOfThree(n int) bool {
    for ; n > 0; n /= 3 {
        if n % 3 == 2 {
            return false
        }
    }
    return true
}

判断一个数字是否可以表示成三的幂的和

LeetCode 每日一题题解

作者 LeetCode-Solution

2022年12月8日 09:59

方法一：进制转换

思路与算法

我们可以将 $n$ 转换成 $3$ 进制。如果 $n$ 的 $3$ 进制表示中每一位均不为 $2$，那么答案为 $\text{True}$，否则为 $\text{False}$。

例如当 $n=12$ 时，$12 = (110)_3$，满足要求；当 $n=21$ 时，$21 = (210)_3$，不满足要求。

代码

###C++

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while (n) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
};

###Java

class Solution {
    public boolean checkPowersOfThree(int n) {
        while (n != 0) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
}

###C#

public class Solution {
    public bool CheckPowersOfThree(int n) {
        while (n != 0) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
}

###Python

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        while n > 0:
            if n % 3 == 2:
                return False
            n //= 3
        return True

###C

bool checkPowersOfThree(int n) {
    while (n) {
        if (n % 3 == 2) {
            return false;
        }
        n /= 3;
    }
    return true;
}

###JavaScript

var checkPowersOfThree = function(n) {
    while (n !== 0) {
        if (n % 3 === 2) {
            return false;
        }
        n = Math.floor(n / 3);
    }
    return true;
};

###go

func checkPowersOfThree(n int) bool {
    for ; n > 0; n /= 3 {
        if n%3 == 2 {
            return false
        }
    }
    return true
}

复杂度分析

时间复杂度：$O(\log n)$，即为进制转换需要的时间。
空间复杂度：$O(1)$。

每日一题-3 的幂🟢

LeetCode 每日一题题解

2025年8月13日 00:00

给定一个整数，写一个函数来判断它是否是 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

提示：

-2³¹ <= n <= 2³¹ - 1

进阶：你能不使用循环或者递归来完成本题吗？

LeetCode 每日一题题解
O(1) 数学做法，一行搞定（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2024年11月2日 14:20

O(1) 数学做法，一行搞定（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2024年11月2日 14:20

$3$ 的幂一定大于 $0$。如果 $n\le 0$，那么 $n$ 不是 $3$ 的幂。下文假定 $n>0$。

在本题的数据范围下，最大的 $3$ 的幂是 $3^{19} = 1162261467$。

怎么算的？比如可以写个循环，找最大的满足 $3^i\le 2^{31}-1$ 的整数 $i$。

如果 $n$ 是 $3$ 的幂。由于任何 $3$ 的幂都是 $3^{19}$ 的因子，所以 $3^{19}\bmod n = 0$。或者说 $n$ 的某个倍数等于 $3^{19}$。
如果 $n$ 不是 $3$ 的幂。那么 $n$ 必然有不等于 $3$ 的质因子，所以 $n$ 的倍数不可能等于 $3^{19}$ 这个只含质因子 $3$ 的数，所以 $3^{19}\bmod n \ne 0$。

因此，在本题数据范围下，当且仅当 $n>0$ 且 $3^{19}\bmod n = 0$ 时，$n$ 是 $3$ 的幂。

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0

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

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

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

func isPowerOfThree(n int) bool {
    return n > 0 && 1162261467%n == 0
}

var isPowerOfThree = function(n) {
    return n > 0 && 1162261467 % n === 0;
};

impl Solution {
    pub fn is_power_of_three(n: i32) -> bool {
        n > 0 && 1162261467 % n == 0
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(1)$。
空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

普通视图

思路

挑出的每一对数，我们…

剪枝小技巧

代码

执行情况

感谢阅读，文字经过反复修改打磨，希望你能感受到这份真诚。欢迎提出建议。

方法一：回溯

寻找子问题

状态定义与状态转移方程

答疑

复杂度分析

专题训练

分类题单

解题思路

填格子游戏开始

代码

怎样推导出官方题解中的状态转移方程

延申

📺视频题解

📖文字题解

方法一：动态规划

分析

方法一：用字符串

复杂度分析

方法二：不用字符串

复杂度分析

思考题

专题训练

分类题单

方法一：贪心 + 字符串

方法二：贪心 + 数学

解题思路

代码

解题思路

代码实现

思路

解题方法

复杂度

Code

方法一：进制转换

复杂度分析

分类题单