970.强整数

【LetMeFly】970.强整数

力扣题目链接：https://leetcode.cn/problems/powerful-integers/

给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。

如果某一整数可以表示为 xi + yj ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。

你可以按 任何顺序 返回答案。在你的回答中，每个值 最多 出现一次。

 

示例 1：

输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释： 
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

示例 2：

输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]

 

提示：

• 1 <= x, y <= 100
• 0 <= bound <= 106

方法一：枚举

如果$x = 1$，那么$x^i=1$，只有一种情况

否则则有$x\geq2$，那么$x^{20}\geq2^{20}=1048576\gt10^6$，最多有20种情况

所以我们直接枚举即可。当超过$bound$或者$x=1$时，退出循环（y同理）

i = 0
while True:
    first = x ** i
    if first > bound:
        break
    # 枚举j
    if x == 1:
        break
    i += 1

当然，我们也可以无脑从0枚举到20，这样退出循环的条件比较少，不容易出错

• 时间复杂度$O(\log^2bound)$
• 空间复杂度$O(\log bound)$

AC代码

C++

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> se;
        int i = 0;
        while (true) {
            int first = pow(x, i);
            if (first > bound) {
                break;
            }
            int j = 0;
            while (true) {
                int second = pow(y, j);
                int s = first + second;
                if (s > bound) {
                    break;
                }
                se.insert(s);
                if (y == 1) {
                    break;
                }
                j++;
            }
            if (x == 1) {
                break;
            }
            i++;
        }
        return vector<int>(se.begin(), se.end());
    }
};

Python

from typing import List

class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        se = set()
        i = 0
        while True:
            first = x ** i
            if first > bound:
                break

            j = 0
            while True:
                second = y ** j
                s = first + second
                if s > bound:
                    break
                se.add(s)
                if y == 1:
                    break
                j += 1

            if x == 1:
                break
            i += 1
        return list(se)

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/130461751