Jewels and Stones

Q: Độ phức tạp thời gian của Jewels and Stones là gì?

Với một tập hợp (set), độ phức tạp là O(j + s) : cần j bước để tạo tập hợp từ jewels và một lần tra cứu trong thời gian hằng số cho mỗi viên trong s viên đá. Quét jewels với mỗi viên đá có độ phức tạp là O(j × s) .

Người mớiBăm

+10

Bạn nhận được hai chuỗi (string) ký tự. Mỗi ký tự trong jewels đại diện cho một loại đá quý và không có ký tự nào lặp lại. Mỗi ký tự trong stones là một viên đá bạn sở hữu. Hãy trả về số viên đá bạn sở hữu là đá quý. Các ký tự phân biệt chữ hoa và chữ thường: "a" và "A" là hai loại khác nhau.

Hàm

numJewelsInStones(jewels: string, stones: string) → integer

jewelsstring: các loại đá được tính là đá quý, mỗi loại tương ứng với một chữ cái
stonesstring: những viên đá bạn sở hữu, mỗi viên một chữ cái
Trả vềinteger: số viên đá có ký tự xuất hiện trong jewels

Ràng buộc

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
Cả hai chuỗi (string) chỉ chứa các chữ cái tiếng Anh, chữ thường và chữ hoa.
Các chữ cái trong jewels đều khác nhau.

Ví dụ

Đầu vào: jewels = "rR"stones = "rubyRRr"
Đầu ra: 4
Giải thích: Các loại đá quý là r và R. Trong rubyRRr, các viên đá r, R, R và r khớp nhau, còn u, b và y thì không, vì vậy đáp án là 4.

Đầu vào: jewels = "z"stones = "ZZZ"
Đầu ra: 0
Giải thích: Loại đá quý duy nhất là chữ thường z. Mỗi viên đá đều là chữ hoa Z, một loại khác, nên không viên nào được tính.

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

Với mỗi viên đá, bạn đặt một câu hỏi: ký tự này có phải là đá quý không? Tìm từng viên đá trong chuỗi jewels sẽ lặp lại cùng một lần quét. Hãy đưa các ký tự đá quý vào một tập hợp ngay từ đầu, như vậy mỗi viên đá chỉ cần tra cứu một lần.

Quét tìm từng viên đá quý

Ý tưởng

Với mỗi viên đá, duyệt qua jewels và dừng ở chữ cái đầu tiên trùng khớp; khi tìm thấy chữ cái trùng khớp, tăng biến đếm thêm 1. Dừng ở đó là an toàn vì các chữ cái đại diện cho viên ngọc đều khác nhau, nên mỗi viên đá khớp với nhiều nhất một chữ cái. Trong ví dụ đầu tiên, viên đá u được so sánh với r và R nhưng không làm tăng biến đếm.

Với j loại ngọc và s viên đá, số phép so sánh tối đa là j × s. Vì j ≤ 52, việc xử lý 10^4 viên đá cần khoảng 5 × 10^5 phép so sánh, đủ nhanh trong trường hợp này. Chi phí tăng theo số loại ngọc, vì ta thực hiện lại cùng một lượt tìm kiếm cho mỗi viên đá.

Thuật toán

Đặt count thành 0.
Với mỗi viên đá, so sánh nó với từng chữ cái trong jewels.
Khi gặp chữ cái trùng khớp đầu tiên, cộng 1 vào count rồi chuyển sang viên đá tiếp theo.
Trả về count.

def numJewelsInStones(jewels, stones):
    count = 0
    for stone in stones:
        for jewel in jewels:
            if stone == jewel:
                count += 1
                break  # the kinds are distinct: no second match is possible
    return count

Đặt những viên ngọc vào một tập hợp

Ý tưởng

Câu trả lời cho câu hỏi “ký tự này có phải là đá quý không?” không thay đổi với mỗi ký tự, nên hãy tính một lần cho mỗi loại: tạo một tập hợp từ các ký tự trong jewels. Tập hợp kiểm tra sự có mặt trong thời gian hằng số, nên mỗi viên đá chỉ cần một lần tra cứu thay vì quét qua.

Ở ví dụ đầu tiên, tập hợp là {r, R}. Khi duyệt rubyRRr, kết quả tra cứu lần lượt là có, không, không, không, có, có, có: bốn viên đá quý. Tạo tập hợp mất j bước và duyệt mất s bước, nên tổng độ phức tạp là O(j + s). Trong ngôn ngữ không có tập hợp tích hợp sẵn, một mảng cờ được đánh chỉ số theo mã ký tự cũng làm được việc tương tự.

Thuật toán

Tạo một tập hợp chứa mọi ký tự trong jewels.
Đặt count thành 0.
Với mỗi viên đá, cộng 1 vào count nếu tập hợp chứa viên đá đó.
Trả về count.

def numJewelsInStones(jewels, stones):
    kinds = set(jewels)
    count = 0
    for stone in stones:
        if stone in kinds:
            count += 1
    return count

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

Bỏ qua chữ hoa chữ thường. Chuyển cả hai chuỗi thành chữ thường sẽ khiến z khớp với Z, còn ví dụ thứ hai trả về 3 thay vì 0.
Đếm số loại đá quý khác nhau thay vì số viên đá. rubyRRr có hai loại đá quý nhưng có bốn viên đá quý; các viên lặp lại vẫn được tính.
Tạo tập hợp bên trong vòng lặp duyệt đá. Việc đó tốn j bước cho mỗi viên đá và khiến độ phức tạp quay lại O(j × s).
Đổi chỗ các đối số. Tập hợp phải chứa jewels, còn vòng lặp phải duyệt qua stones. Nếu đảo ngược, ("a", "aaa") trả về 1 thay vì 3.

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

Độ phức tạp thời gian của Jewels and Stones là gì?

Với một tập hợp (set), độ phức tạp là O(j + s): cần j bước để tạo tập hợp từ jewels và một lần tra cứu trong thời gian hằng số cho mỗi viên trong s viên đá. Quét jewels với mỗi viên đá có độ phức tạp là O(j × s).

Tại sao nên dùng tập hợp băm cho Jewels and Stones?

Mỗi viên đá đặt ra câu hỏi liệu ký tự của nó có phải là đá quý hay không. Tập hợp băm trả lời trong thời gian hằng số, còn việc tìm kiếm trong chuỗi jewels tốn thời gian tỷ lệ thuận với độ dài của chuỗi. Bạn chỉ tốn công xây dựng tập hợp một lần rồi tiết kiệm thời gian với mọi viên đá sau đó.

Bạn có thể giải bài này mà không dùng tập hợp không?

Có. Các chữ cái là chữ cái tiếng Anh, nên một mảng (array) gồm 128 cờ, được đánh chỉ số theo mã ký tự, có thể hoạt động như một tập hợp mà không cần băm. Đánh dấu từng chữ cái của viên ngọc, rồi đếm những viên đá có cờ được bật.

def numJewelsInStones(jewels, stones):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

jewels = "rR"
stones = "rubyRRr"

Đầu ra mong đợi