题目来源：https://leetcode.com/problems/powerful-integers/description/
标记难度：Medium
提交次数：1/1
代码效率：4ms
题意
给定正整数x和y（1 <= x, y <= 100），求所有在[1, bound]（0 <= bound <= 10^6）范围内的x^i + y^j，要求去重。
分析
去掉x或y为1的情况，由于log(1000000) / log(2) = 19，所以可以直接枚举所有x和y的幂和，然后去重。总的来说很简单。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
if (x > y) swap(x, y);
if (x == 1 && y == 1) {
if (bound >= 2) return {2};
else return {};
}
if (x == 1) {
vector<int> ans;
int yj = 1;
for (int j = 0; yj <= bound; j++) {
int t = yj + 1;
if (t <= bound) ans.push_back(t);
}
return ans;
}
unordered_set<int> numbers;
vector<int> ans;
int xi = 1;
for (int i = 0; xi <= bound; i++) {
int yj = 1;
for (int j = 0; yj <= bound; j++) {
int t = xi + yj;
if (t <= bound && numbers.find(t) == numbers.end()) {
numbers.insert(t);
ans.push_back(t);
}
yj *= y;
}
xi *= x;
}
return ans;
}
};
|
近期评论