Richest Customer Wealth

Q: Độ phức tạp thời gian của bài toán Tài sản của khách hàng giàu nhất là gì?

O(m × n) với m khách hàng và n ngân hàng, vì mỗi số dư được cộng một lần. Không thuật toán nào có thể bỏ qua một ô, vì số dư bị bỏ qua có thể là số dư giúp chủ sở hữu trở thành người giàu nhất. Giá trị lớn nhất đang được theo dõi chỉ cần thêm O(1) không gian.

Q: Các tổng có thể vượt quá giới hạn của số nguyên 32 bit không?

Không phải ở đây. Một hàng có tối đa 100 số dư, mỗi số dư tối đa 10^4 , nên tổng tối đa là 10^6 , nhỏ hơn nhiều so với 2^31 - 1 . Nếu giới hạn lớn hơn, bạn sẽ cộng vào một số nguyên 64 bit.

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

+10

Một ngân hàng lưu một bảng accounts gồm m hàng, mỗi hàng ứng với một khách hàng, và n cột, mỗi cột ứng với một ngân hàng: accounts[i][j] là số tiền khách hàng i có trong ngân hàng j. Tài sản của một khách hàng là tổng số tiền trong hàng của họ. Hãy trả về tài sản của khách hàng giàu nhất.

Hàm

maximumWealth(accounts: integer-2d-array) → integer

accountsinteger-2d-array: lưới số dư, mỗi khách hàng một hàng và mỗi ngân hàng một cột
Trả vềinteger: tổng lớn nhất của hàng

Ràng buộc

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100, và mọi hàng đều có cùng độ dài.
0 ≤ accounts[i][j] ≤ 10⁴

Ví dụ

Đầu vào: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Đầu ra: 14
Giải thích: Tổng các hàng lần lượt là 11, 14 và 10. Khách hàng ở giữa giàu nhất với 14, dù số dư lớn nhất, 8, thuộc về người khác.

Đầu vào: accounts = [[3], [9], [4]]
Đầu ra: 9
Giải thích: Mỗi khách hàng sử dụng một ngân hàng, nên các tổng là 3, 9 và 4, và đáp án là 9.

Lời giải

Mỗi số dư chỉ thuộc về đúng một khách hàng, vì vậy bạn phải đọc toàn bộ lưới: không cách nào nhanh hơn thời gian O(m × n). Vấn đề là bạn giữ lại bao nhiêu thông tin trong khi đọc. Chỉ tổng lớn nhất tính đến lúc đó mới quan trọng, vì vậy chỉ cần một con số.

Liệt kê tất cả các tổng, rồi chọn tổng lớn nhất

Ý tưởng

Đi qua từng hàng, cộng các số dư và lưu một tổng cho mỗi khách hàng: [11, 14, 10] trong ví dụ đầu tiên. Sau đó quét danh sách đó để tìm giá trị lớn nhất, 14.

Mỗi số dư trong m × n số dư được cộng một lần, nên thời gian chạy ổn. Chi phí nằm ở danh sách, gồm m số bổ sung mà bạn chỉ giữ lại để rồi loại bỏ tất cả, trừ một số.

Thuật toán

Tạo một danh sách trống totals.
Với mỗi hàng, cộng các số dư rồi thêm tổng vào totals.
Đặt richest bằng tổng đầu tiên.
Thay richest bằng bất kỳ tổng nào lớn hơn, rồi trả về giá trị đó.

def maximumWealth(accounts):
    # First pass: every customer's total wealth.
    totals = []
    for customer in accounts:
        wealth = 0
        for money in customer:
            wealth += money
        totals.append(wealth)
    # Second pass: the largest total.
    richest = totals[0]
    for wealth in totals:
        if wealth > richest:
            richest = wealth
    return richest

Luôn giữ giá trị lớn nhất

Ý tưởng

Khi đã biết tổng của một hàng, bạn chỉ cần xem tổng đó có lớn hơn tổng cao nhất tính đến lúc đó hay không. Hãy so sánh ngay và chỉ giữ một con số, richest. Trong ví dụ đầu tiên, richest lần lượt là 0 → 11 → 14 và giữ nguyên ở 14 khi tổng của hàng cuối cùng là 10.

Bắt đầu richest ở 0 là an toàn vì không số dư nào âm, nên mọi tổng đều ít nhất bằng 0 và một lưới toàn số 0 sẽ trả về 0. Nếu số dư có thể âm, bạn sẽ bắt đầu từ tổng của hàng đầu tiên.

Thuật toán

Đặt richest thành 0.
Với mỗi hàng, cộng các số dư của hàng đó vào wealth.
Nếu wealth > richest, đặt richest thành wealth.
Sau hàng cuối cùng, trả về richest.

def maximumWealth(accounts):
    richest = 0  # money is never negative, so 0 is a safe start
    for customer in accounts:
        richest = max(richest, sum(customer))
    return richest

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

Cộng các cột thay vì các hàng. Mỗi cột là một ngân hàng của tất cả khách hàng. Trong ví dụ đầu tiên, tổng các cột lần lượt là 14, 13 và 8, và cột đầu tiên chỉ khớp với đáp án do may mắn.
Trả về số dư lớn nhất. 8 là số lớn nhất trong lưới đầu tiên, nhưng chủ sở hữu của số đó có tổng cộng 11, ít hơn 14 của một khách hàng không có số dư nào vượt quá 5.
Đặt lại tổng của hàng sai chỗ. Đặt wealth thành 0 bên trong vòng lặp hàng, trước vòng lặp bên trong. Hãy đặt nó một lần ở bên ngoài, nếu không mỗi khách hàng sẽ cộng dồn số tiền của khách hàng trước đó.

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

Độ phức tạp thời gian của bài toán Tài sản của khách hàng giàu nhất là gì?

O(m × n) với m khách hàng và n ngân hàng, vì mỗi số dư được cộng một lần. Không thuật toán nào có thể bỏ qua một ô, vì số dư bị bỏ qua có thể là số dư giúp chủ sở hữu trở thành người giàu nhất. Giá trị lớn nhất đang được theo dõi chỉ cần thêm O(1) không gian.

Làm thế nào để tìm tổng hàng lớn nhất trong mảng 2D?

Duyệt qua các hàng, tính tổng từng hàng và lưu tổng lớn nhất vào một biến. Nhiều ngôn ngữ rút gọn vòng lặp bên trong bằng hàm sum có sẵn, chẳng hạn như max(sum(row) for row in accounts) trong Python. Dù dùng cách nào, bạn cũng chỉ đọc mỗi ô một lần.

Các tổng có thể vượt quá giới hạn của số nguyên 32 bit không?

Không phải ở đây. Một hàng có tối đa 100 số dư, mỗi số dư tối đa 10^4, nên tổng tối đa là 10^6, nhỏ hơn nhiều so với 2^31 - 1. Nếu giới hạn lớn hơn, bạn sẽ cộng vào một số nguyên 64 bit.

def maximumWealth(accounts):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]

Đầu ra mong đợi