0

Leetcode 问题：有效完美平方

我的回答是：

public class Solution {
    public boolean isPerfectSquare(int num) {
        int l = 0;
        int r = (num>>1)+1;
        while(l<=r) {
            int mid = (l+r)>>1;
            long temp = mid*mid;// why long
            if( temp == num) return true;
            else if( temp< num) l = mid+1;
            else r=mid-1;
        }
        return false;
    }
}

此回答时限超过（输入 2^31-1 时）。但是如果我将 l,r,mid 更改为 long（不是 int），它就可以工作。为什么？ 谢谢

4

1 回答 1

2

如果你调试你的代码，你可以看到哪里出了问题。“调试”的一种方法是插入语句，因此在赋值print之后插入以下代码：temp

System.out.printf("l=%1$08x=%1$-10d r=%2$08x=%2$-10d mid=%3$08x=%3$-10d temp=%4$016x=%4$d%n", l, r, mid, temp);
if (temp < 0)
    throw new IllegalStateException();

这将以十六进制和十进制打印 4 个值l、r、mid和temp，对齐以便于比较。当发生明显的内部错误时，插入该if语句以结束循环，并将触发。

调用时输出isPerfectSquare(Integer.MAX_VALUE)：

l=00000000=0          r=40000000=1073741824 mid=20000000=536870912  temp=0000000000000000=0
l=20000001=536870913  r=40000000=1073741824 mid=30000000=805306368  temp=0000000000000000=0
l=30000001=805306369  r=40000000=1073741824 mid=38000000=939524096  temp=0000000000000000=0
l=38000001=939524097  r=40000000=1073741824 mid=3c000000=1006632960 temp=0000000000000000=0
l=3c000001=1006632961 r=40000000=1073741824 mid=3e000000=1040187392 temp=0000000000000000=0
l=3e000001=1040187393 r=40000000=1073741824 mid=3f000000=1056964608 temp=0000000000000000=0
l=3f000001=1056964609 r=40000000=1073741824 mid=3f800000=1065353216 temp=0000000000000000=0
l=3f800001=1065353217 r=40000000=1073741824 mid=3fc00000=1069547520 temp=0000000000000000=0
l=3fc00001=1069547521 r=40000000=1073741824 mid=3fe00000=1071644672 temp=0000000000000000=0
l=3fe00001=1071644673 r=40000000=1073741824 mid=3ff00000=1072693248 temp=0000000000000000=0
l=3ff00001=1072693249 r=40000000=1073741824 mid=3ff80000=1073217536 temp=0000000000000000=0
l=3ff80001=1073217537 r=40000000=1073741824 mid=3ffc0000=1073479680 temp=0000000000000000=0
l=3ffc0001=1073479681 r=40000000=1073741824 mid=3ffe0000=1073610752 temp=0000000000000000=0
l=3ffe0001=1073610753 r=40000000=1073741824 mid=3fff0000=1073676288 temp=0000000000000000=0
l=3fff0001=1073676289 r=40000000=1073741824 mid=3fff8000=1073709056 temp=0000000040000000=1073741824
l=3fff8001=1073709057 r=40000000=1073741824 mid=3fffc000=1073725440 temp=0000000010000000=268435456
l=3fffc001=1073725441 r=40000000=1073741824 mid=3fffe000=1073733632 temp=0000000004000000=67108864
l=3fffe001=1073733633 r=40000000=1073741824 mid=3ffff000=1073737728 temp=0000000001000000=16777216
l=3ffff001=1073737729 r=40000000=1073741824 mid=3ffff800=1073739776 temp=0000000000400000=4194304
l=3ffff801=1073739777 r=40000000=1073741824 mid=3ffffc00=1073740800 temp=0000000000100000=1048576
l=3ffffc01=1073740801 r=40000000=1073741824 mid=3ffffe00=1073741312 temp=0000000000040000=262144
l=3ffffe01=1073741313 r=40000000=1073741824 mid=3fffff00=1073741568 temp=0000000000010000=65536
l=3fffff01=1073741569 r=40000000=1073741824 mid=3fffff80=1073741696 temp=0000000000004000=16384
l=3fffff81=1073741697 r=40000000=1073741824 mid=3fffffc0=1073741760 temp=0000000000001000=4096
l=3fffffc1=1073741761 r=40000000=1073741824 mid=3fffffe0=1073741792 temp=0000000000000400=1024
l=3fffffe1=1073741793 r=40000000=1073741824 mid=3ffffff0=1073741808 temp=0000000000000100=256
l=3ffffff1=1073741809 r=40000000=1073741824 mid=3ffffff8=1073741816 temp=0000000000000040=64
l=3ffffff9=1073741817 r=40000000=1073741824 mid=3ffffffc=1073741820 temp=0000000000000010=16
l=3ffffffd=1073741821 r=40000000=1073741824 mid=3ffffffe=1073741822 temp=0000000000000004=4
l=3fffffff=1073741823 r=40000000=1073741824 mid=3fffffff=1073741823 temp=ffffffff80000001=-2147483647
Exception in thread "main" java.lang.IllegalStateException
    at Test.isPerfectSquare(Test.java:14)
    at Test.main(Test.java:4)

