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/maximum-69-number/

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 một số nguyên dương num chỉ bao gồm hai số 6 và 9.
Trả về số tối đa bạn có thể nhận được bằng cách thay đổi tối đa một chữ số (6 thành 9 và 9 thành 6).

Điều kiện:

  • 1 <= num <= 104.
  • num chỉ bao gồm chữ số 6 và 9.

Ví dụ 1:

Input: num = 9669
Output: 9969
Explanation: 
Đổi chữ số 9 đầu tiên thành 6 thì ra kết quả 6669.
Đổi chữ số 6 thứ hai thành 9 thì ra kết quả 9969.
Đổi chữ số 6 thứ ba thành 9 thì ra kết quả 9699.
Đổi chữ số 9 cuối cùng thành 6 thì ra kết quả 9666.
So sánh các số trên thì số lớn nhất là 9969.

Ví dụ 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Ví dụ 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

3. Phân tích

Như các bạn có thể thấy, bài này họ cho chúng ta một số nguyên dương num chỉ bao gồm chữ số 6 và 9. Họ yêu cầu chúng ta đổi chữ số 6 thành 9 và 9 thì thành 6 trong số num đã cho, mỗi lần đổi cho ra một số khác nhau. So sánh các số đã thay đổi và trả về kết quả là số lớn nhất.

  Thực ra thì các bạn không cần làm loăng ngoằng như vậy đâu, chúng ta không cần phải đổi hết tất cả các chữ số, rồi mới đem so sánh để lấy ra số lớn nhất. Chắc chắn số `9` thì lớn hơn `6` rồi, vậy nên chỉ khi nào gặp số `6` ta mới đổi thành số `9`. Dùng một vòng lặp duyệt qua từng chữ số của `num`, nếu thấy số `9` thì bỏ qua không đổi, còn nếu gặp số `6` thì ta đổi thành `9` rồi cho dừng vòng lặp luôn. Và đó sẽ là số lớn nhất chứ không phải bất kì số nào khác.

Done! Chúng ta tới bước tiếp theo!

4. Code chạy bằng cơm

  • Lấy ra các chữ số của num:
    Đầu tiên chúng ta sẽ biến số num này thành một mảng số nguyên digits chứa những chữ số của nó. Hãy thử với ví dụ 1 với num = 9669. Ta thấy có bốn chữ số, vậy nên mảng digits sẽ có kích thước là n = 4. Chúng ta sẽ thêm các phần tử vào cuối mảng digits, tức là chúng ta sẽ lấy từng chữ số phía cuối của num, vậy nên ta sẽ cần con trỏ i bắt đầu từ vị trí cuối cùng trong mảng
    leetcode-1323-1

    Bằng cách sử dụng vòng lặp while(), ta sẽ lấy được từng chữ số rồi đưa vào trong mảng digits
    Ý tưởng ở đây sẽ là, ta bắt đầu thêm phần tử vào cuối mảng digits, và để làm được như vậy ta sẽ chia num cho 10 và lấy phần dư (nếu có), phần dư đó sẽ là chữ số hàng đơn vị hiện tại của num. Sau khi lấy được chữ số hàng đơn vị hiện tại, ta gán num = num / 10 để bớt đi chữ số cuối ta vừa lấy, cùng với đó giảm i đi 1 để đến vị trí tiếp theo.
    leetcode-1323-2

    Tại vị trí i = 3, ta thấy i > 0 vậy nên thực hiện các phép tính và phép gán:
    leetcode-1323-3

    Tại vị trí i = 2, thỏa mãn i> 0 nên ta có:
    leetcode-1323-4

    Tại vị trí i = 1, vẫn thỏa mãn i > 0 nên ta có:
    leetcode-1323-5

    Và cuối cùng tại i = 0, thỏa mãn điều kiện i = 0 ta có:
    leetcode-1323-6

    Ok vậy la chúng ta đã có hết các chữ số của num ở trong mảng digits rồi!

  • Duyệt qua mảng digits và kiểm tra xem số nào là 6 thì đổi sang 9:
    Duyệt mảng từ trái qua phải, ta thấy tại vị trí i = 1 thì gặp số 6 đầu tiên, ta đổi thành 9 rồi break luôn vòng lặp:
    leetcode-1323-7

  • Biến đổi từ mảng digits trở lại thành số nguyên tố:
    Sau khi đã có các chữ số như ý muốn rồi, chúng ta phải ghép chúng lại thành số nguyên tố như ban đầu. Để làm được như vậy, chúng ta sẽ làm ngược lại với bước tách chữ số ở trên. Ta lấy chữ số từ trái qua phải, nhân với lũy thừa bậc n của 10, trong đó n tương ứng với giá trị của chữ số đó.
    Ví dụ 9669 thì chữ số lớn nhất thuộc đơn vị hàng nghìn là 9, ta sẽ nhân 9 với 10^3 và số 3 chính là n nói ở trên. Vậy làm thế nào để tìm ra n tương ứng với chữ số đó. Ta chỉ cần lấy chiều dài của dãy chữ số đó trừ đi một số tạm gọi là k và k mặc định ban đầu là 1, cụ thể ở ví dụ này ta có chiều dài của num là 4, vậy chữ số đầu tiền từ trái qua sẽ là 4 - 1 = 3. Sau mỗi lần nhân như vậy ta sẽ thêm k lên 1.
    Chúng ta sẽ có công thức cơ bản như sau:
    leetcode-1323-8

    Hãy đi từng bước để xem code chạy như thế nào? Tại vị trí i = 0, ta có:
    leetcode-1323-9

    Tại vị trí i = 1 ta có:
    leetcode-1323-10

    Tại vị trí i = 2 ta có:
    leetcode-1323-11

    Và cuối cùng tại i = 3:
    leetcode-1323-12

    Vậy là xong, chúng ta sẽ trả về kết quả là res = 9969, đúng với yêu cầu của đề bài.

5. Code bằng máy

Code của chúng ta như sau:

 public static int maximum69Number (int num) {
     int[] digits = getDigits(num);
     int res = 0;
     int n = digits.length;

     for (int i = 0; i < n; i++) {
         if (digits[i] != 9) {
             digits[i] = 9;
             break;
         } 
     }

     res = mergeDigit(digits);

     return res;
 }

   // Function lấy ra các chữ số của num rồi bỏ vào mảng digits
 public static int[] getDigits(int num){
     int n = String.valueOf(num).length();
     int[] digits = new int[n];
     int i = n - 1;

     while (i >= 0) {
         digits[i--] = num % 10;
         num /= 10;
     }

     return digits;
 }

   // Function ghép các chữ số sau khi đã thay đổi từ mảng digits thành một số nguyên hoàn chỉnh
 public static int mergeDigit(int[] digits){
     int res = 0, k = 1, i = 0;
     int n = digits.length;

     while(k <= n){
         res+= digits[i++] * Math.pow(10, (n - k));
         k++;
     }

     return res;
 }

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!!!