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

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

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

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

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

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

方法一：二进制枚举

题目分析

解题思路

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

vector<int> three(1, 1);  // 初始值是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;

复杂度分析

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

方法二：进制转换

AC代码

C++

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

以上就是C++ LeetCode1780判断数字是否可以表示成三的幂的和的详细内容，更多关于C++ LeetCode判断数字三的幂和的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C++ LeetCode1781题解所有子字符串美丽值之和

    目录 LeetCode 1781.所有子字符串美丽值之和 方法一:前缀和 AC代码 C++ 方法二:边遍历边计算 AC代码 C++ LeetCode 1781.所有子字符串美丽值之和 力扣题目链接:leetcode.cn/problems/su… 一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差. 比方说,"abaacc" 的美丽值为 3 - 1 = 2 . 给你一个字符串 s ,请你返回它所有子字符串的 美丽值 之和. 示例 1: 输入:s = &quo

  • C++ LeetCode1945题解字符串转化后的各位数字之和

    目录 1945.字符串转化后的各位数字之和 方法一:计算 AC代码 C++ 1945.字符串转化后的各位数字之和 力扣题目链接:leetcode.cn/problems/su… 给你一个由小写字母组成的字符串 s ,以及一个整数 k . 首先,用字母在字母表中的位置替换该字母,将 s 转化 为一个整数(也就是,'a' 用 1 替换,'b' 用 2 替换,... 'z' 用 26 替换).接着,将整数 转换 为其 各位数字之和 .共重复 转换 操作 k 次 . 例如,如果 s = "zbax&qu

  • C++ LeetCode1832题解判断句子是否为全字母句

    目录 LeetCode 1832.判断句子是否为全字母句 方法一:统计 AC代码 C++ LeetCode 1832.判断句子是否为全字母句 力扣题目链接:leetcode.cn/problems/ch… 全字母句 指包含英语字母表中每个字母至少一次的句子. 给你一个仅由小写英文字母组成的字符串 sentence ,请你判断 sentence 是否为 全字母句 . 如果是,返回 true :否则,返回 false . 示例 1: 输入:sentence = "thequickbrownfoxju

  • C++ LeetCode300最长递增子序列

    目录 LeetCode 300.最长递增子序列 方法一:动态规划 AC代码 C++ LeetCode 300.最长递增子序列 力扣题目链接:leetcode.cn/problems/lo… 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度. 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序.例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列. 示例 1: 输入:nums = [10,9,2,5,3,7,101,18]输出:4

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • C++ LeetCode0547题解省份数量图的连通分量

    目录 LeetCode 547.省份数量 方法一:BFS求图的连通分量 AC代码 C++ LeetCode 547.省份数量 力扣题目链接:leetcode.cn/problems/nu… 有 n 个城市,其中一些彼此相连,另一些没有相连.如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连. 省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市. 给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i

  • C++ LeetCode1827题解最少操作使数组递增

    目录 LeetCode1827.最少操作使数组递增 方法一:遍历 AC代码 C++ LeetCode1827.最少操作使数组递增 力扣题目链接:leetcode.cn/problems/mi… 给你一个整数数组 nums (下标从 0 开始).每一次操作中,你可以选择数组中一个元素,并将它增加 1 . 比方说,如果 nums = [1,2,3] ,你可以选择增加 nums[1] 得到 nums = [1,3,3] . 请你返回使 nums 严格递增 的 最少 操作次数. 我们称数组 nums 是

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

    目录 LeetCode 1780.判断一个数字是否可以表示成三的幂的和 方法一:二进制枚举 题目分析 解题思路 复杂度分析 AC代码 C++ 方法二:进制转换 AC代码 C++ LeetCode 1780.判断一个数字是否可以表示成三的幂的和 力扣题目链接:leetcode.cn/problems/ch… 给你一个整数 n ,如果你可以将 n 表示成若干个不同的三的幂之和,请你返回 true ,否则请返回 false . 对于一个整数 y ,如果存在整数 x 满足 y == 3x ,我们称这个整

  • js中判断数字\字母\中文的正则表达式 (实例)

    /* 判断指定的内容是否为空,若为空则弹出 警告框 */ function isEmpty(theValue, strMsg){ if(theValue==""){ alert(strMsg+"不能为空!"); return true; } return false; } /* 中文判断函数,允许生僻字用英文"*"代替 返回true表示是符合条件,返回false表示不符合 */ function isChinese(str){ var badCh

  • java正则表达式获取大括号小括号内容并判断数字和小数亲测可用

     获取大括号小括号内容 项目开发用到了,暂做个简单记录 private static String regex = "\\{([^}]*)\\}";//匹配大括号 private static String regexx = "\\(([^}]*)\\)";//匹配小括号 public static void main(String[] args) { String dakuohao = "{a+b}={c+d}>{d}"; Pattern

  • JavaScript判断数字是否为质数的方法汇总

    JavaScript判断数字是否为质数的方法汇总

    前言 今天看到一个题目,让判断一个数字是否为质数.看上去好像不难.因此,我决定实现一下. DOM结构 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>计算500以内的质数并输出</title> <meta name="viewport" content="width=d

  • 对python 判断数字是否小于0的方法详解

    为了精度更准确 可以使用数字的绝对值 < 1.0e-16  或者 < 1.0e-8来对比 abs(Num) <  1.0e-16 以上这篇对python 判断数字是否小于0的方法详解就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • python如果快速判断数字奇数偶数

    这篇文章主要介绍了python如果快速判断数字奇数偶数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 使用 按位与运算符(&) 将能更加快速地判断一个整数是奇数还是偶数 使用举例如下: def check_number(n): if n & 1: return '奇数' else: return '偶数' # 简单测试: for i in range(-3, 3): print(i, check_number(i)) 不过缺点就是不够直观

  • python中判断数字是否为质数的实例讲解

    在计算机程序中,算法是灵魂,是程序的精髓所在.程序执行效率的高低直接取决于算法的优劣,所以计算机算法是计算机课程必修课.算法可以快速计算出我们所需要的结果,例如判断质数,这是很基础的内容,具体如何操作呢?下面小编向大家演示在python如何判断数字是否为质数. 质数:一个大于1的自然数,除了1和它本身外,不能被其他自然数(质数)整除(2, 3, 5, 7等),换句话说就是该数除了1和它本身以外不再有其他的因数. 判断代码: def isprime(a): if isinstance(a,int)

  • Java去掉数字字符串开头的0三种方法(推荐)

    方式一: 例如:"0000123" (字符串必须全为数字) 处理过程: String tempStr = "0000123"; int result = Integer.parseInt(tempStr); result 结果:123 方式二: 例如:"0000123" 处理过程: String str = "0000123"; String newStr = str.replaceFirst("^0*",

  • 利用Java将2019拆分成三个素数平方和的方法实例

    主要分析: (1):将2019拆分成三个素数平方和,就要先得到三个素数,这也就涉及到了三个素数的范围,我们不妨从其中最大的质数推论,因为是三个素数的平方和,所以最大的素数必然小于,现在也就了解了三个素数的大致范围,那么也就可以将这个范围内的素数放进数组中操作: (2):其次,三个素数可能有多种组合方式,可以利用到三重循环遍历所有情况,但也因为组合的多样,最后结果可能重复出现,因此要去重,例:(7.11.43)和(11.7.43),可以发现,这两对质数,虽然顺序不一,但表达的却是同一种结果,那发生

  • python判断数字是否是超级素数幂

    如果一个数字能表示成 p^q,且p是一个素数,q为大于1的正整数,则此数字就是超级素数幂. param number: 测试该数字是否是超级素数幂 return: 如果不是就返回 False,如果是就返回 p 和 q 值 例如,输入125,返回(5,3) 代码: import math def get_prime(number): ''' 寻找小于number的所有的质数,时间复杂度o(n^2) ''' if number <= 1: print 'Wrong given number.' re

随机推荐