To Lower Case

Q: Vì sao độ chênh lệch giữa chữ hoa và chữ thường là 32?

ASCII đặt các chữ cái in hoa ở mã từ 65 đến 90 và các chữ cái in thường ở mã từ 97 đến 122, với sáu ký hiệu ở giữa. Hai bảng chữ cái có cùng thứ tự, nên mỗi cặp cách nhau 97 - 65 = 32 . 32 tương ứng với một bit, vì vậy bật bit đó sẽ biến chữ cái in hoa thành chữ cái in thường.

Q: Bạn có thể đổi kiểu chữ bằng một phép toán bit không?

Đúng vậy. Với một chữ cái viết hoa, code | 32 bật bit phân biệt chữ hoa và chữ thường, nhờ đó tạo ra chữ cái viết thường, còn code & ~32 sẽ xóa bit đó. Bạn vẫn cần kiểm tra phạm vi trước, vì mẹo dùng bit tương tự cũng sẽ làm thay đổi chữ số và ký hiệu.

Q: Độ phức tạp thời gian khi chuyển một chuỗi thành chữ thường là bao nhiêu?

Độ phức tạp là O(n) với chuỗi có độ dài n , vì mỗi ký tự được kiểm tra một lần. Chuỗi mới cần O(n) bộ nhớ. Nếu bạn có thể thay đổi mảng ký tự ngay tại chỗ, bộ nhớ phụ giảm xuống O(1) .

Người mớiMảng và chuỗi

+10

Bạn nhận được một chuỗi s. Hãy trả về một chuỗi mới, trong đó mỗi chữ cái tiếng Anh viết hoa, từ A đến Z, được thay bằng chữ cái viết thường tương ứng. Mọi ký tự khác, chẳng hạn như chữ cái viết thường, chữ số hoặc ký hiệu, đều giữ nguyên.

Hàm

toLowerCase(s: string) → string

sstring: văn bản cần chuyển đổi
Trả vềstring: s với mọi chữ cái viết hoa được chuyển thành chữ thường

Ràng buộc

1 ≤ s.length ≤ 10⁴
Mọi ký tự trong s đều là chữ cái tiếng Anh, chữ số hoặc một trong các ký hiệu !#$%&()*+-./:;<=>?@[]^_`{|}~.

Ví dụ

Đầu vào: s = "Hello-World!"
Đầu ra: "hello-world!"
Giải thích: Các chữ in hoa H và W trở thành h và w. - và ! không phải là chữ cái, nên chúng giữ nguyên vị trí.

Đầu vào: s = "coddy_2026"
Đầu ra: "coddy_2026"
Giải thích: Không có chữ cái viết hoa nào để thay đổi. Các chữ cái viết thường, _ và các chữ số vẫn giữ nguyên.

Câu hỏi mở rộng

Bạn có thể viết toUpperCase bằng cùng vòng lặp và giải thích vì sao mã ký tự của A và a chỉ khác nhau một bit không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi ngôn ngữ đều có sẵn hàm chuyển thành chữ thường, và trong code thực tế, bạn nên gọi hàm đó. Người phỏng vấn đặt câu hỏi này để xem bạn có biết hàm đó làm gì không: trong ASCII, mã của mỗi chữ cái viết hoa thấp hơn mã của chữ cái viết thường tương ứng đúng 32 đơn vị, vì vậy bạn cộng 32 vào mỗi mã nằm trong khoảng từ 'A' đến 'Z'.

Gọi hàm chuyển thành chữ thường có sẵn

Ý tưởng

lower() của Python, toLowerCase() của JavaScript, downcase của Ruby và các hàm tương tự đã làm sẵn việc này; C và C++ có tolower để xử lý một ký tự, vì vậy bạn gọi nó trong một vòng lặp. Mỗi ký tự được xét một lần, mất thời gian O(n) và chuỗi mới cần O(n) bộ nhớ.

Một số hàm này tuân theo cài đặt ngôn ngữ của máy. Trong tiếng Thổ Nhĩ Kỳ, chữ thường của I là ı không có dấu chấm, vì vậy các phiên bản Java và C# yêu cầu dùng quy tắc cố định với Locale.ROOT và ToLowerInvariant. Trong một buổi phỏng vấn, câu trả lời này thường không được chấp nhận vì nó che khuất ý tưởng mà câu hỏi muốn kiểm tra.

