0970._Powerful_Integers.md

970. Powerful Integers

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/powerful-integers/

内容描述

Given two non-negative integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all powerful integers that have value less than or equal to bound.

You may return the answer in any order.  In your answer, each value should occur at most once.

 

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 
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
Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]
 

Note:

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

解题方案

思路 1 - 时间复杂度: O(log(bound, min(x,y)))- 空间复杂度: O(1)******

注意x和y都等于1的特殊情况，这样可能会超时

class Solution:
    def powerfulIntegers(self, x, y, bound):
        """
        :type x: int
        :type y: int
        :type bound: int
        :rtype: List[int]
        """
        if x == 1 and y == 1:
            if bound >= 2:
                return [2]
            else:
                return []
        if x == 1:
            res = set()
            j = 0
            while True:
                tmp = 1 + y ** j
                if tmp > bound:
                    break
                else:
                    res.add(tmp)
                j += 1
            return list(res)
        if y == 1:
            res = set()
            i = 0
            while True:
                tmp = x ** i + 1
                if tmp > bound:
                    break
                else:
                    res.add(tmp)
                i += 1
            return list(res)
                    
            return 
        res = set()
        i = 0
        while True:
            if x ** i + 1 > bound:
                break
            j = 0
            while True:
                tmp = x ** i + y ** j
                if tmp > bound:
                    break
                else:
                    res.add(tmp)
                j += 1
            i += 1
        return list(res)
        

思路 2 - 时间复杂度: O(log(bound, min(x,y)))- 空间复杂度: O(1)******

但其实可以及时退出，因为2^18 > 10^6，所以我们只要循环到18次方就足够了

class Solution(object): #aw
    def powerfulIntegers(self, x, y, bound):
        """
        :type x: int
        :type y: int
        :type bound: int
        :rtype: List[int]
        """
        res = set()
        
        for i in range(18): # 2**18 > bound
            for j in range(18):
                tmp = x ** i + y ** j 
                if tmp <= bound:
                    res.add(tmp)
                else:
                    break
                    
        return list(res)