0970. Powerful Integers - kumaeki/LeetCode GitHub Wiki

970. Powerful Integers

Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound.

An integer is powerful if it can be represented as xi + yj for some integers i >= 0 and j >= 0.

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 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

Example 2:

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

Constraints:

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

解法1

每次尝试增加x 或者y的幂次, 然后加起来判断是否超过边界.

但是,太慢了, 重复计算太多了.

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> res = new HashSet<Integer>();
        // 以1为起始值开始计算
        helper(x, y, bound, 1, 1, res);
        return new ArrayList<Integer>(res);
    }
    
    private void helper(int x, int y, int bound, int x_cur, int y_cur, Set<Integer> res){
        int cur = x_cur + y_cur;
        // 如果当前的结算结果满足边界条件
        if(cur <= bound){
            // 将当前结果加入返回结果
            res.add(cur);
            // 尝试计算下一个x
            helper(x, y, bound, x_cur * x, y_cur, res);
            // 尝试结算下一个y
            helper(x, y, bound, x_cur, y_cur * y, res);
        }
    }
}

解法2

用递归(解法1)貌似容易栈溢出. 那么用普通的循环来做.

先得到x和y可能的所有幂值, 然后相互相加得到符合条件的值放入结果list.

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {

        // 因为可能会有重复结果,所以用HashSet过滤重复值
        Set<Integer> res = new HashSet<Integer>();
        
        // x 和 y 可能的幂值
        List<Integer> list_x = getList(x, bound), list_y = getList(y, bound);
        
        // x 递减计算
        for(int i = list_x.size() - 1; i >= 0; i--){
            // y 递增计算
            for(int j = 0; j < list_y.size(); j++){
                // 满足条件则放入set中
                int cur = list_x.get(i) + list_y.get(j);
                if( cur <= bound)
                    res.add(cur);
                else
                    break;
            }
        }
        
        // 由set生成list返回
        return new ArrayList<Integer>(res);
    }
    
    // 得到小于bound的所有n的幂值的list
    private List<Integer> getList(int n, int bound){
        List<Integer> list= new ArrayList<Integer>();
        if(bound == 0)
            return list;
        
        list.add(1);
        if(n == 1)
            return list;
        
        int p = n;
        while(p <= bound){
            list.add(p);
            p *= n;
        }
        
        return list;
    }
}
⚠️ **GitHub.com Fallback** ⚠️