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

2021-03-07

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

难度中等

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

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

示例 1：

1
2
3

输入：n = 12
输出：true
解释：12 = 31 + 32

示例 2：

1
2
3

输入：n = 91
输出：true
解释：91 = 30 + 32 + 34

示例 3：

1 2	输入：n = 21 输出：false

提示：

1 <= n <= 10^7

贪心算法

最大值是$10^7$,所以从后往前遍历粗略设置为最大指数是30，只要剩余的数字大于一个某个3的幂，就减去它，直到最大指数是0，如果到最后剩下的结果为0，那么就可以组成，否则不行


class Solution {
    public boolean checkPowersOfThree(int n) {
		
        for(int i=30;i>=0;i--){
            int di=(int)Math.pow(3,i);
            if(n-di>=0){
                n-=di;
            }
        }

        if(n==0)return true;
        
        return false;
    }
}

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true