Chương trình tìm số danh sách con có phần tử đầu và cuối giống nhau trong Python

Cho danh sách số nums, đếm số danh sách con (liên tiếp) mà phần tử đầu và cuối bằng nhau.

Ví dụ

Đầu vào: nums = [10, 15, 13, 10].
Đầu ra: 5 (danh sách con: [10], [15], [13], [10], [10,15,13,10]).

Thuật toán

1. Khởi tạo num_sublists = len(nums) (mỗi phần tử đơn lẻ là một danh sách con hợp lệ).
2. Đếm tần suất mỗi giá trị trong nums.
3. Với mỗi tần suất v > 1, thêm (v-1)*v//2 vào num_sublists (số cặp chỉ mục có giá trị giống nhau).
4. Trả về num_sublists.

Mã nguồn Python

from collections import defaultdict

class Solution:
    def solve(self, nums):
        num_sublists = len(nums)
        d = defaultdict(int)
        for n in nums:
            d[n] += 1
        for v in d.values():
            if v != 1:
                num_sublists += (v-1)*v//2
        return num_sublists

ob = Solution()
print(ob.solve([10, 15, 13, 10]))

Đầu vào / Đầu ra

Input: [10, 15, 13, 10]
Output: 5