Bài vỡ lòng khi học lập trình Java đó là kiểu nguyên thủy sẽ có int (32 bit) và long (64 bit). Kiểu long sẽ mô tả được số lượng lớn hơn. Vâng ai cũng biết cả. Nhưng khi lập trình vẫn truy vấn phải lỗi sơ đẳng
Ví dụ bài Leet Code number 69. bình phương(x)
Request of this post
Cho một số nguyên không âm x, trả về căn bậc hai của x được làm tròn xuống số nguyên gần nhất. Số nguyên được trả về cũng không được âm thanh
Bạn không thể sử dụng bất kỳ hàm hoặc thuật toán tích lũy tích hợp nào
Ví dụ. không sử dụng pow(x, 0,5) trong c++ hoặc x ** 0,5 trong python
Ví dụ 1
Đầu vào. x = 4
đầu ra. 2
Giải thích. Căn bậc hai của 4 là 2, vì vậy chúng tôi trả về 2
Ví dụ 2
Đầu vào. x = 8
đầu ra. 2
Giải thích. Căn bậc hai của 8 là 2,82842…, và vì chúng ta làm tròn nó xuống số nguyên gần nhất nên 2 được trả về
Cách làm
Hướng giải của bài này là sử dụng Tìm kiếm nhị phân. get point between mid of the strip number from @Test void test() { assertThat(mySqrt(4)).isEqualTo(2); assertThat(mySqrt(8)).isEqualTo(2); assertThat(mySqrt(9)).isEqualTo(3); assertThat(mySqrt(16)).isEqualTo(4); assertThat(mySqrt(80)).isEqualTo(8); assertThat(mySqrt(2)).isEqualTo(1); } 0 to @Test void test() { assertThat(mySqrt(4)).isEqualTo(2); assertThat(mySqrt(8)).isEqualTo(2); assertThat(mySqrt(9)).isEqualTo(3); assertThat(mySqrt(16)).isEqualTo(4); assertThat(mySqrt(80)).isEqualTo(8); assertThat(mySqrt(2)).isEqualTo(1); } 1 if
- @Test void test() { assertThat(mySqrt(4)).isEqualTo(2); assertThat(mySqrt(8)).isEqualTo(2); assertThat(mySqrt(9)).isEqualTo(3); assertThat(mySqrt(16)).isEqualTo(4); assertThat(mySqrt(80)).isEqualTo(8); assertThat(mySqrt(2)).isEqualTo(1); } 2 thì @Test void test() { assertThat(mySqrt(4)).isEqualTo(2); assertThat(mySqrt(8)).isEqualTo(2); assertThat(mySqrt(9)).isEqualTo(3); assertThat(mySqrt(16)).isEqualTo(4); assertThat(mySqrt(80)).isEqualTo(8); assertThat(mySqrt(2)).isEqualTo(1); } 3
- @Test void test() { assertThat(mySqrt(4)).isEqualTo(2); assertThat(mySqrt(8)).isEqualTo(2); assertThat(mySqrt(9)).isEqualTo(3); assertThat(mySqrt(16)).isEqualTo(4); assertThat(mySqrt(80)).isEqualTo(8); assertThat(mySqrt(2)).isEqualTo(1); } 4 thì @Test void test() { assertThat(mySqrt(4)).isEqualTo(2); assertThat(mySqrt(8)).isEqualTo(2); assertThat(mySqrt(9)).isEqualTo(3); assertThat(mySqrt(16)).isEqualTo(4); assertThat(mySqrt(80)).isEqualTo(8); assertThat(mySqrt(2)).isEqualTo(1); } 5
Code ban đầu của tôi như sau
class Solution { public int mySqrt(int x) { int lo = 0, hi = x; while (hi > lo) { int mid = (hi + lo) / 2; int square_mid = mid * mid; if (square_mid > x) { hi = mid; } else if (square_mid < x) { lo = mid + 1; } else { return mid; } } if (lo * lo > x) { return lo - 1; } else { return lo; } } }
Unit test chạy đúng hết
@Test void test() { assertThat(mySqrt(4)).isEqualTo(2); assertThat(mySqrt(8)).isEqualTo(2); assertThat(mySqrt(9)).isEqualTo(3); assertThat(mySqrt(16)).isEqualTo(4); assertThat(mySqrt(80)).isEqualTo(8); assertThat(mySqrt(2)).isEqualTo(1); }
Khi đủ lớn, hãy dùng long
Khi x là một số đủ lớn, đoạn mã trên chạy không còn đúng nữa
________số 8_______
Đoạn kiểm tra trên sẽ trả về không thành công. Khi gỡ lỗi, tôi thấy đoạn mã này
int square_mid = mid * mid;
Khi mid đủ lớn thì bình phương của nó sẽ giới hạn lưu trữ số nguyên dương biến kiển int 32 bit là @Test void test() { assertThat(mySqrt(4)).isEqualTo(2); assertThat(mySqrt(8)).isEqualTo(2); assertThat(mySqrt(9)).isEqualTo(3); assertThat(mySqrt(16)).isEqualTo(4); assertThat(mySqrt(80)).isEqualTo(8); assertThat(mySqrt(2)).isEqualTo(1); } 7 (ngoại trừ một bit mô tả dấu hiệu âm hay dương). Lúc này @Test void test() { assertThat(mySqrt(4)).isEqualTo(2); assertThat(mySqrt(8)).isEqualTo(2); assertThat(mySqrt(9)).isEqualTo(3); assertThat(mySqrt(16)).isEqualTo(4); assertThat(mySqrt(80)).isEqualTo(8); assertThat(mySqrt(2)).isEqualTo(1); } 8 trả về giá trị âm
Gorge integer before bình phương một số kiểu int hãy ép kiểu sang long để tránh tình trạng tràn số