Bài 8 Leetcode: String to Integer (atoi)

Đề bài:

Triển khai hàm myAtoi(string s), chuyển đổi một chuỗi thành một số nguyên có dấu 32-bit (tương tự như hàm atoi trong C/C++).

Thuật toán của myAtoi(string s) được thực hiện như sau:

1. Đọc và bỏ qua bất kỳ khoảng trắng nào ở đầu chuỗi.

2. Kiểm tra xem ký tự tiếp theo (nếu chưa đến cuối chuỗi) có phải là ‘-‘ hoặc ‘+’ không. Đọc ký tự này nếu nó là ‘-‘ hoặc ‘+’. Điều này xác định kết quả cuối cùng là âm hay dương. Giả sử kết quả là dương nếu cả hai ký tự đều không xuất hiện.

3. Đọc các ký tự tiếp theo cho đến khi gặp ký tự không phải chữ số hoặc đến cuối chuỗi đầu vào. Các ký tự phía sau sẽ bị bỏ qua.

4. Chuyển đổi các chữ số này thành một số nguyên (ví dụ: “123” -> 123, “0032” -> 32). Nếu không có chữ số nào được đọc, số nguyên sẽ là 0. Thay đổi dấu nếu cần (từ bước 2).

5. Nếu số nguyên vượt quá phạm vi số nguyên có dấu 32-bit [-2³¹, 2³¹ – 1], thì giới hạn số nguyên để nó vẫn nằm trong phạm vi đó. Cụ thể, số nguyên nhỏ hơn -2³¹ sẽ được giới hạn thành -2³¹ và số nguyên lớn hơn 2³¹ – 1 sẽ được giới hạn thành 2³¹ – 1.

6. Trả về số nguyên là kết quả cuối cùng.

Lưu ý:

• Chỉ có ký tự khoảng trắng ‘ ‘ được coi là ký tự khoảng trắng.
• Không bỏ qua bất kỳ ký tự nào khác ngoài khoảng trắng ở đầu hoặc phần còn lại của chuỗi sau các chữ số.

Ví dụ 1:

Input: s = "42"
Output: 42
Giải thích: Các ký tự được gạch chân là những ký tự được đọc vào, dấu mũ (^) là vị trí đọc hiện tại.
Bước 1: "42" (không có ký tự nào được đọc vì không có khoảng trắng dẫn đầu)
^
Bước 2: "42" (không có ký tự nào được đọc vì không có dấu '-' hoặc '+')
^
Bước 3: "42" ("42" được đọc vào)
^
Số nguyên đã được phân tích là 42.
Vì 42 nằm trong khoảng [-2^31, 2^31 - 1], kết quả cuối cùng là 42.

Ví dụ 2:

Input: s = "   -42"
Output: -42
Giải thích:
Bước 1: " -42" (khoảng trắng dẫn đầu được đọc và bỏ qua)
^
Bước 2: " -42" (ký tự '-' được đọc, vì vậy kết quả phải là số âm)
^
Bước 3: " -42" ("42" được đọc vào)
^
Số nguyên đã được phân tích là -42.
Vì -42 nằm trong khoảng [-2^31, 2^31 - 1], kết quả cuối cùng là -42

Ví dụ 3:

Input: s = "4193 with words"
Output: 4193
Giải thích:
Bước 1: "4193 with words" (không có ký tự nào được đọc vì không có khoảng trắng dẫn đầu)
^
Bước 2: "4193 with words" (không có ký tự nào được đọc vì không có dấu '-' hoặc '+')
^
Bước 3: "4193 with words" ("4193" được đọc vào; việc đọc dừng lại vì ký tự tiếp theo không phải là chữ số)
^
Số nguyên đã được phân tích là 4193.
Vì 4193 nằm trong khoảng [-2^31, 2^31 - 1], kết quả cuối cùng là 4193.

Ràng buộc:

• 0 <= độ dài của s <= 200
• s bao gồm các chữ cái tiếng Anh (chữ thường và chữ hoa), chữ số (0-9), dấu cách (‘ ‘), ‘+’, ‘-‘, và ‘.’.

Giải thích thuật toán bằng C++

