Đề bài:
Cho hai số nguyên dividend và divisor, chia hai số nguyên mà không sử dụng các phép nhân, chia và lấy phần dư.
Phép chia nguyên này sẽ cắt giảm phần thập phân của nó. Ví dụ, 8.345 sẽ được cắt giảm thành 8 và -2.7335 sẽ được cắt giảm thành -2.
Trả về phần nguyên sau khi chia dividend cho divisor.
Lưu ý: Giả sử chúng ta đang làm việc trong một môi trường chỉ có thể lưu trữ các số nguyên trong khoảng số nguyên có dấu 32 bit: [-2^31, 2^31 – 1]. Đối với bài toán này, nếu phần nguyên là nghiêm ngặt lớn hơn 2^31 – 1, thì trả về 2^31 – 1, và nếu phần nguyên nhỏ hơn nghiêm ngặt hơn -2^31, thì trả về -2^31.
Ví dụ 1:
Input: dividend = 10, divisor = 3 Output: 3 Giải thích: 10/3 = 3.33333.. nhưng bị cắt giảm thành 3.
Ví dụ 2:
Input: dividend = 7, divisor = -3 Output: -2 Giải thích: 7/-3 = -2.33333.. nhưng bị cắt giảm thành -2.
Ràng buộc:
- -2^31 <= dividend, divisor <= 2^31 – 1
- divisor != 0
Giải thích thuật toán bằng C++
class Solution {
public:
int divide(int dividend, int divisor) {
// -2^{31} / -1 = 2^31 -> overflow so return 2^31 - 1
if (dividend == INT_MIN && divisor == -1)
return INT_MAX;
const int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
long ans = 0;
long dvd = labs(dividend);
long dvs = labs(divisor);
while (dvd >= dvs) {
long k = 1;
while (k * 2 * dvs <= dvd)
k *= 2;
dvd -= k * dvs;
ans += k;
}
return sign * ans;
}
};
Đây là một phương thức trong lớp `Solution` được sử dụng để thực hiện phép chia hai số nguyên `dividend` và `divisor` mà không sử dụng các phép nhân, chia và lấy phần dư.
Dưới đây là cách thuật toán hoạt động:
1. Kiểm tra trường hợp đặc biệt khi `dividend` là -2^31 và `divisor` là -1. Khi thực hiện phép chia này, sẽ xảy ra tràn số (overflow), vì vậy trả về giá trị INT_MAX (2^31 – 1).
2. Xác định dấu của kết quả phép chia bằng cách kiểm tra dấu của `dividend` và `divisor`. Nếu dấu khác nhau, kết quả sẽ có dấu âm, ngược lại sẽ có dấu dương. Gán giá trị `sign` tương ứng (-1 hoặc 1).
3. Khởi tạo biến `ans` với giá trị ban đầu là 0, đại diện cho phần nguyên của kết quả phép chia.
4. Sử dụng hàm `labs` để lấy giá trị tuyệt đối của `dividend` và `divisor`, gán cho biến `dvd` và `dvs`. Điều này đảm bảo rằng chúng ta đang làm việc với các giá trị không âm.
5. Thực hiện vòng lặp while cho đến khi `dvd` lớn hơn hoặc bằng `dvs`. Trong mỗi lần lặp, tiến hành tìm giá trị `k`, lần lượt nhân `k` với 2 và `dvs`, cho đến khi `k * 2 * dvs` lớn hơn `dvd`. Điều này giúp chúng ta tìm được giá trị lớn nhất của `k` sao cho `k * dvs` vẫn nhỏ hơn hoặc bằng `dvd`.
6. Giảm giá trị `dvd` đi `k * dvs` và tăng giá trị `ans` lên `k`. Điều này đại diện cho việc trừ đi một phần của `dvd` và cộng thêm một phần vào `ans`.
7. Trả về kết quả của phép chia, nhân với giá trị `sign` để đảm bảo đúng dấu.
Thuật toán trên sử dụng phép chia theo phương pháp tìm kiếm nhị phân để tìm ra phần nguyên của kết quả phép chia. Nó lặp đi lặp lại việc tìm giá trị `k` lớn nhất mà `k * dvs` vẫn nhỏ hơn hoặc bằng `dvd`, sau đó trừ `k * dvs` từ `dvd` và cộng `k` vào `ans`. Quá trình này tiếp tục cho đến khi `dvd` không còn lớn hơn hoặc bằng `dvs`.
Giải thích thuật toán bằng Java
class Solution {
public int divide(long dividend, long divisor) {
// -2^{31} / -1 = 2^31 will overflow, so return 2^31 - 1.
if (dividend == Integer.MIN_VALUE && divisor == -1)
return Integer.MAX_VALUE;
final int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
long ans = 0;
long dvd = Math.abs(dividend);
long dvs = Math.abs(divisor);
while (dvd >= dvs) {
long k = 1;
while (k * 2 * dvs <= dvd)
k *= 2;
dvd -= k * dvs;
ans += k;
}
return sign * (int) ans;
}
}
Giải thích thuật toán bằng Python
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
# -2^{31} / -1 = 2^31 will overflow, so return 2^31 - 1.
if dividend == -2**31 and divisor == -1:
return 2**31 - 1
sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
ans = 0
dvd = abs(dividend)
dvs = abs(divisor)
while dvd >= dvs:
k = 1
while k * 2 * dvs <= dvd:
k <<= 1
dvd -= k * dvs
ans += k
return sign * ans
0 / 5 - (0 Đánh Giá)