阅读视图

发现新文章,点击刷新页面。

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

给你一个整数 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

 

提示:

  • 1 <= n <= 107

【爪哇缪斯】图解LeetCode

解题思路

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

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

image.png

代码实现

###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;
    }
}

image.png

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

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

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

三进制

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
}

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

方法一:进制转换

思路与算法

我们可以将 $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 的幂🟢

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

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

 

示例 1:

输入:n = 27
输出:true

示例 2:

输入:n = 0
输出:false

示例 3:

输入:n = 9
输出:true

示例 4:

输入:n = 45
输出:false

 

提示:

  • -231 <= n <= 231 - 1

 

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

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

$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)$。

分类题单

如何科学刷题?

  1. 滑动窗口与双指针(定长/不定长/单序列/双序列/三指针/分组循环)
  2. 二分算法(二分答案/最小化最大值/最大化最小值/第K小)
  3. 单调栈(基础/矩形面积/贡献法/最小字典序)
  4. 网格图(DFS/BFS/综合应用)
  5. 位运算(基础/性质/拆位/试填/恒等式/思维)
  6. 图论算法(DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流)
  7. 动态规划(入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望)
  8. 常用数据结构(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)
  9. 数学算法(数论/组合/概率期望/博弈/计算几何/随机算法)
  10. 贪心与思维(基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造)
  11. 链表、二叉树与回溯(前后指针/快慢指针/DFS/BFS/直径/LCA/一般树)
  12. 字符串(KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机)

我的题解精选(已分类)

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

【宫水三叶】一题三解 :「数学」&「倍数/约数」&「打表」

数学

一个不能再朴素的做法是将 $n$ 对 $3$ 进行试除,直到 $n$ 不再与 $3$ 呈倍数关系,最后判断 $n$ 是否为 $3^0 = 1$ 即可。

代码:

###Java

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n % 3 == 0) n /= 3;
        return n == 1;
    }
}
  • 时间复杂度:$O(\log_{3}n)$
  • 空间复杂度:$O(1)$

倍数 & 约数

题目要求不能使用循环或递归来做,而传参 $n$ 的数据类型为 int,这引导我们首先分析出 int 范围内的最大 $3$ 次幂是多少,约为 $3^{19} = 1162261467$。

如果 $n$ 为 $3$ 的幂的话,那么必然满足 $n * 3^k = 1162261467$,即 $n$ 与 $1162261467$ 存在倍数关系。

因此,我们只需要判断 $n$ 是否为 $1162261467$ 的约数即可。

注意:这并不是快速判断 $x$ 的幂的通用做法,当且仅当 $x$ 为质数可用。

代码:

###Java

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}
  • 时间复杂度:$O(1)$
  • 空间复杂度:$O(1)$

打表

另外一个更容易想到的「不使用循环/递归」的做法是进行打表预处理。

使用 static 代码块,预处理出不超过 int 数据范围的所有 $3$ 的幂,这样我们在跑测试样例时,就不需要使用「循环/递归」来实现逻辑,可直接 $O(1)$ 查表返回。

代码:

###Java

class Solution {
    static Set<Integer> set = new HashSet<>();
    static {
        int cur = 1;
        set.add(cur);
        while (cur <= Integer.MAX_VALUE / 3) {
            cur *= 3;
            set.add(cur);
        }
    }
    public boolean isPowerOfThree(int n) {
        return n > 0 && set.contains(n);
    }
}
  • 时间复杂度:将打表逻辑交给 $OJ$ 执行的话,复杂度为 $O(\log_3{C})$,$C$ 固定为 $2147483647$;将打表逻辑放到本地执行,复杂度为 $O(1)$
  • 空间复杂度:$O(\log_3{n})$

其他「$x$ 的幂」问题

题目简单?不如来看「矩阵快速幂」三部曲 🍭🍭🍭:

题目 题解 难度 推荐指数
1137. 第 N 个泰波那契数 LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
剑指 Offer 10- I. 斐波那契数列 LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
552. 学生出勤记录 II LeetCode 题解链接 困难 🤩🤩🤩🤩

或是加练如下的「$x$ 的幂」问题 🍭🍭🍭:

题目 题解 难度 推荐指数
231. 2 的幂 LeetCode 题解链接 简单 🤩🤩🤩🤩
342. 4的幂 LeetCode 题解链接 简单 🤩🤩🤩🤩

最后

如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我(公主号后台回复「送书」即可参与长期看题解学算法送实体书活动)或 加入「组队打卡」小群 ,提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南,欢迎 star 哦 ~

3的幂

方法一:试除法

思路与算法