如您所见，您的问题已经出现在第一次迭代中，其中temp计算为0.

这是由平方时的数字溢出引起的0x2000_0000。应该是0x0400_0000_0000_0000，但这是0因为乘法是使用int数学完成的。

long通过将其中至少一个转换为 来更改数学long，例如将行更改为long temp = (long)mid * mid;。

通过该更改，您的调试输出变为：

l=00000000=0          r=40000000=1073741824 mid=20000000=536870912  temp=0400000000000000=288230376151711744
l=00000000=0          r=1fffffff=536870911  mid=0fffffff=268435455  temp=00ffffffe0000001=72057593501057025
l=00000000=0          r=0ffffffe=268435454  mid=07ffffff=134217727  temp=003ffffff0000001=18014398241046529
l=00000000=0          r=07fffffe=134217726  mid=03ffffff=67108863   temp=000ffffff8000001=4503599493152769
l=00000000=0          r=03fffffe=67108862   mid=01ffffff=33554431   temp=0003fffffc000001=1125899839733761
l=00000000=0          r=01fffffe=33554430   mid=00ffffff=16777215   temp=0000fffffe000001=281474943156225
l=00000000=0          r=00fffffe=16777214   mid=007fffff=8388607    temp=00003fffff000001=70368727400449
l=00000000=0          r=007ffffe=8388606    mid=003fffff=4194303    temp=00000fffff800001=17592177655809
l=00000000=0          r=003ffffe=4194302    mid=001fffff=2097151    temp=000003ffffc00001=4398042316801
l=00000000=0          r=001ffffe=2097150    mid=000fffff=1048575    temp=000000ffffe00001=1099509530625
l=00000000=0          r=000ffffe=1048574    mid=0007ffff=524287     temp=0000003ffff00001=274876858369
l=00000000=0          r=0007fffe=524286     mid=0003ffff=262143     temp=0000000ffff80001=68718952449
l=00000000=0          r=0003fffe=262142     mid=0001ffff=131071     temp=00000003fffc0001=17179607041
l=00000000=0          r=0001fffe=131070     mid=0000ffff=65535      temp=00000000fffe0001=4294836225
l=00000000=0          r=0000fffe=65534      mid=00007fff=32767      temp=000000003fff0001=1073676289
l=00008000=32768      r=0000fffe=65534      mid=0000bfff=49151      temp=000000008ffe8001=2415820801
l=00008000=32768      r=0000bffe=49150      mid=00009fff=40959      temp=0000000063fec001=1677639681
l=0000a000=40960      r=0000bffe=49150      mid=0000afff=45055      temp=0000000078fea001=2029953025
l=0000b000=45056      r=0000bffe=49150      mid=0000b7ff=47103      temp=00000000843e9001=2218692609
l=0000b000=45056      r=0000b7fe=47102      mid=0000b3ff=46079      temp=000000007e8e9801=2123274241
l=0000b400=46080      r=0000b7fe=47102      mid=0000b5ff=46591      temp=0000000081629401=2170721281
l=0000b400=46080      r=0000b5fe=46590      mid=0000b4ff=46335      temp=000000007ff79601=2146932225
l=0000b500=46336      r=0000b5fe=46590      mid=0000b57f=46463      temp=0000000080acd501=2158810369
l=0000b500=46336      r=0000b57e=46462      mid=0000b53f=46399      temp=0000000080522581=2152867201
l=0000b500=46336      r=0000b53e=46398      mid=0000b51f=46367      temp=000000008024d9c1=2149898689
l=0000b500=46336      r=0000b51e=46366      mid=0000b50f=46351      temp=00000000800e36e1=2148415201
l=0000b500=46336      r=0000b50e=46350      mid=0000b507=46343      temp=000000008002e631=2147673649
l=0000b500=46336      r=0000b506=46342      mid=0000b503=46339      temp=000000007ffd3e09=2147302921
l=0000b504=46340      r=0000b506=46342      mid=0000b505=46341      temp=0000000080001219=2147488281
l=0000b504=46340      r=0000b504=46340      mid=0000b504=46340      temp=000000007ffea810=2147395600
false
于 2016-06-26T18:02:01.720 回答