Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/plus-one/
1. Mở đầu
Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.
2. Đề bài
Cho bạn một số nguyên được biểu diễn dưới dạng mảng số nguyên digits, với phần tử tại digits[i] chính là số thứ i của số đó. Các chữ số được sắp xếp theo thứ tự từ trái sang phải và không chứa số 0 đứng ở đầu.
Tăng số nguyên ban đầu thêm 1 và trả về kết quả là mảng chứa các chữ số của số nguyên sau khi đã thêm 1.
Điều kiện:
1 <= digits.length <= 100.0 <= digits[i] <= 9.- Mảng
digitskhông chứa số0đứng đầu mảng.
Ví dụ 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].
Ví dụ 2:
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].
Ví dụ 3:
Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].
3. Phân tích
Âu kê, bài này yêu cầu chúng ta cộng số nguyên ban đầu thêm 1 rồi trả về kết quả dưới dạng mảng các chữ số của số nguyên đó. Ban đầu chúng ta sẽ nghĩ đơn giản là ngay từ cái mảng digits ban đầu chỉ cần cộng thêm 1 rồi trả về luôn cũng được phải không ạ? Nhưng hãy nhìn vào ví dụ 3 ở trên, chúng ta thấy kích thước của mảng kết quả đã tăng thêm 1 do số nguyên là 9, cộng thêm 1 thành 10 tức là phải thêm một chữ số nữa.
Vậy thì chúng ta phải chia ra làm hai trường hợp:
Trường hợp đầu tiên là chữ số cuối cùng của mảng nhỏ hơn
9thì ta chỉ cần cộng thêm1, lúc này kích thước mảng không thay đổi, ta trả về mảng ấy luôn.Trường hợp thứ hai, chữ số cuối cùng là
9, khi ta cộng thêm1thì sẽ thành số tròn chục. Lúc này ta phải tạo mảng mới với kích thước tăng thêm1.Done! Hãy thử xem code chạy thế nào nhé!
4. Code chạy bằng cơm
- Hãy thử với trường hợp đầu tiên với ví dụ 1 nhé, chúng ta có mảng
digits = [1,2,3]. Ta trỏitới ngay vị trí cuối cùng của mảng chính làlength - 1:
Tại đây ta kiểm tra thấy i < 9 nên ta gán giá trị cho i = i + 1 luôn:
Rồi trả về kết quả là mảng sau khi đã thay đổi:
- Ok, với trường hợp thứ hai, số cuối cùng của mảng là
9thì chúng ta hãy thử với ví dụdigits = [9,9]:
Tại vị trí i = 1 ta thấy digits[i] = 9, mà 9 + 1 = 10 và tận cùng của 10 là 0 cho nên cứ khi nào gặp 9 thì ta đổi giá trị về 0:
Tại vị trí i = 0 ta lại thấy bằng 9, tương tự như bước trên ta thay 9 bằng số 0:
Lúc này con trỏ i đã chạy qua hết các chữ số trong digits mà vẫn không gặp số nào nhỏ hơn 9 để trả về mảng cũ, điều này có nghĩa là số nguyên này sau khi cộng thêm 1 đã thêm một chữ số nữa. Vậy thì ta sẽ tạo thêm một mảng mới với kích thước mảng digits.length + 1:
Mảng số nguyên khi mới tạo thì các giá trị mặc định sẽ là 0, vậy nên chúng ta chỉ cần gán giá trị 1 vào phần tử đầu tiên của mảng mới là xong:
Tại sao lại vậy? Tại vì 99 hay 999 hay thậm chí 9999 đều là trường hợp đặc biệt, mọi chữ số đều bằng 9, và khi ta thực hiện phép cộng thêm 1 vào từng chữ số cũng đều ra kết quả có chữ số cuối là 0. Khi con trỏ i chạy từ phải sang trái (hay từ cuối đến đầu mảng chứa các chữ số) mà không tìm thấy số nào nhỏ hơn 9 thì có nghĩa số này là trường hợp đặc biệt, kết quả trả về phải tăng thêm một chữ số.
Nói nhanh một trường hợp khác là digits = [8,9]. Ta thấy chữ số cuối thì bằng 9 nên ta chuyển về 0. Nhưng chữ số đầu thì là 8 lại nhỏ hơn 9, giống như trường hợp đầu tiên ta cộng thêm 1 thì bằng 9. Vậy ta trả về kết quả là [9,0] luôn:
5. Code bằng máy
Code của chúng ta như sau:
public static int[] plusOne(int[] digits) {
int length = digits.length;
for(int i = length-1; i >= 0 ; i--){
if(digits[i] < 9){
digits[i] += 1;
return digits;
}
else {
digits[i] = 0;
}
}
int[] newDigits = new int[length + 1];
newDigits[0] = 1;
return newDigits;
}
6. Kết thúc
Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!
Bình luận