我们不断地将 $n$ 除以 $3$,直到 $n=1$。如果此过程中 $n$ 无法被 $3$ 整除,就说明 $n$ 不是 $3$ 的幂。

本题中的 $n$ 可以为负数或 $0$,可以直接提前判断该情况并返回 $\text{False}$,也可以进行试除,因为负数或 $0$ 也无法通过多次除以 $3$ 得到 $1$。

代码

###C++

class Solution {
public:
    bool isPowerOfThree(int n) {
        while (n && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
};

###Java

class Solution {
    public boolean isPowerOfThree(int n) {
        while (n != 0 && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

###C#

public class Solution {
    public bool IsPowerOfThree(int n) {
        while (n != 0 && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

###Python

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while n and n % 3 == 0:
            n //= 3
        return n == 1

###JavaScript

var isPowerOfThree = function(n) {
    while (n !== 0 && n % 3 === 0) {
        n = Math.floor(n / 3);
    }
    return n === 1;
};

###go

func isPowerOfThree(n int) bool {
    for n > 0 && n%3 == 0 {
        n /= 3
    }
    return n == 1
}

复杂度分析

  • 时间复杂度:$O(\log n)$。当 $n$ 是 $3$ 的幂时,需要除以 $3$ 的次数为 $\log_3 n = O(\log n)$;当 $n$ 不是 $3$ 的幂时,需要除以 $3$ 的次数小于该值。

  • 空间复杂度:$O(1)$。

方法二:判断是否为最大 $3$ 的幂的约数

思路与算法

我们还可以使用一种较为取巧的做法。

在题目给定的 $32$ 位有符号整数的范围内,最大的 $3$ 的幂为 $3^{19} = 1162261467$。我们只需要判断 $n$ 是否是 $3^{19}$ 的约数即可。

与方法一不同的是,这里需要特殊判断 $n$ 是负数或 $0$ 的情况。

代码

###C++

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

###Java

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

###C#

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

###Python

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

###JavaScript

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

###go

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

复杂度分析

  • 时间复杂度:$O(1)$。

  • 空间复杂度:$O(1)$。

每日一题-将一个数字表示成幂的和的方案数🟡

给你两个  整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说,你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目,满足 n = n1x + n2x + ... + nkx 。

由于答案可能非常大,请你将它对 109 + 7 取余后返回。

比方说,n = 160 且 x = 3 ,一个表示 n 的方法是 n = 23 + 33 + 53 

 

示例 1:

输入:n = 10, x = 2
输出:1
解释:我们可以将 n 表示为:n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。

示例 2:

输入:n = 4, x = 1
输出:2
解释:我们可以将 n 按以下方案表示:
- n = 41 = 4 。
- n = 31 + 11 = 4 。

 

提示:

  • 1 <= n <= 300
  • 1 <= x <= 5

2787. 将一个数字表示成幂的和的方案数

解法

思路和算法

计算 $\textit{maxNum} = \lfloor \sqrt[x]{n} \rfloor$,则当 $n$ 表示成各不相同的正整数的 $x$ 次幂之和时,任何一个作为底数的正整数都不能超过 $\textit{maxNum}$。问题等价于计算从 $1^x$ 到 $\textit{maxNum}^x$ 的 $\textit{maxNum}$ 个正整数的 $x$ 次幂中选取一个或多个数字满足选取的数字之和等于 $n$ 的方案数。

该问题是 0-1 背包问题的变种,和传统 0-1 背包问题的区别在于,这道题要求选取的数字之和恰好等于 $n$。对于每个数字,选取的数字之和取决于之前选取的数字,因此可以使用动态规划计算选取的数字之和等于 $n$ 的方案数。

创建 $(\textit{maxNum} + 1) \times (n + 1)$ 的二维数组 $\textit{dp}$,其中 $\textit{dp}[i][j]$ 表示在前 $i$ 个数字中选取数字使数字之和等于 $j$ 的方案数。

当 $i = 0$ 时,没有任何数字,数字之和一定是 $0$,因此动态规划的边界情况是:当 $j = 0$ 时 $\textit{dp}[0][j] = 1$,当 $j > 0$ 时 $\textit{dp}[0][j] = 0$。

当 $i > 0$ 时,当前数字是 $i^x$,只有当 $j \ge i^x$ 时才能选取当前数字。分别考虑 $j < i^x$ 和 $j \ge i^x$ 的情况。

  • 如果 $j < i^x$,则不能选取当前数字,在前 $i$ 个数字中选取数字使数字之和等于 $j$ 等价于在前 $i - 1$ 个数字中选取数字使数字之和等于 $j$,因此方案数为 $\textit{dp}[i - 1][j]$。

  • 如果 $j \ge i^x$,则可以不选取或选取当前数字,根据两种情况计算方案数。

    • 如果不选取当前数字,则需要在前 $i - 1$ 个数字中选取数字使数字之和等于 $j$,方案数为 $\textit{dp}[i - 1][j]$。

    • 如果选取当前数字,则需要在前 $i - 1$ 个数字中选取数字使数字之和等于 $j - i^x$,加上选取的当前数字之后数字之和等于 $j$,因此方案数为 $\textit{dp}[i - 1][j - i^x]$。

因此动态规划的状态转移方程如下。

  • 如果 $j < i^x$,则 $\textit{dp}[i][j] = \textit{dp}[i - 1][j]$。

  • 如果 $j \ge i^x$,则 $\textit{dp}[i][j] = \textit{dp}[i - 1][j] + \textit{dp}[i - 1][j - i^x]$。

根据动态规划的状态转移方程,计算 $\textit{dp}[i][j]$ 的顺序为从小到大遍历每个 $i$。计算得到 $\textit{dp}[\textit{maxNum}][n]$ 即为将 $n$ 表示成各不相同的正整数的 $x$ 次幂之和的方案数。

上述做法的时间复杂度和空间复杂度都是 $O(\sqrt[x]{n} \times n)$。

实现方面可以优化空间,做法如下。

  1. 由于 $\textit{dp}[i][]$ 只取决于 $\textit{dp}[i - 1][]$,和更早的状态无关,因此可以使用滚动数组的思想,只保留前一个 $i$ 处的状态,将空间复杂度降到 $O(n)$。

  2. 优化空间时,如果从小到大遍历每个 $j$ 则对于每个遍历到的 $i$ 都需要新建一个临时数组。可以进一步优化空间,从大到小遍历每个 $j$,则不需要新建临时数组。

为了避免浮点数误差,计算 $\textit{maxNum}$ 时可以取 $\textit{maxNum} = \lfloor \sqrt[x]{n + 0.5} \rfloor$。

代码

下面的代码为不优化空间的实现。

###Java

class Solution {
    static final int MODULO = 1000000007;

    public int numberOfWays(int n, int x) {
        int maxNum = (int) Math.pow(n + 0.5, 1.0 / x);
        int[][] dp = new int[maxNum + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= maxNum; i++) {
            int power = (int) Math.pow(i, x);
            for (int j = 0; j <= n; j++) {
                if (j < power) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - power]) % MODULO;
                }
            }
        }
        return dp[maxNum][n];
    }
}

###C#

public class Solution {
    const int MODULO = 1000000007;

    public int NumberOfWays(int n, int x) {
        int maxNum = (int) Math.Pow(n + 0.5, 1.0 / x);
        int[][] dp = new int[maxNum + 1][];
        for (int i = 0; i <= maxNum; i++) {
            dp[i] = new int[n + 1];
        }
        dp[0][0] = 1;
        for (int i = 1; i <= maxNum; i++) {
            int power = (int) Math.Pow(i, x);
            for (int j = 0; j <= n; j++) {
                if (j < power) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - power]) % MODULO;
                }
            }
        }
        return dp[maxNum][n];
    }
}

下面的代码为优化空间的实现。

###Java

class Solution {
    static final int MODULO = 1000000007;

    public int numberOfWays(int n, int x) {
        int maxNum = (int) Math.pow(n + 0.5, 1.0 / x);
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= maxNum; i++) {
            int power = (int) Math.pow(i, x);
            for (int j = n; j >= power; j--) {
                dp[j] = (dp[j] + dp[j - power]) % MODULO;
            }
        }
        return dp[n];
    }
}

###C#

public class Solution {
    const int MODULO = 1000000007;

