Chương trình đếm số cặp đẹp trong mảng trong Python

Mô tả bài toán

Cho mảng nums chứa các số không âm. Một cặp chỉ số (i, j) được gọi là "đẹp" nếu 0 <= i < j < len(nums) và nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]). Hàm rev() đảo ngược phần dương của số nguyên (ví dụ: rev(564) = 465, rev(540) = 45). Hãy đếm số cặp đẹp, kết quả modulo 10^9 + 7.

Ví dụ

Nếu đầu vào là nums = [97,2,42,11], thì đầu ra là 2 vì có hai cặp: (0,2) và (1,3).

Giải thuật

1. Khởi tạo m = 10^9 + 7 và từ điển dic mặc định giá trị 0.
2. Duyệt từng num trong nums:
   • Tính rev = int(str(num)[::-1]).
   • Tăng dic[num - rev] lên 1.
3. Khởi tạo res = 0.
4. Duyệt các giá trị val trong dic.values():
   • res += val * (val - 1) // 2.
5. Trả về res % m.

Triển khai Python

from collections import defaultdict

def solve(nums):
    m = (10**9) + 7
    dic = defaultdict(int)
    for num in nums:
        rev = int(str(num)[::-1])
        dic[num - rev] += 1
    res = 0
    for val in dic.values():
        res += (val * (val - 1)) // 2
    return res % m

nums = [97, 2, 42, 11]
print(solve(nums))

Đầu vào

[97,2,42,11]

Đầu ra

2