阅读视图

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

每日一题-6 和 9 组成的最大数字🟢

给你一个仅由数字 6 和 9 组成的正整数 num

你最多只能翻转一位数字,将 6 变成 9,或者把 9 变成 6 。

请返回你可以得到的最大数字。

 

示例 1:

输入:num = 9669
输出:9969
解释:
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。

示例 2:

输入:num = 9996
输出:9999
解释:将最后一位从 6 变到 9,其结果 9999 是最大的数。

示例 3:

输入:num = 9999
输出:9999
解释:无需改变就已经是最大的数字了。

 

提示:

  • 1 <= num <= 10^4
  • num 每一位上的数字都是 6 或者 9 。

两种方法:用字符串/不用字符串(Python/Java/C++/C/Go/JS/Rust)

分析

要想把数字变大,只能把 $6$ 改成 $9$。

比如 $\textit{num}=9669$:

  • 改高位的 $6$,得到 $9969$。
  • 改低位的 $6$,得到 $9699$。
  • $9969 > 9699$。

改高位的 $6$ 比改低位的 $6$ 更好。由于至多改一次,所以改最高位的 $6$。若 $\textit{num}$ 无 $6$,则 $\textit{num}$ 不变。

方法一:用字符串

###py

class Solution:
    def maximum69Number(self, num: int) -> int:
        s = str(num).replace('6', '9', 1)  # 替换第一个 6
        return int(s)

###py

class Solution:
    def maximum69Number(self, num: int) -> int:
        s = str(num)
        i = s.find('6')
        if i < 0:
            return num
        return int(s[:i] + '9' + s[i + 1:])

###java

class Solution {
    public int maximum69Number(int num) {
        String s = String.valueOf(num).replaceFirst("6", "9"); // 替换第一个 6
        return Integer.parseInt(s);
    }
}

###java

class Solution {
    public int maximum69Number(int num) {
        String s = Integer.toString(num);
        int i = s.indexOf('6');
        if (i < 0) {
            return num;
        }
        s = s.substring(0, i) + "9" + s.substring(i + 1);
        return Integer.parseInt(s);
    }
}

###cpp

class Solution {
public:
    int maximum69Number(int num) {
        string s = to_string(num);
        int i = s.find('6');
        if (i == string::npos) {
            return num;
        }
        s[i] = '9';
        return stoi(s);
    }
};

###c

int maximum69Number(int num) {
    char s[6];
    sprintf(s, "%d", num);
    char* p = strchr(s, '6');
    if (p == NULL) {
        return num;
    }
    *p = '9';
    return atoi(s);
}

###go

func maximum69Number(num int) int {
s := strconv.Itoa(num)
s = strings.Replace(s, "6", "9", 1) // 替换第一个 6
ans, _ := strconv.Atoi(s)
return ans
}

###js

var maximum69Number = function(num) {
    const s = String(num).replace('6', '9'); // 替换第一个 6
    return parseInt(s);
};

###rust

impl Solution {
    pub fn maximum69_number(num: i32) -> i32 {
        num.to_string()
           .replacen("6", "9", 1) // 替换第一个 6
           .parse()
           .unwrap()
    }
}

复杂度分析

  • 时间复杂度:$\mathcal{O}(\log \textit{num})$。
  • 空间复杂度:$\mathcal{O}(\log \textit{num})$。

方法二:不用字符串

可以不用转成字符串处理,而是不断取最低位(模 $10$),去掉最低位(除以 $10$),直到数字为 $0$。

例如 $\textit{num}=9669$:

  1. 初始化 $x=\textit{num}$。
  2. 通过 $x\bmod 10$ 取到个位数 $9$,然后把 $x$ 除以 $10$(下取整),得到 $x=966$。
  3. 再次 $x\bmod 10$ 取到十位数 $6$,然后把 $x$ 除以 $10$(下取整),得到 $x=96$。
  4. 再次 $x\bmod 10$ 取到百位数 $6$,然后把 $x$ 除以 $10$(下取整),得到 $x=9$。
  5. 最后 $x\bmod 10$ 取到千位数 $9$,然后把 $x$ 除以 $10$(下取整),得到 $x=0$。此时完成了遍历 $\textit{num}$ 的每个数位,退出循环。