    public int NumberOfWays(int n, int x) {
        int maxNum = (int) Math.Pow(n + 0.5, 1.0 / x);
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= maxNum; i++) {
            int power = (int) Math.Pow(i, x);
            for (int j = n; j >= power; j--) {
                dp[j] = (dp[j] + dp[j - power]) % MODULO;
            }
        }
        return dp[n];
    }
}

复杂度分析

代码中使用了 $\texttt{Math.pow}$ 方法,该方法调用了本地方法 $\texttt{StrictMath.pow}$,因此其时间与空间复杂度取决于本地方法的实现,此处的复杂度分析将该方法的时间复杂度和空间复杂度视为 $O(1)$。

  • 时间复杂度:$O(\sqrt[x]{n} \times n)$,其中 $n$ 和 $x$ 是给定的正整数。状态数是 $O(\sqrt[x]{n} \times n)$,每个状态的计算时间是 $O(1)$,因此时间复杂度是 $O(\sqrt[x]{n} \times n)$。

  • 空间复杂度:$O(\sqrt[x]{n} \times n)$ 或 $O(n)$,其中 $n$ 和 $x$ 是给定的正整数。空间复杂度取决于实现方式,不优化空间的实现需要创建大小为 $(\lfloor \sqrt[x]{n} \rfloor + 1) \times (n + 1)$ 的二维数组因此空间复杂度是 $O(\sqrt[x]{n} \times n)$,优化空间的实现需要创建长度为 $n + 1$ 的一维数组因此空间复杂度是 $O(n)$。

