970.强整数

链接：970.强整数
难度：Medium
标签：哈希表、数学、枚举
简介：给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。

题解 1 - rust

• 编辑时间：2023-05-02
• 执行用时：4ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn powerful_integers(x: i32, y: i32, bound: i32) -> Vec<i32> {
        let mut list = vec![];
        let mut res = std::collections::HashSet::<i32>::new();
        let mut i = 0;
        while x.pow(i) <= bound {
            list.push(x.pow(i));
            if x == 1 {
                break;
            }
            i += 1;
        }
        i = 0;
        while y.pow(i) <= bound {
            let ynum = y.pow(i);
            for xnum in &list {
                if ynum + *xnum <= bound {
                    res.insert(ynum + *xnum);
                } else {
                    break;
                }
            }
            if y == 1 {
                break;
            }
            i += 1;
        }
        res.into_iter().collect()
    }
}

题解 2 - cpp

• 编辑时间：2023-05-02
• 内存消耗：6.6MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        vector<int> list;
        unordered_set<int> res;
        for (int i = 0; pow(x, i) <= bound; i++) {
            list.push_back(pow(x, i));
            if (x == 1) break;
        }
        for (int i = 0; pow(y, i) <= bound; i++) {
            int ynum = pow(y, i);
            for (auto &xnum : list)
                if (ynum + xnum <= bound) res.insert(ynum + xnum);
                else break;
            if (y == 1) break;
        }
        return vector<int>(res.begin(), res.end());
    }
};

题解 3 - python

• 编辑时间：2023-05-02
• 执行用时：48ms
• 内存消耗：16.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        list = []
        res = set()
        i = 0
        while pow(x, i) <= bound:
            list.append(pow(x, i))
            if x == 1:
                break
            i += 1
        i = 0
        while pow(y, i) <= bound:
            ynum = pow(y, i)
            for xnum in list:
                if ynum + xnum <= bound:
                    res.add(ynum + xnum)
                else:
                    break
            if y == 1:
                break
            i += 1
        return [num for num in res]