在这个过程中,维护一个变量 $\textit{base}$,初始值为 $1$,在循环末尾把 $\textit{base}$ 乘以 $10$。每当我们遍历到一个等于 $6$ 的数位,就保存此刻的 $\textit{base}$,即更新 $\textit{maxBase} = \textit{base}$。其中 $\textit{maxBase}$ 初始值为 $0$。由于我们从低位往高位遍历,所以最终的 $\textit{maxBase}$ 就是最高位的 $6$ 对应的 $\textit{base}$。在上面的例子中,我们可以得到 $\textit{maxBase} = 100$。

最终答案为

$$
\textit{num} + \textit{maxBase}\cdot 3
$$

在上面的例子中,答案为 $9669 + 100\cdot 3 = 9969$。

注:如果 $\textit{num}$ 中没有 $6$,由于我们初始化 $\textit{maxBase}=0$,最终答案为 $\textit{num}$。

###py

class Solution:
    def maximum69Number(self, num: int) -> int:
        max_base = 0
        base = 1
        x = num
        while x:
            x, d = divmod(x, 10)
            if d == 6:
                max_base = base
            base *= 10
        return num + max_base * 3

###java

class Solution {
    public int maximum69Number(int num) {
        int maxBase = 0;
        int base = 1;
        for (int x = num; x > 0; x /= 10) {
            if (x % 10 == 6) {
                maxBase = base;
            }
            base *= 10;
        }
        return num + maxBase * 3;
    }
}

###cpp

class Solution {
public:
    int maximum69Number(int num) {
        int max_base = 0;
        int base = 1;
        for (int x = num; x > 0; x /= 10) {
            if (x % 10 == 6) {
                max_base = base;
            }
            base *= 10;
        }
        return num + max_base * 3;
    }
};

###c

int maximum69Number(int num) {
    int max_base = 0;
    int base = 1;
    for (int x = num; x > 0; x /= 10) {
        if (x % 10 == 6) {
            max_base = base;
        }
        base *= 10;
    }
    return num + max_base * 3;
}

###go

func maximum69Number(num int) int {
maxBase := 0
base := 1
for x := num; x > 0; x /= 10 {
if x%10 == 6 {
maxBase = base
}
base *= 10
}
return num + maxBase*3
}

###js

var maximum69Number = function(num) {
    let maxBase = 0;
    let base = 1;
    for (let x = num; x > 0; x = Math.floor(x / 10)) {
        if (x % 10 === 6) {
            maxBase = base;
        }
        base *= 10;
    }
    return num + maxBase * 3;
};

###rust

impl Solution {
    pub fn maximum69_number(num: i32) -> i32 {
        let mut max_base = 0;
        let mut base = 1;
        let mut x = num;
        while x > 0 {
            if x % 10 == 6 {
                max_base = base;
            }
            base *= 10;
            x /= 10;
        }
        num + max_base * 3
    }
}

复杂度分析

  • 时间复杂度:$\mathcal{O}(\log \textit{num})$。
  • 空间复杂度:$\mathcal{O}(1)$。

思考题

  1. 改成求最小数字。
  2. 额外输入一个正整数 $k$,至多翻转 $k$ 个数,返回可以得到的最大数字。
  3. 给定正整数 $\textit{low}$ 和 $\textit{high}$,计算闭区间 $[\textit{low},\textit{high}]$ 中的所有整数 $x$ 的 $\texttt{maximum69Number}(x)$ 之和。

欢迎在评论区分享你的思路/代码。

专题训练

见下面贪心题单的「§3.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站@灵茶山艾府

6 和 9 组成的最大数字

方法一:贪心 + 字符串