0-1 背包模板题(Python/Java/C++/C/Go/JS/Rust)

把 $n$ 看成背包容量,$1^x,2^x,3^x,\dots$ 看成物品,本题是恰好装满型 0-1 背包的方案数,做法同 494. 目标和,原理讲解见【基础算法精讲 18】,包含倒序循环的讲解。

代码实现时,由于最坏情况 $n=300$,$x=1$ 的答案没有超过 $64$ 位整数的最大值,可以在计算结束后再取模。

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        f = [1] + [0] * n
        for i in range(1, n + 1):
            v = i ** x
            if v > n:
                break
            for s in range(n, v - 1, -1):
                f[s] += f[s - v]
        return f[n] % 1_000_000_007
# 预处理所有答案
MX_N = 300
MX_X = 5
f = [[1] + [0] * MX_N for _ in range(MX_X + 1)]
for x in range(1, MX_X + 1):
    for i in count(1):
        v = i ** x
        if v > MX_N:
            break
        for s in range(MX_N, v - 1, -1):
            f[x][s] += f[x][s - v]

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        return f[x][n] % 1_000_000_007
class Solution {
    int numberOfWays(int n, int x) {
        long[] f = new long[n + 1];
        f[0] = 1;
        // 本题数据范围小,Math.pow 的计算结果一定准确
        for (int i = 1; Math.pow(i, x) <= n; i++) {
            int v = (int) Math.pow(i, x);
            for (int s = n; s >= v; s--) {
                f[s] += f[s - v];
            }
        }
        return (int) (f[n] % 1_000_000_007);
    }
}
class Solution {
public:
    int numberOfWays(int n, int x) {
        vector<long long> f(n + 1);
        f[0] = 1;
        // 本题数据范围小,pow 的计算结果一定准确
        for (int i = 1; pow(i, x) <= n; i++) {
            int v = pow(i, x);
            for (int s = n; s >= v; s--) {
                f[s] += f[s - v];
            }
        }
        return f[n] % 1'000'000'007;
    }
};
#define MOD 1000000007

int numberOfWays(int n, int x) {
    long long* f = calloc(n + 1, sizeof(long long));
    f[0] = 1;

    // 本题数据范围小,pow 的计算结果一定准确
    for (int i = 1; pow(i, x) <= n; i++) {
        int v = pow(i, x);
        for (int s = n; s >= v; s--) {
            f[s] += f[s - v];
        }
    }

    int ans = f[n] % MOD;
    free(f);
    return ans;
}
func numberOfWays(n, x int) int {
f := make([]int, n+1)
f[0] = 1
for i := 1; pow(i, x) <= n; i++ {
v := pow(i, x)
for s := n; s >= v; s-- {
f[s] += f[s-v]
}
}
return f[n] % 1_000_000_007
}

// 本题数据范围小,math.Pow 的计算结果一定准确
func pow(i, x int) int {
return int(math.Pow(float64(i), float64(x)))
}
var numberOfWays = function(n, x) {
    const f = new Array(n + 1).fill(0);
    f[0] = 1;
    // 本题数据范围小,pow 的计算结果一定准确
    for (let i = 1; Math.pow(i, x) <= n; i++) {
        const v = Math.pow(i, x);
        for (let s = n; s >= v; s--) {
            f[s] += f[s - v];
        }
    }
    return f[n] % 1_000_000_007;
};
impl Solution {
    pub fn number_of_ways(n: i32, x: i32) -> i32 {
        let n = n as usize;
        let mut f = vec![0i64; n + 1];
        f[0] = 1;
        for i in 1usize.. {
            let v = i.pow(x as u32);
            if v > n {
                break;
            }
            for s in (v..=n).rev() {
                f[s] += f[s - v];
            }
        }
        (f[n] % 1_000_000_007) as _
    }
}

复杂度分析

  • 时间复杂度:$\mathcal{O}(n\sqrt[x]n)$。外层循环的循环次数为 $\mathcal{O}(\sqrt[x]n)$。
  • 空间复杂度:$\mathcal{O}(n)$。

