【LetMeFly】1780.判断一个数字是否可以表示成三的幂的和 力扣题目链接:https://leetcode.cn/problems/check-if-number-is-a-sum-of-powers-of-three/
给你一个整数 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
提示:
也可直接看效率更高的方法二
方法一:二进制枚举 题目分析 $3^{14}=4782969<10^7, 3^{15}=14348907>10^7$
因此,想要数个不同的$3$的$n$次幂组成$n$($n\leq 10^7$),那么最多使用$3^0~3^{14}$这$15$个数
每个数有“选”与“不选”两种选择,因此最多有$2^{15}=32768$种方案,可以枚举解决。
解题思路 那么,我们直接开辟一个数组,把所有的小于等于$n$的“3的幂”放入数组
1 2 3 4 vector<int > three (1 , 1 ) ; while (three.back () < n) { three.push_back (three.back () * 3 ); }
接下来,用一个整数$state$从$0$到$2^{len(three)}$枚举,$state$的第$i$位为$0$则代表使用$three$数组中的第$i$个数,否则代表不使用。
每个$state$代表一种方案,计算所有的方案中,是否有和为$n$的
1 2 3 4 5 6 7 8 9 10 11 12 int num = three.size (), to = 1 << num;for (int state = 0 ; state < to; state++) { int s = 0 ; for (int j = 0 ; j < num; j++) { if (state & (1 << j)) { s += three[j]; } } if (s == n) return true ; }return false ;
复杂度分析
时间复杂度$O(2^{\log_3 n})$
空间复杂度$O(\log_3 n)$
AC代码 C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : bool checkPowersOfThree (int n) { vector<int > three (1 , 1 ) ; while (three.back () < n) { three.push_back (three.back () * 3 ); } int num = three.size (), to = 1 << num; for (int state = 0 ; state < to; state++) { int s = 0 ; for (int j = 0 ; j < num; j++) { if (state & (1 << j)) { s += three[j]; } } if (s == n) return true ; } return false ; } };
方法二:进制转换 我们只需要将$n$转化为三进制,然后判断$n$在三进制下是否有$2$
例如$10=(101)_3$,那就说明$10=3^0+3^2$;$15=(120)_3$,那就说明$15=3^2+2\times3^1$,需要两个$3^1$
时间复杂度$O(\log_3 n)$
空间复杂度$O(1)$
AC代码 C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : bool checkPowersOfThree (int n) { while (n) { if (n % 3 == 2 ) { return false ; } n /= 3 ; } return true ; } };
Python 1 2 3 4 5 6 7 8 9 10 11 12 13 ''' Author: LetMeFly Date: 2025-08-14 10:28:59 LastEditors: LetMeFly.xyz LastEditTime: 2025-08-14 18:43:00 ''' class Solution : def checkPowersOfThree (self, n: int ) -> bool : while n: if n % 3 == 2 : return False n //= 3 return True
Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public boolean checkPowersOfThree (int n) { while (n > 0 ) { if (n % 3 == 2 ) { return false ; } n /= 3 ; } return true ; } }
Go 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 package mainfunc checkPowersOfThree (n int ) bool { for ; n > 0 ; n /= 3 { if n % 3 == 2 { return false } } return true }
Rust 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 impl Solution { pub fn check_powers_of_three (mut n: i32 ) -> bool { while n > 0 { if n % 3 == 2 { return false ; } n /= 3 ; } return true ; } }
同步发文于CSDN 和我的个人博客 ,原创不易,转载经作者同意后请附上原文链接 哦~
千篇源码题解已开源