思路与算法

此题要求将一个由数字 $6$ 和 $9$ 构成的十进制数 $\textit{num}$ 进行至多一次 $6$ 和 $9$ 之间的翻转得到的最大数字。由十进制数的性质易知:贪心的选择数位最高的一个 $6$ 变成 $9$,得到的答案就是最大的。如果不存在这样的 $6$,则说明这个数字全由数字 $9$ 构成。根据题意,此时不对 $\textit{num}$ 做任何更改即为最优解。

对于算法实现,我们使用字符数组来处理 $\textit{num}$ 较为方便。首先将 $\textit{num}$ 转为字符数组,然后从左到遍历字符,按上述算法处理。最后将修改后的字符数组转回数字即为所求。

代码

###C++

class Solution {
public:
    int maximum69Number (int num) {
        string s = to_string(num);
        for (char &c : s) {
            if (c == '6') {
                c = '9';
                break;
            }
        }
        return stoi(s);
    }
};

###Java

public class Solution {
    public int maximum69Number (int num) {
        char[] chars = Integer.toString(num).toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '6') {
                chars[i] = '9';
                break;
            }
        }
        return Integer.parseInt(new String(chars));
    }
}

###C#

public class Solution {
    public int Maximum69Number (int num) {
        char[] chars = num.ToString().ToCharArray();
        for (int i = 0; i < chars.Length; i++) {
            if (chars[i] == '6') {
                chars[i] = '9';
                break;
            }
        }
        return int.Parse(new string(chars));
    }
}

###Go

func maximum69Number(num int) int {
    s := strconv.Itoa(num)
    chars := []byte(s)
    for i := 0; i < len(chars); i++ {
        if chars[i] == '6' {
            chars[i] = '9'
            break
        }
    }
    result, _ := strconv.Atoi(string(chars))
    return result
}

###Python

class Solution:
    def maximum69Number (self, num: int) -> int:
        s = list(str(num))
        for i in range(len(s)):
            if s[i] == '6':
                s[i] = '9'
                break
        return int(''.join(s))

###C

int maximum69Number(int num) {
    char s[20];
    sprintf(s, "%d", num);
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '6') {
            s[i] = '9';
            break;
        }
    }
    return atoi(s);
}

###Rust

impl Solution {
    pub fn maximum69_number (num: i32) -> i32 {
        let mut s = num.to_string().chars().collect::<Vec<char>>();
        for i in 0..s.len() {
            if s[i] == '6' {
                s[i] = '9';
                break;
            }
        }
        s.iter().collect::<String>().parse().unwrap()
    }
}

###JavaScript

var maximum69Number = function (num) {
    let charArray = [...num.toString()];

    for (let i = 0; i < charArray.length; i++) {
        if (charArray[i] === '6') {
            charArray[i] = '9';
            break;
        }
    }

    return Number(charArray.join(''));
};

###TypeScript

function maximum69Number(num: number): number {
    let charArray = [...num.toString()];

    for (let i = 0; i < charArray.length; i++) {
        if (charArray[i] === '6') {
            charArray[i] = '9';
            break;
        }
    }

    return Number(charArray.join(''));
};

复杂度分析

  • 时间复杂度:$O(\log \textit{num})$。

  • 空间复杂度:$O(\log \textit{num})$。

方法二:贪心 + 数学

思路与算法

思想同方法一,但是不依赖字符串操作,而是通过纯数学的方式找到最高位的 $6$ 并更改为 $9$。

首先初始化一个基数 $\textit{digitBase} = 10^{\lfloor \log_{10}(\textit{num}) \rfloor}$,这个基数代表了 $\textit{num}$ 的最高位。然后从高位向低位遍历,每次将 $\textit{digitBase}$ 除以 $10$。在每一次循环中,通过 $\lfloor \textit{num} \div \textit{digitBase} \rfloor \bmod 10$ 来获取当前基数 $\textit{digitBase}$ 所在的十进制位上的数字。一旦这个数字等于 $6$,我们就可以确定这就是需要修改的最高位的 $6$。此时,我们将 $\textit{num}$ 加上 $3 \times \textit{digitBase}$,即可将该位的 $6$ 修改为 $9$,结果即为所求。