:也可以用快速幂计算 $\texttt{pow}$,原理见【图解】一张图秒懂快速幂

专题训练

见下面动态规划题单的「§3.1 0-1 背包」。

分类题单

如何科学刷题?

  1. 滑动窗口与双指针(定长/不定长/单序列/双序列/三指针/分组循环)
  2. 二分算法(二分答案/最小化最大值/最大化最小值/第K小)
  3. 单调栈(基础/矩形面积/贡献法/最小字典序)
  4. 网格图(DFS/BFS/综合应用)
  5. 位运算(基础/性质/拆位/试填/恒等式/思维)
  6. 图论算法(DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流)
  7. 动态规划(入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望)
  8. 常用数据结构(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)
  9. 数学算法(数论/组合/概率期望/博弈/计算几何/随机算法)
  10. 贪心与思维(基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造)
  11. 链表、二叉树与回溯(前后指针/快慢指针/DFS/BFS/直径/LCA/一般树)
  12. 字符串(KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机)

我的题解精选(已分类)

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

三种方法解决:记忆化搜索,2维DP(背包),1维DP(背包)

请见下面代码中的注释:

###python

class Solution:
    # 方法一:记忆化搜索
    def numberOfWays(self, n: int, x: int) -> int:
        mod = 10 ** 9 + 7
        @cache
        # 函数dfs(num, target)的解释:
        # num:当前遍历到的数
        # target:期望组合成的数
        # dfs()的意义:找到以整数num开始的,能形成幂和的方案数
        # 以例题1:"输入:n = 10, x = 2" 为例,可以由下面步骤得来:
        # 1. 从整数1,2,3中依次寻找, 从1开始
        # 2-1. 如果到达1,如果选择了1,那方案数为dfs(0, 10 - 1 ** 2),即dfs(0, 9)
        # 2-2. 如果到达1,但是没有选择1,那方案数为dfs(0, 10),即到达0,目的仍然为10的方案数
        # 3. 所以到达1的方案数dfs(1, 10) = dfs(0, 10 - 1 ** 2) + dfs(0, 10)
        def dfs(num, target):
            # 如果target为0,说明已经组合成功,则返回1(种情况)
            if target == 0:
                return 1
            # 如果当前数的x幂已经超过target了,说明后面已经没必要进行下去(因为是正整数)
            if num ** x > target:
                return 0
            # 选择了当前的整数的方案数
            res = dfs(num+1, target- num ** x) % mod
            # 加上不选择当前的整数的方案数
            res = (res + dfs(num+1, target)) % mod
            return res
        # dfs(1, n)意思是从整数1开始找,目标是n的方案数
        return dfs(1, n)

    # 方法二:二维DP/背包问题,时间O(nlogn),空间O(nlogn)
    def numberOfWays(self, n: int, x: int) -> int:
        mod = 10 ** 9 + 7
        # 此处用n+1的原因是防止精度丢失,比如n=64, x = 3,math.pow(64, 1/3) = 2.999999,会导致max_num = 2
        max_num = int(math.pow(n+1, 1/x))
        # DP[num][target]意义为:方案选到整数num时,能够组成幂和为target的方案数
        dp = [[0] * (n+1) for _ in range(max_num+1)]
        # 初始化:方案选为0时,幂和为0的方案数为1
        dp[0][0] = 1
        for num in range(1, max_num+1):
            for target in range(n+1):
                # 不选num数时
                dp[num][target] = dp[num-1][target]
                # 选num数时,需要保证target-num ** x >=0,能才选
                if target >= num ** x:
                    dp[num][target] = (dp[num][target] + dp[num-1][target-num ** x]) % mod
        return dp[max_num][n]


    # 方法三:优化后的一维DP/背包问题, 时间O(nlogn),空间O(logn)
    def numberOfWays(self, n: int, x: int) -> int:
        mod = 10 ** 9 + 7
        max_num = int(math.pow(n+1, 1/x))
        dp = [0] * (n+1)
        dp[0] = 1
        for num in range(1, max_num+1):
            # 此处为倒序
            # 以上述二维dp的转移方程为例:dp[num][target] = dp[num-1][target] + dp[num][target-num**x]
            # 可以知道当前的状态dp[num][target]只与上一行有关,而且只与上一行的并且列数小于等于当前列的状态有关
            # 请大家画个矩阵出来,就可以容易的看出,只有使用倒序,在更新最新一行时,不会覆盖对后面有意义的上一行的数据
            for target in range(n, -1, -1):
                if target >= num ** x:
                    dp[target] = (dp[target] + dp[target - num ** x] ) % mod
        return dp[n]
❌