970. Powerful Integers

2023-12-21 16:19

文章标签 integers powerful 970

本文主要是介绍970. Powerful Integers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

970. 强整数

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

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

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

示例 1：
输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释： 
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
示例 2：
输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]
提示：

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

解法一

class Solution {
public:vector<int> powerfulIntegers(int x, int y, int bound) {unordered_set<int> us;int temp;if(x == 1 && y == 1) return bound > 1 ? vector<int>(1, 2) : vector<int>();else if(x == 1) {for(int i = 0; (temp = pow(y, i) + 1) < bound; i++) us.insert(temp);}else if(y == 1) {for(int i = 0; (temp = pow(x, i) + 1) < bound; i++) us.insert(temp);}else {int xi;for(int i = 0; (temp = (xi = pow(x, i)) + pow(y, 0)) <= bound; i++) {us.insert(temp);for(int j = 1; (temp = xi + pow(y, j)) <= bound; j++) {us.insert(temp);}}}return vector<int>(us.begin(), us.end());}
};

解法二

class Solution {
public:vector<int> powerfulIntegers(int x, int y, int bound) {int temp;unordered_set<int> us;for(int i = 0; i <= 19; i++) {for(int j = 0; j <= 19; j++) {if( (temp = pow(x, i) + pow(y, j)) > 0 && temp <= bound) us.insert(temp);}}return vector<int>(us.begin(), us.end());}
};

解法三

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

思路：

解法一

注意区别x和y等于1的情况，如果两个都为1，那根据bound的值应该返回{2}或{}。如果x、y其中1个为1，就退化为成了一个变量的i次方求小于等于boud的问题。

如果两个都不为1，那就从i = 0开始：对于每一个i，遍历j从0开始的所有合法取值，将其添加到哈希表中，直到遇到一个i使其和大于bound。最后将其转为vector返回。

解法二

上一个解法逻辑有点复杂，解法二更简洁一些。

它基于这样一个隐含条件：如果x^i + y^j <= bound，那么一定有x^i < bound且y^j < bound（不含等于号，因为x^i 或 y^j至少等于1）。那么就一定有i < log(bound) / log(x)且j < log(bound) / log(y)。

因为bound最大为1000000，i最大（这时x应取2，i = log(1000000)/log(2)）为19，对j同理。所以我们就遍历i、j从0到19，满足的话将其保存。

这里要判断加法溢出，如果i和j都比较大（比如都是19）其和就是负数，要判断其和大于0。

解法三

上一个解法是官方题解的思路。解法三与其类似，只是将原来i、j的上限19改为了计算出的值m、n。

令m = i < log(bound) / log(x)，n = j < log(bound) / log(y)。