LeetCode 970. 强整数

文章目录

• • 1. 题目
  • 2. 解题
  • • 2.1 暴力法
    • 2.2 优化双重循环

1. 题目

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

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

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

示例 1： 输入：x = 2, y = 3, bound = 10 输出：[2,3,4,5,7,9,10]

解释：
2 = 2⁰ + 3⁰
3 = 2¹ + 3⁰
4 = 2⁰ + 3¹
5 = 2¹ + 3¹
7 = 2² + 3¹
9 = 2³ + 3⁰
10 = 2⁰ + 3²

示例 2： 输入：x = 3, y = 5, bound = 15 输出：[2,4,6,8,10,14]提示： 1 <= x <= 100 1 <= y <= 100 0 <= bound <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powerful-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 暴力法

• 双重循环+set去重

class Solution { public:vector<int> powerfulIntegers(int x, int y, int bound) {int i, j, res;unordered_set<int> s;int Maxi = (x != 1) ? log(bound)/log(x)+1 : bound/2;int Maxj = (y != 1) ? log(bound)/log(y)+1 : bound/2;for(i = 0; i <= Maxi; i++){for(j = 0; j <= Maxj; j++){res = pow(x,i)+pow(y,j);if(res <= bound)s.insert(res);}} return vector<int> (s.begin(),s.end());} };

2.2 优化双重循环

• 优化x或者y等于1时的情况，提前退出（1的任何次方等于1，只有一种选择）

class Solution { public:vector<int> powerfulIntegers(int x, int y, int bound) {int i = 0, j = 0, res;unordered_set<int> s;int powx, powy;for(i = 0; (powx = pow(x,i)) <= bound; i++){for(j = 0; (powy = pow(y,j)) <= bound; j++){res = powx+powy;if(res <= bound)s.insert(res);if(y == 1)break;}if(x == 1)break;} return vector<int> (s.begin(),s.end());} };

or

class Solution { public:vector<int> powerfulIntegers(int x, int y, int bound) {int i, j, res;unordered_set<int> s;int Maxi = (x != 1) ? log(bound)/log(x)+1 : 1;int Maxj = (y != 1) ? log(bound)/log(y)+1 : 1;for(i = 0; i < Maxi; i++){for(j = 0; j < Maxj; j++){res = pow(x,i)+pow(y,j);if(res <= bound)s.insert(res);}} return vector<int> (s.begin(),s.end());} };

总结

以上是生活随笔为你收集整理的LeetCode 970. 强整数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。