LeetCode970. 强整数
2024-10-21 07:40:12
问题：970. 强整数
- 用户通过次数0
- 用户尝试次数0
- 通过次数0
- 提交次数0
- 题目难度Easy
给定两个非负整数 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 <= 1001 <= y <= 1000 <= bound <= 10^6
链接：https://leetcode-cn.com/contest/weekly-contest-118/problems/powerful-integers/
分析：
数据范围并不大，只需要列出所有的Xs=X^i<=bound，Ys=Y^i<=bound，然后找到满足Xs+Ys<=bound即可。
需要注意的有
1.如果x/等于1，对应的列表里面只会有1
2,有可能X^i11+Y^i12==X^i21+Y^i22，且i11!=i21,i12!=i22，比如2^4+4^0=2^0+4^2，所以需要对和去重。
AC Code：
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
vector<int> ret;
vector<int> xs;
vector<int> ys;
int tmp = ;
while (true)
{
if (x == )
{
xs.emplace_back(x);
break;
}
int local = pow(x, tmp);
if (local > bound)
{
break;
}
else
{
xs.emplace_back(local);
tmp++;
}
}
tmp = ;
while (true)
{
if (y == )
{
ys.emplace_back(y);
break;
}
int local = pow(y, tmp);
if (local > bound)
{
break;
}
else
{
ys.emplace_back(local);
tmp++;
}
}
set<int> nums;
for (int i = ; i < xs.size(); i++)
{
for (int j = ; j < ys.size(); j++)
{
int local = xs[i] + ys[j];
if (local > bound)
{
break;
}
else
{
nums.insert(local);
}
}
}
for (set<int>::iterator it = nums.begin(); it != nums.end(); it++)
{
ret.emplace_back(*it);
}
return ret;
}
};
其他：
国内第一code：
class Solution(object):
def powerfulIntegers(self, x, y, bound):
"""
:type x: int
:type y: int
:type bound: int
:rtype: List[int]
"""
if x > y:
x, y = y, x
ans = set()
for i in range():
for j in range():
if x ** i + y ** j <= bound:
ans.add(x ** i + y ** j)
return list(ans)
1<=x,y<=100,0<=bound<=10^6，由于x,y取整数，所以除1外最小的2^20=1048576>10^6，20*20两层循环即可，甚至可以在外层判断如果过大直接结束，内层也是如果大于bound可以直接结束。
如下：
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
vector<int> ret;
if (x < y)
{
int tmp = x;
x = y;
y = tmp;
}
for(int i=;i<;i++)
{
int tmp = pow(x, i);
if (tmp >= bound)
{
break;
}
for (int j = ; j < ; j++)
{
int tmpans =tmp+ pow(y, j);
if (tmpans > bound)
{
break;
}
else
{
if (count(ret.begin(), ret.end(), tmpans) == )
{
ret.emplace_back(tmpans);
}
}
}
}
return ret;
}
};
4ms战胜98.13% cpp code。
用时最短code：
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
set<int> S;
int i, tx, ty;
for (tx = ; tx <= bound; tx *= x) {
for (ty = ; ty <= bound; ty *= y) {
if (tx + ty > bound)
break;
S.insert(tx + ty);
if (y == )
break;
}
if (x == )
break;
}
auto it = S.begin();
vector<int> ans;
while (it != S.end()) {
ans.push_back(*it);
it++;
}
return ans;
}
};
大概逻辑差不多，用set去重，计算幂的和，对比bound，对于1只用一次跳过循环
最新文章
- 有趣的 CSS 像素艺术
- RMAN异机恢复快速参考
- Extjs4.0以上版本 Ext.Ajax.request请求的返回问题
- tinyhttpd源码分析
- 统计Apache或Nginx访问日志里的独立IP访问数量的Shell
- php lock_sh共享锁 与 lock_ex排他锁
- Oracle学习笔记2
- html学习：插入优酷视频
- 以一则LUA实例说明敏捷开发中“分离构造和使用”原则
- javascript百度地图添加一个普通标注点（2014-3-8 记）
- 避免jQuery名字冲突--noConflict()方法
- Makefile简介
- source insight 的使用
- 【转】 怎么刷入BOOT.IMG(刷机后开机卡在第一屏的童鞋请注意)-------不错不错
- Android查缺补漏（View篇）--自定义 View 中 wrap_content 无效的解决方案
- 如何遍历 Windows 摄像头设备？
- zTree：一个依靠 jQuery 实现的多功能 “树插件”
- JSAP107
- windows如何简单安装mongodb
- js把mysql传过来的时间格式化为：0000-00-00 00:00:00