Every day a Leetcode

题目来源：970. 强整数

解法1：枚举

枚举 i 和 j 所有的可能性，然后计算 pow(x, i) + pow(y, j)，判断是否 <= bound。若满足，则放入一个哈希集合，最后将集合转成数组返回。

第一种枚举方法：

int num1 = 1;
for (int i = 0; i <= 20; i++)
{int num2 = 1;for (int j = 0; j <= 20; j++){int num = num1 + num2;if (num <= bound)nums.insert(num);elsebreak;num2 *= y;}if (num1 >= bound)break;num1 *= x;
}

第二种枚举方法：

for (int i = 1; i < bound; i *= x)
{for (int j = 1; i + j <= bound; j *= y){nums.insert(i + j);if (y == 1)break;}if (x == 1)break;
}

代码：

/** @lc app=leetcode.cn id=970 lang=cpp** [970] 强整数*/// @lc code=start
class Solution
{
public:vector<int> powerfulIntegers(int x, int y, int bound){unordered_set<int> nums;// for (int i = 1; i < bound; i *= x)// {//     for (int j = 1; i + j <= bound; j *= y)//     {//         nums.insert(i + j);//         if (y == 1)//             break;//     }//     if (x == 1)//         break;// }int num1 = 1;for (int i = 0; i <= 20; i++){int num2 = 1;for (int j = 0; j <= 20; j++){int num = num1 + num2;if (num <= bound)nums.insert(num);elsebreak;num2 *= y;}if (num1 >= bound)break;num1 *= x;}return vector<int>(nums.begin(), nums.end());}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(log²(bound))，双层循环的时间复杂度是 O(log²(bound))。

空间复杂度：O(log²(bound))，是哈希集合的空间复杂度。