public class PowersOfTen {
public static boolean isPowerOfTen(long input) {
if (input % 10 != 0 || input == 0) {
return false;
}
if (input == 10) {
return true;
}
return isPowerOfTen(input/10);
}
public static void main(String[] args) {
System.out.println("1000: " + isPowerOfTen(1000));
System.out.println("4: " + isPowerOfTen(4));
System.out.println("0: " + isPowerOfTen(0));
System.out.println("10: " + isPowerOfTen(10));
System.out.println("100: " + isPowerOfTen(100));
}
}
#1 楼
为此,递归似乎很繁重。您可以使用几乎相同的逻辑,但有一个简单的循环: 10的倍数)和10的倍数(因为10的所有幂显然都大于1)。首先以小的微优化形式进行正面检查;然后进行正面检查。短路评估将避免执行不必要的除法运算来计算不需要的模量。如果两个条件都满足,则将整数除以10,然后重复该过程。对于任何10的幂,该值都将以1终止;如果传递了1本身,则无需执行
while
循环的主体即可这样做。 评论
\ $ \ begingroup \ $
使它变为while(输入> 9 ...可以避免对输入1到9(以及它们的10 ^ x倍数)进行一些多余的额外计算。
\ $ \ endgroup \ $
–杰夫Y
16年1月20日在17:33
\ $ \ begingroup \ $
@JeffY如何处理10的负幂?对于0.1或0.01等输入
\ $ \ endgroup \ $
– Paras
16年1月20日在18:31
\ $ \ begingroup \ $
参见:长输入。
\ $ \ endgroup \ $
–杰夫Y
16年1月20日在19:42
\ $ \ begingroup \ $
@ParasDPain输入为long,这是整数类型。分数值是不可能的。
\ $ \ endgroup \ $
–马克·里德(Mark Reed)
16年1月20日在19:44
\ $ \ begingroup \ $
我明白了,要求。
\ $ \ endgroup \ $
– Paras
16年1月20日在19:47
#2 楼
您也可以只列出它们,因为long数据类型的范围并不多。OP中代码的优点是简单,清晰和正确。
缺点是有些人可能认为它很冗长。此外,(潜在的)微优化可能是将比较分为多个较小的组,并在通过非幂10的情况下执行二进制搜索以减少比较的次数。
public static boolean isPowerOfTen(long input) {
return
input == 1L
|| input == 10L
|| input == 100L
|| input == 1000L
|| input == 10000L
|| input == 100000L
|| input == 1000000L
|| input == 10000000L
|| input == 100000000L
|| input == 1000000000L
|| input == 10000000000L
|| input == 100000000000L
|| input == 1000000000000L
|| input == 10000000000000L
|| input == 100000000000000L
|| input == 1000000000000000L
|| input == 10000000000000000L
|| input == 100000000000000000L
|| input == 1000000000000000000L;
}
评论
\ $ \ begingroup \ $
的确如此,或者将它们放在静态(或简洁的环境中)中,以测试其成员资格。
\ $ \ endgroup \ $
– Erick Wong
16年1月19日在19:27
\ $ \ begingroup \ $
排序帽子版本。
\ $ \ endgroup \ $
–疯狂
16年1月20日在10:33
\ $ \ begingroup \ $
也有点慢,因为所有ors将使CPU必须多次分支,但是..无论如何,这都是Java,所以无论如何它都会很慢。
\ $ \ endgroup \ $
–宏线程
16年1月21日在4:36
\ $ \ begingroup \ $
@FilipHaglund-是的。它是否需要帮助还是要进行测试-即使它确实有所帮助,除非这是代码中的关键路径,清晰度的损失也可能无法弥补。
\ $ \ endgroup \ $
–马丁·史密斯
16年1月21日在9:38
\ $ \ begingroup \ $
此答案是此代码高尔夫球问题的基础
\ $ \ endgroup \ $
–已删除
16-2-3在12:44
#3 楼
我认为您的代码不正确,因为我希望isPowerOfTen(1)
为true
。评论
\ $ \ begingroup \ $
你说得对,很好接。
\ $ \ endgroup \ $
– jcm
16年1月19日在6:14
\ $ \ begingroup \ $
只需将if(input == 10)更改为if(input == 1),然后将if放在第一位。
\ $ \ endgroup \ $
–有资格
16年1月19日在8:25
\ $ \ begingroup \ $
因此,“是否有更好的方法来检查数字是否为10的幂?”
\ $ \ endgroup \ $
–马丁·史密斯
16年1月20日在22:58
\ $ \ begingroup \ $
@MartinSmith这不仅仅是简单地重写解决方案并说“你走了”,这更是一个有效的回顾点。
\ $ \ endgroup \ $
– Quill
16年1月20日在23:04
#4 楼
数学替代方法有
Math.log10()
:我已经更新了上面的答案,以处理1e14
以上的值,这似乎会失去精度。单元测试转换为单元测试的形式例如,使用TestNG:
public static boolean isPowerOfTen(long value) {
// updated answer - check for precision in if statement
if (value >= 1e14) {
try {
return isPowerOfTen(BigDecimal.valueOf(value)
.divide(BigDecimal.valueOf(1e14)).longValueExact());
} catch (ArithmeticException e) {
return false;
}
}
double power = Math.log10(value);
return Double.isFinite(power) && Math.round(power) == power;
}
评论
\ $ \ begingroup \ $
您是否针对精度问题对此进行了测试? 10 ^ 18 + 1的log10将非常接近18,可能比以双精度忠实表示的结果更接近。
\ $ \ endgroup \ $
– Erick Wong
16年1月19日,下午6:51
\ $ \ begingroup \ $
@ErickWong完全有效。 :)更新了我的答案。
\ $ \ endgroup \ $
– h.j.k.
16年1月19日在7:26
\ $ \ begingroup \ $
我不喜欢这种解决方案,因为1)确保自己正确是太难了。浮点数舍入很棘手。 2)使用异常作为核心逻辑的一部分。
\ $ \ endgroup \ $
– CodesInChaos
16年1月19日在14:52
\ $ \ begingroup \ $
@CodesInChaos我个人认为,我的方法的主要问题始于if(值> = 14)。如果可以挥之不去,我认为原始方法是可以的。因此,“注意精度”强调...;)
\ $ \ endgroup \ $
– h.j.k.
16年1月19日在15:40
\ $ \ begingroup \ $
@ h.j.k。您想移开的部分对于方法的正确性至关重要。从根本上讲,问题在于根除像log10这样的函数,其正确性仅近似于需要精确性的问题。
\ $ \ endgroup \ $
– Erick Wong
16年1月19日在19:14
#5 楼
按照马丁·史密斯(Martin Smith)的回答,可以将所有10的幂次存储在一个数组中,然后进行二进制搜索:对于这种小型数据集,效率远不如Martin的效率(在我的计算机上慢2.5倍),但对大型数据集的伸缩性要好得多。另一方面,如果您需要极高的速度,则可以基于5gon12eder的注释的算法可能值得使用。它会打开输入的低位(您不能长时间打开),如果遇到击中,它将执行线性搜索。在前十亿个正整数上进行计算:
线性搜索(马丁史密斯):2970毫秒
二进制搜索:6908毫秒
打开哈希然后进行线性搜索:1519毫秒
评论
\ $ \ begingroup \ $
我认为switch语句将是这里最快(最易读?)的解决方案。
\ $ \ endgroup \ $
– 5gon12eder
16年1月20日在19:50
\ $ \ begingroup \ $
@ 5gon12eder Java不支持启用多头。
\ $ \ endgroup \ $
–恢复莫妮卡
16年1月20日在19:54
\ $ \ begingroup \ $
Ups,我忘记了……您可以将long的位“散列”为一个int并将其切换为int,但这并不那么明显。
\ $ \ endgroup \ $
– 5gon12eder
16 Jan 20 '20:00
\ $ \ begingroup \ $
@ 5gon12eder如果您进行哈希处理,则会得到误报。您可以哈希,然后如果匹配,则运行精确算法。那会更快,我将相应地更新此答案。
\ $ \ endgroup \ $
–恢复莫妮卡
16年1月20日在21:00
\ $ \ begingroup \ $
@Supuhstar几乎可以肯定,这比二进制搜索或切换要慢,直到表变得很大为止。
\ $ \ endgroup \ $
–恢复莫妮卡
17年4月9日在18:14
#6 楼
迭代版本此建议类似于@ 200_success的答案。如果您喜欢这种事情,可以将其压缩为for循环:)。兴趣点:
没有递归。递归可以生成精美的代码,但与迭代函数相比,那些额外的函数调用有时会带来明显的性能损失。
使用乘法而不是除法(应该更快,但我对此没有权限) />无需特殊处理0、1或负的
input
数字。但是需要检查基础。可以使用除10以外的其他基础。
因为有时Long不够长:)
public static boolean isPowerOf(long input, long base) {
if (base < 2) throw new IllegalArgumentException("base must be 2 or larger");
//find the biggest number that is safe to multiply base with without getting integer oveflow
long safeMultiplier = Long.MAX_VALUE / base;
long x = 1;
while (x < input && x <= safeMultiplier) {
x *= base;
}
return x == input;
}
递归版本
递归版本仍使用乘法而不是除法。将递归调用放在函数的最后(就像您也这样做),是对可以执行尾部调用优化的语言的致敬(http://c2.com/cgi/wiki? Wiki / Tail_call)。我不认为Java会这样做。
public static boolean isPowerOf(BigInteger input, BigInteger base) {
if (base.compareTo(BigInteger.ONE) != 1) {
throw new IllegalArgumentException("base must be 2 or larger");
}
BigInteger x = BigInteger.ONE;
int comparison;
while ((comparison = x.compareTo(input)) == -1) {
x = x.multiply(base);
}
return comparison == 0;
}
编辑:
根据@ErickWong的建议
添加了有效基数检查(> 1)
添加了BigInteger版本
修复了错误的溢出检查
评论
\ $ \ begingroup \ $
如果输入相对于MAX_INT / base太大,则迭代版本将陷入无限循环。您是否在大约MAX_INT的2/3倍的输入上对此进行了测试?
\ $ \ endgroup \ $
– Erick Wong
16年1月19日在19:22
\ $ \ begingroup \ $
@ErickWong Wong你是正确的。由于Java似乎在整数溢出上默默地回绕,它将进入无限循环。接得好。我添加了溢出检查。我喜欢我对代码审查帖子的回答刚刚得到审查。 :)
\ $ \ endgroup \ $
–最大
16 Jan 20'8:51
\ $ \ begingroup \ $
不幸的是,溢出检查还不够。当base == 2时很好,但是对于较大的base,完全有可能10 * x溢出到正值。一种检查溢出的更安全方法是在for循环外花费一个除法来找到可以乘以base的最大值。
\ $ \ endgroup \ $
– Erick Wong
16年1月20日在18:30
#7 楼
没有除法,没有模,没有递归?我们开始:public static boolean power10(int n) {
int max_power10 = 100000; //whatever you can accept given your type
int i = 1;
while ( i != n && i != max_power10) i *= 10;
return i == n;
}
改进:
public static boolean power10(int n) {
int max_power10 = 100000; //whatever you can accept given your type
if (n > max_power10 ) return false;
int i = 1;
while (i < n) i *= 10;
return i == n;
}
评论
\ $ \ begingroup \ $
为什么不那么简单(i
– FranMowinckel
16年3月3日在22:06
\ $ \ begingroup \ $
@FranMowinckel,因为它可能导致溢出。考虑一下n是最大int值的情况。
\ $ \ endgroup \ $
– DarioP
16年4月4日在7:45
\ $ \ begingroup \ $
来吧,这只是一个极限情况,您可以在之前检查(即(n> max_power10)是否返回false)
\ $ \ endgroup \ $
– FranMowinckel
16-2-4在8:31
#8 楼
IMO会更干净,因为:public static boolean isPowerOfTen(long input) {
if (input <= 0 ) {
// powers of 10 can't be 0 or negative
return false;
}
// don't have to worry about negative powers since long input
// doesn't hold fractions
for (int pow = 0; pow <= Math.log10(Long.MAX_VALUE); ++pow) {
if (input == (long)Math.pow(10, pow)) {
return true;
}
}
return false;
}
Math.log10(Long.MAX_VALUE)将产生最大10的幂,该幂将适合较长的地板,是(被隐式转换为截断)18。 Java没有Math.logb方法,但请回想一下:logb(x)= logc(x)/ logc(b)。因此logb(Long.MAX_VALUE)= Math.log(Long.MAX_VALUE)/ Math.log(b):
public static boolean isPowerOf(long input, int base) {
if (input <= 0 ) {
return false;
}
for (int pow = 0; pow <= Math.log(Long.MAX_VALUE) / Math.log(base); ++pow) {
if (input == Math.floor(Math.pow(base, pow))) {
return true;
}
}
return false;
}
但是我们也可以使用小数学可以直接找到幂并检查它是否是整数:
public static boolean isPowerOf(long input, int base) {
if (input == 0) {
return false;
}
// use Math.abs since if the argument is NaN or less than zero to Math.log,
// then the result is NaN. This makes it work for negative inputs and bases
Double power = Math.log(Math.abs(input)) / Math.log(Math.abs(base));
// power might have lost precision, so I'm trying floor and ceiling. These are integers so if either yields the input, return true
return (input == (long)Math.pow(base, Math.floor(power)) ||
input == (long)Math.pow(base, Math.ceil(power)));
}
评论
\ $ \ begingroup \ $
1)对于整数问题,我会避免使用浮点数,这会使进行推理变得非常困难。即使碰巧是正确的,也需要太多的思考才能确保它是正确的。 2)您的代码显然是错误的,因为Math.pow返回一个不能代表所有有效long的双精度型。
\ $ \ endgroup \ $
– CodesInChaos
16年1月19日在14:25
\ $ \ begingroup \ $
3)您可以使用BigInteger.pow代替math.pow。 4)将幂四舍五入为整数将比测试floor和ceil更简单。
\ $ \ endgroup \ $
– CodesInChaos
16 Jan 19 '14:53
#9 楼
这很有趣,但是这个非常基本的解决方案呢?:String.valueOf(x).matches("^10*$")
它对于使用
long
的BigDecimal
和toPlainString()
也应适用。顺便说一句,我知道这不是很高的性能:P。
出于好奇,二进制表示法中的10的幂都以其自身结尾:
1 -> b'1'
10 -> b'x10'
100 -> b'x100'
1000 -> b'x1000'
...
(其中x是'1'和'0'的序列)
评论
\ $ \ begingroup \ $
@WashingtonGuedes对我感到羞耻!谢谢!多么愚蠢的错误
\ $ \ endgroup \ $
– FranMowinckel
16-2-3在11:11
\ $ \ begingroup \ $
无论如何+1 ..我也不必三思而后行...我个人想推断正则表达式的目的
\ $ \ endgroup \ $
–已删除
16-2-3在11:14
#10 楼
迭代比递归更有效。input == 1
也应算作10
的幂。public static boolean isPowerOfTen(long input) {
while (input > 1) {
if (input % 10 != 0)
return false;
input = input / 10;
}
if (input == 1) {
return true;
}
return false;
}
甚至更短的版本(由Landei建议) –谢谢!):
public static boolean isPowerOfTen(long input) {
while (input > 1) {
if (input % 10 != 0)
return false;
input /= 10;
}
return input == 1;
}
评论
\ $ \ begingroup \ $
当我看到这样的代码时,我总是感到困惑。为什么要最后一个?为什么不简单地返回输入== 1?
\ $ \ endgroup \ $
–兰台
16年1月19日在15:07
\ $ \ begingroup \ $
@Landei好吧,我也是。但是我在这里看到过如此多次的代码,以至于我开始相信这是Java程序员社区中的首选样式。现在已更正。
\ $ \ endgroup \ $
–CiaPan
16年1月19日在21:18
\ $ \ begingroup \ $
@Landei,其意图更加明确
\ $ \ endgroup \ $
– Ben Leggiero
17年4月9日在19:13
\ $ \ begingroup \ $
@Supuhstar您的大脑需要处理四行而不是一条,存在分支,并且该方法具有两个出口点而不是一个。这可能是“更明确的”,但显然难以理解。
\ $ \ endgroup \ $
–兰台
17年4月10日在7:56
\ $ \ begingroup \ $
@Landei的四行更简单,用英语更自然地阅读,而不是一条简洁的行在数学上更易读。无论如何,这不是这个地方。如果您想继续进行讨论,请随时通过Supuhstar0@gmail.com给我发送电子邮件。
\ $ \ endgroup \ $
– Ben Leggiero
17-4-10在10:17
#11 楼
如果我们要避免CPU分支,这是一个解决方案,这对于具有广泛指令流水线的CPU的C或C ++等编译语言来说将是不错的选择。它计算所有非零和以10为底的整数。想法是:当且仅当不存在大于1且正好为1的整数时,我们才有10的幂。 br />
int ispow10(int aInput){
int lCntO = 0, lCnt1 = 0, lTmp = 0, i = 0;
for( i=0 ;i < 10; i++, aInput /= 10 ){
lTmp = aInput % 10;
lCntO += (lTmp > 1);
lCnt1 += (lTmp == 1);
}
return (lCntO == 0)&(lCnt1==1);
}
#12 楼
我知道这可能不是最好的选择,但是我总是从人的角度解决数学上的简单问题,而且还没有人建议在这种情况下研究数字的写法:boolean isPowerOfTen(int n) {
char[] digits = (n+"").toCharArray();
if (digits[0] != '1') return false;
for (int i = 1; i<digits.length; i++) {
if (digits[i] != '0') return false;
}
return true;
}
您可以轻松地将其扩展为负数(0.000001),并且尽管性能较差,但可以说它比其他方法更易读和易用。
评论
@TomFenech如果输入是整数,则不能为10的负幂。@ErickWong这是我问的原因之一;我指的是像0.1这样的数字,显然这将需要不同的实现。
@TomFenech打开大量蠕虫。请记住,浮点类型也不能完全代表10的负幂。
1是10的幂,因为10到0的幂是1。此函数为1返回false。
主持人对审稿人的注释:是的,有很多不同的方法可以解决此问题。但是,这是“代码审查”,答案必须与问题中的代码有关。如果您提出一个独立的解决方案,则还需要包括一些理由。