warum lang, nicht int sonst begrenzt Zeit überschreiten

Question

Leetcode Problem: valid perfect square

Meine Antwort ist:

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; 
    } 
} 

Diese Antwort Zeitgrenze überschreitet (wenn Eingang 2^31-1). aber wenn ich l, r, mittel bis lang (nicht int) ändere, funktioniert es. Warum? Dank

Answer 1

Wenn Sie debuggen Ihren Code, können Sie sehen, was schief geht. Ein Weg, um "debug" ist print Anweisungen einzufügen, so legen Sie den folgenden Code direkt nach der temp Zuordnung:

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(); 

Dies druckt die 4 Werte l, r, mid und temp sowohl in hex und dezimal, für einfachen Vergleich ausgerichtet. Die Anweisung if wird eingefügt, um die Schleife zu beenden, wenn ein interner Fehler offensichtlich aufgetreten ist, und es wird ausgelöst.

Ausgabe, wenn isPerfectSquare(Integer.MAX_VALUE) Aufruf:

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) 

Wie Sie sehen können, Ihr Problem tritt bereits in der ersten Iteration, wo temp-0 berechnet wird.

Ursache ist der numerische Überlauf beim Quadrieren 0x2000_0000. Es sollte 0x0400_0000_0000_0000 sein, aber es ist 0, weil die Multiplikation mit int math erfolgt.

Schalte auf long math durch mindestens einen von ihnen zu long Gießen, z.B. Ändern Sie die Linie zu long temp = (long)mid * mid;.

Mit dieser Änderung Ihrer Debug-Ausgabe wird:

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 

Answer 2

Ganzzahlen sind in einer Gruppe namens Primitive. Aus diesem Grund können Ganzzahlen in Java keine Dezimalzahlen haben und sind begrenzt, was bedeutet, dass sie nicht über bestimmte Zahlen hinausgehen können. Andernfalls erhalten Sie entweder das, was Sie erhalten haben, oder einen Stapelüberlauffehler. Um dies zu beheben, können Sie die Variable nicht als Integer festlegen, sondern als Double oder Long. Longs werden normalerweise verwendet, wenn Sie sehr große oder sehr kleine Zahlen speichern müssen. Wenn Sie Zahlen wie 2.5 oder 7.78 verwenden müssen, werden normalerweise doppelte Werte verwendet. Diese Zahlen sind nicht sehr klein oder sehr groß, aber sie sind Dezimalzahlen, was bedeutet, dass sie nicht als ganze Zahlen gespeichert werden können. Hoffe das hat geholfen!