开发者

C++ LeetCode1780判断数字是否可以表示成三的幂的和

目录
  • LeetCode 1780.判断一个数字是否可以表示成三的幂的和
  • 方法一:二进制枚举
    • 题目分析
    • 解题思路
    • 复杂度分析
  • AC代码
    • C++
  • 方法二:进制转换
    • AC代码
      • C++

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

    力扣题目链接:leetcode.cn/problems/ch…

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

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

    C++ LeetCode1780判断数字是否可以表示成三的幂的和

    方法一:二进制枚举

    题目分析

    C++ LeetCode1780判断数字是否可以表示成三的幂的和

    解题思路

    那么,我们直接开辟一个数组,把所有的小于等于nnn的“3的幂”放入数组

    vector<int> three(1, 1);  // 初始值是1个1
    while (three.back() < n) {
        three.push_back(three.back() * 3);
    }
    

    C++ LeetCode1780判断数字是否可以表示成三的幂的和

    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;
    

    复杂度分析

    C++ LeetCode1780判断数字是否可以表示成三的幂的和

    AC代码

    C++

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

    方法二:进制转换

    C++ LeetCode1780判断数字是否可以表示成三的幂的和

    AC代码

    C++

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

    以上就是C++ LeetCode1780判断数字是否可以表示成三的幂的和的详细内容javascript,更多关于C++ Leeht开发者_C培训tp://www.devze.comtCode判断数字三的幂和的资料请关注我们其它相关文章!

    0

    上一篇:

    下一篇:

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    最新开发

    开发排行榜