class Solution {
 public:
  int myAtoi(string s) {
    trim(s);
    if (s.empty())
      return 0;

    const int sign = s[0] == '-' ? -1 : 1;
    if (s[0] == '+' || s[0] == '-')
      s = s.substr(1);

    long num = 0;

    for (const char c : s) {
      if (!isdigit(c))
        break;
      num = num * 10 + (c - '0');
      if (sign * num < INT_MIN)
        return INT_MIN;
      if (sign * num > INT_MAX)
        return INT_MAX;
    }

    return sign * num;
  }

 private:
  void trim(string& s) {
    s.erase(0, s.find_first_not_of(' '));
    s.erase(s.find_last_not_of(' ') + 1);
  }
};

Đây là một đoạn mã trong ngôn ngữ C++ để triển khai hàm myAtoi(string s) theo thuật toán đã mô tả trước đó. Dưới đây là giải thích chi tiết về thuật toán này:

1. Hàm trim(string& s): Đây là một hàm hỗ trợ để cắt bỏ các khoảng trắng ở đầu và cuối chuỗi. Hàm này sử dụng các phương thức erase để loại bỏ các ký tự khoảng trắng từ đầu chuỗi (s.erase(0, s.find_first_not_of(‘ ‘))) và từ cuối chuỗi (s.erase(s.find_last_not_of(‘ ‘) + 1)).

2. Hàm myAtoi(string s): Đây là hàm chính để chuyển đổi chuỗi thành số nguyên. Hàm này nhận đầu vào là một chuỗi s.

3. trim(s): Thực hiện cắt bỏ khoảng trắng ở đầu và cuối chuỗi s bằng cách gọi hàm trim.

4. Kiểm tra s.empty(): Nếu chuỗi s là rỗng, hàm trả về 0.

5. Xác định dấu của số: Đầu tiên, ta kiểm tra nếu ký tự đầu tiên của chuỗi s là ‘-‘ thì số sẽ là số âm, ngược lại là số dương. Ta sử dụng biến sign để lưu giá trị dấu của số.

6. Xử lý ký tự ‘+’ và ‘-‘: Nếu ký tự đầu tiên của chuỗi s là ‘+’ hoặc ‘-‘, ta loại bỏ ký tự đó bằng cách gán s bằng chuỗi con của s bắt đầu từ vị trí 1 (s.substr(1)).

7. Khởi tạo biến num với giá trị ban đầu là 0. Biến num sẽ lưu giá trị số nguyên cuối cùng sau khi chuyển đổi.

8. Vòng lặp for: Với mỗi ký tự c trong chuỗi s, ta kiểm tra nếu ký tự đó không phải là chữ số (isdigit(c)), thì dừng vòng lặp. Ngược lại, ta cập nhật giá trị của num bằng cách nhân num cho 10 và cộng với giá trị số tương ứng với ký tự c (‘0’ là 48 trong bảng mã ASCII). Điều này cho phép ta chuyển đổi chuỗi thành số nguyên.

9. Kiểm tra giới hạn: Trong quá trình chuyển đổi, ta kiểm tra nếu phép nhân của sign và num vượt quá giới hạn của số nguyên 32-bit (INT_MIN và INT_MAX), thì trả về giá trị tương ứng để giới hạn kết quả đầu ra.

10. Trả về kết quả: Cuối cùng, ta trả về giá trị sign * num là kết quả cuối cùng của hàm myAtoi.

Giải thích thuật toán bằng Java

class Solution {
  public int myAtoi(String s) {
    s = s.strip();
    if (s.isEmpty())
      return 0;

    final int sign = s.charAt(0) == '-' ? -1 : 1;
    if (s.charAt(0) == '+' || s.charAt(0) == '-')
      s = s.substring(1);

    long num = 0;

    for (final char c : s.toCharArray()) {
      if (!Character.isDigit(c))
        break;
      num = num * 10 + (c - '0');
      if (sign * num <= Integer.MIN_VALUE)
        return Integer.MIN_VALUE;
      if (sign * num >= Integer.MAX_VALUE)
        return Integer.MAX_VALUE;
    }

    return sign * (int) num;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def myAtoi(self, s: str) -> int:
    s = s.strip()
    if not s:
      return 0

    sign = -1 if s[0] == '-' else 1
    if s[0] in {'-', '+'}:
      s = s[1:]

    num = 0

    for c in s:
      if not c.isdigit():
        break
      num = num * 10 + ord(c) - ord('0')
      if sign * num <= -2**31:
        return -2**31
      if sign * num >= 2**31 - 1:
        return 2**31 - 1

    return sign * num