Bài vỡ lòng trong khi học lập trình Java đó là kiểu integer nguyên thuỷ sẽ có
int
(32 bit) vàlong
(64 bit). Kiểulong
sẽ mô tả được số lớn hơn. Vâng ai cũng biết cả. Nhưng khi lập trình vẫn mắc phải lỗi sơ đẳng.
Ví dụ bài Leet Code số 69: Sqrt(x).
Yêu cầu của bài này
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.
Bạn không được sử dụng bất kỳ hàm hoặc toán tử lũy thừa 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, 2 được trả về.
Cách làm
Hướng giải của bài này là sử dụng Binary Search: lấy điểm giữa mid
của dải số từ lo
đến hi
nếu:
mid * mid > x
thìhi = mid
mid *mid < x
thìlow = mid +1
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;
}
}
}
Bộ 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 x đủ lớn, hãy dùng long
Khi x là một số đủ lớn, đoạn code trên chạy không còn đúng nữa
assertThat(mySqrt(2147483647)).isEqualTo(46340);
Đoạn test trên sẽ trả về failed. Khi debug tôi thấy đoạn code này
int square_mid = mid * mid;
Khi mid
đủ lớn thì bình phương của nó sẽ vượt giới hạn lưu trữ số nguyên dương biến kiển int 32 bit là 2^31
(trừ đi một bit mô tả dấu âm hay dương). Lúc này mid * mid
trả về giá trị âm.
Vậy nguyên tắc trước khi 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ố
long square_mid = (long) mid * mid;
Code đầy đủ sau khi sửa lỗi
public int mySqrt(int x) {
int lo = 0, hi = x;
while (hi > lo) {
int mid = (hi + lo) / 2;
long square_mid = (long) mid * mid;
if (square_mid > x) {
hi = mid;
} else if (square_mid < x) {
lo = mid + 1;
} else {
return mid;
}
}
if ((long) lo * lo > x) {
return lo - 1;
} else {
return lo;
}
Bình luận