Thuật toán

Gọi hàm chuyển thành chữ thường của ngôn ngữ bạn đang dùng với s, hoặc gọi tolower cho từng ký tự trong C và C++.
Chọn quy tắc cố định, không phụ thuộc vào ngôn ngữ, nếu hàm có hỗ trợ.
Trả về kết quả.

def toLowerCase(s):
    return s.lower()

Dịch chuyển mã ký tự của chữ cái in hoa

Ý tưởng

Mỗi ký tự được lưu dưới dạng một con số. Trong ASCII, các chữ cái từ A đến Z có mã từ 65 đến 90, còn các chữ cái từ a đến z có mã từ 97 đến 122. Cả hai dãy đều theo thứ tự bảng chữ cái và cách nhau 32, vì vậy chữ thường tương ứng với một chữ hoa có mã bằng mã của chữ hoa đó cộng 32: H có mã 72 và h có mã 104. Chỉ các mã từ 65 đến 90 thay đổi; các ký hiệu như _ nằm giữa Z và a nên phải được sao chép nguyên trạng.

Mỗi ký tự được kiểm tra một lần, với độ phức tạp thời gian O(n), và kết quả là một chuỗi mới có cùng độ dài, với độ phức tạp không gian O(n). Viết 'a' - 'A' thay vì 32 cho thấy con số này được tính từ đâu.

Thuật toán

Sao chép s vào một mảng ký tự hoặc mã.
Ở mỗi vị trí, đọc mã ký tự.
Nếu mã nằm trong khoảng từ 'A' (65) đến 'Z' (90), hãy cộng thêm 32.
Chuyển mảng trở lại thành một chuỗi rồi trả về.

def toLowerCase(s):
    # Every capital letter sits 32 codes below its small letter: 'A' is 65, 'a' is 97.
    shift = ord("a") - ord("A")
    chars = []
    for ch in s:
        if "A" <= ch <= "Z":
            ch = chr(ord(ch) + shift)
        chars.append(ch)
    return "".join(chars)

Lỗi thường gặp và trường hợp biên

Cộng 32 vào mọi ký tự không phải chữ thường. Các chữ số và ký hiệu cũng thay đổi: 1 trở thành Q.
Chỉ kiểm tra một đầu của phạm vi. code < 'a' cũng bắt cả [, _ và @, còn code >= 'A' cũng bắt mọi chữ cái thường.
Dùng < thay vì <= ở hai đầu, khiến A hoặc Z vẫn là chữ hoa.
Tạo đáp án bằng result = result + ch trên một chuỗi bất biến. Mỗi bước sao chép toàn bộ nội dung đã có, khiến độ phức tạp là bậc hai khi n = 10^4.
Trong C, ghi vào đầu vào hoặc quên ký tự kết thúc '\0'. Cấp phát n + 1 byte cho bản sao.

Câu hỏi thường gặp3

Vì sao độ chênh lệch giữa chữ hoa và chữ thường là 32?

ASCII đặt các chữ cái in hoa ở mã từ 65 đến 90 và các chữ cái in thường ở mã từ 97 đến 122, với sáu ký hiệu ở giữa. Hai bảng chữ cái có cùng thứ tự, nên mỗi cặp cách nhau 97 - 65 = 32. 32 tương ứng với một bit, vì vậy bật bit đó sẽ biến chữ cái in hoa thành chữ cái in thường.

Bạn có thể đổi kiểu chữ bằng một phép toán bit không?

Đúng vậy. Với một chữ cái viết hoa, code | 32 bật bit phân biệt chữ hoa và chữ thường, nhờ đó tạo ra chữ cái viết thường, còn code & ~32 sẽ xóa bit đó. Bạn vẫn cần kiểm tra phạm vi trước, vì mẹo dùng bit tương tự cũng sẽ làm thay đổi chữ số và ký hiệu.

Độ phức tạp thời gian khi chuyển một chuỗi thành chữ thường là bao nhiêu?

Độ phức tạp là O(n) với chuỗi có độ dài n, vì mỗi ký tự được kiểm tra một lần. Chuỗi mới cần O(n) bộ nhớ. Nếu bạn có thể thay đổi mảng ký tự ngay tại chỗ, bộ nhớ phụ giảm xuống O(1).

def toLowerCase(s):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "Hello-World!"

Đầu ra mong đợi

"hello-world!"