Chương trình tìm tích vô hướng của hai vector thưa trong Python

Giả sử ta có hai vector thưa (sparse vectors) được biểu diễn bằng hai danh sách. Ta phải trả về tích vô hướng của hai vector thưa này. Các vector được biểu diễn dưới dạng đối tượng, và danh sách được lưu trữ trong biến thành viên 'nums' trong đối tượng.

Ví dụ: vector1 = [1, 0, 0, 0, 1], vector2 = [0, 0, 0, 1, 1], kết quả là 1 vì tích vô hướng = 1*0 + 0*0 + 0*0 + 0*1 + 1*1 = 1.

Giải thuật

1. res := 0
2. Duyệt qua từng chỉ mục i, giá trị v trong nums của vector2:
   • Nếu v == 0: continue
   • Ngược lại nếu nums[i] của vector1 == 0: continue
   • Ngược lại: res := res + v * nums[i] của vector1
3. Trả về res

Ví dụ (Python)

class Solution:
    def __init__(self, nums):
        self.nums = nums
    
    def solve(self, vec):
        res = 0
        for i, v in enumerate(vec.nums):
            if v == 0:
                continue
            elif self.nums[i] == 0:
                continue
            else:
                res += v * self.nums[i]
        return res

ob1, ob2 = Solution([1, 0, 0, 0, 1]), Solution([0, 0, 0, 1, 1])
print(ob1.solve(ob2))

Input

[1, 0, 0, 0, 1], [0, 0, 0, 1, 1]

Output

1