【leetcode刷题】T55-强整数

木又AI帮

修改于 2019-07-18 10:08:25

4380

修改于 2019-07-18 10:08:25

文章被收录于专栏：木又AI帮

【题目】

给定两个正整数 x 和 y，如果某一整数等于 x^i + y^j，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个强整数。

返回值小于或等于 bound 的所有强整数组成的列表。

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

示例 1：

输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释： 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

示例 2：

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

提示：

1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

【思路】

本题暴力破解即可，首先得到x和y的所有指数结果lsx和lsy，接着将lsx和lsy的元素分别相加，最后取得唯一集合。

【代码】

python版本

class Solution(object):
    def get_all_num(self, x, bound):
        ls = []
        if x == :
            return ls
        num = x
        while num < bound:
            ls.append(num)
            num *= x
        return ls
    
    def powerfulIntegers(self, x, y, bound):
        """
        :type x: int
        :type y: int
        :type bound: int
        :rtype: List[int]
        """
        ls1 = self.get_all_num(x, bound)
        ls2 = self.get_all_num(y, bound)
        res = []
        for ls1i in ls1:
            for ls2i in ls2:
                tmp = ls1i + ls2i
                if tmp > bound:
                    break
                res.append(tmp)
        return list(set(res))

C++版本

class Solution {
public:
    vector<int> get_all_num(int x, int bound){
        vector<int> ls(,);
        if(x == )
            return ls;
        int num = x;
        while(num < bound){
            ls.push_back(num);
            num *= x;
        }
        return ls;
    }
    vector<int> powerfulIntegers(int x, int y, int bound) {
        vector<int> ls1 = get_all_num(x, bound);
        vector<int> ls2 = get_all_num(y, bound);
        map<int, int> d;
        int tmp;
        for(auto n1: ls1){
            for(auto n2:ls2){
               tmp = n1 + n2;
                if(tmp > bound)
                    break;
                d[tmp] = ;
            }
        }
        vector<int> res;
        for(map<int, int>::iterator it=d.begin(); it != d.end(); it++)
            res.push_back(it->first);
        return res;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-05-09，如有侵权请联系 cloudcommunity@tencent.com 删除

c++