代码

###C++

class Solution {
public:
    int maximum69Number (int num) {
        int digitBase = pow(10, (int)log10(num));
        while (digitBase > 0) {
            if ((num / digitBase) % 10 == 6) {
                num += 3 * digitBase;
                return num;
            }
            digitBase /= 10;
        }
        
        return num;
    }
};

###Java

public class Solution {
    public int maximum69Number (int num) {
        int digitBase = (int)Math.pow(10, (int)Math.log10(num));
        while (digitBase > 0) {
            if ((num / digitBase) % 10 == 6) {
                num += 3 * digitBase;
                return num;
            }
            digitBase /= 10;
        }
        
        return num;
    }
}

###C#

public class Solution {
    public int Maximum69Number (int num) {
        int digitBase = (int)Math.Pow(10, (int)Math.Log10(num));
        while (digitBase > 0) {
            if ((num / digitBase) % 10 == 6) {
                num += 3 * digitBase;
                return num;
            }
            digitBase /= 10;
        }
        
        return num;
    }
}

###Go

func maximum69Number(num int) int {
    digitBase := int(math.Pow10(int(math.Log10(float64(num)))))
    for digitBase > 0 {
        if (num / digitBase) % 10 == 6 {
            num += 3 * digitBase
            return num
        }
        digitBase /= 10
    }
    
    return num
}

###Python

class Solution:
    def maximum69Number (self, num: int) -> int:
        digit_base = 10 ** int(math.log10(num)) if num != 0 else 0
        while digit_base > 0:
            if (num // digit_base) % 10 == 6:
                num += 3 * digit_base
                return num
            digit_base = digit_base // 10
        
        return num

###C

int maximum69Number(int num) {
    int digitBase = pow(10, (int)log10(num));
    while (digitBase > 0) {
        if ((num / digitBase) % 10 == 6) {
            num += 3 * digitBase;
            return num;
        }
        digitBase /= 10;
    }
    
    return num;
}

###Rust

impl Solution {
    pub fn maximum69_number (num: i32) -> i32 {
        let mut digit_base = 10i32.pow((num as f32).log10() as u32);
        let mut num = num;
        while digit_base > 0 {
            if (num / digit_base) % 10 == 6 {
                num += 3 * digit_base;
                return num;
            }
            digit_base /= 10;
        }
        
        num
    }
}

###JavaScript

var maximum69Number = function (num) {
    let digitBase = Math.pow(10, Math.trunc(Math.log10(num)));

    while (digitBase > 0) {
        if (Math.trunc(num / digitBase) % 10 === 6) {
            num += 3 * digitBase;
            return num;
        }
        digitBase = Math.trunc(digitBase / 10);
    }

    return num;
};

###TypeScript

function maximum69Number(num: number): number {
    let digitBase = Math.pow(10, Math.trunc(Math.log10(num)));

    while (digitBase > 0) {
        if (Math.trunc(num / digitBase) % 10 === 6) {
            num += 3 * digitBase;
            return num;
        }
        digitBase = Math.trunc(digitBase / 10);
    }

    return num;
};

复杂度分析

  • 时间复杂度:$O(\log \textit{num})$。

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

C 不转换字符串

解题思路

循环看看哪个6最靠前,然后加上3的x次幂即可
(4ms, 61.64%; 6.8MB, 100.00%)

代码

###c

#include <Math.h>
int maximum69Number (int num){
    int count = 0, th = 0;          // count 记录除了多少次,th记录最大的6在第几位
    int re = num;
    while(re){
        count++;
        if(re%10==6)
           th = count;
        re /= 10;
    }
    return num+3*pow(10,th-1);
}

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

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