Giả sử hai người bạn Amal và Bimal đang chơi một trò chơi với một danh sách các số được sắp xếp gọi là nums. Trong trò chơi này trong một lượt duy nhất, Amal chọn ba số bất kỳ. Bimal loại bỏ một trong số chúng, và sau đó Amal loại bỏ một trong số chúng. Danh sách bắt đầu với một số phần tử lẻ. Ở đây Amla muốn giảm thiểu số lượt cần thiết để danh sách không chứa phần tử lặp lại, Bimal muốn tối đa hóa số lượt. Nếu Amal và Bimal hoạt động tối ưu, chúng ta phải tìm ra bao nhiêu lượt cần thiết cho trò chơi này.
Vì vậy, nếu đầu vào là nums =[1, 1, 2, 3, 3, 3, 4], thì đầu ra sẽ là 2, vì Nếu Amal chọn [1, 1, 3], thì Bimal loại bỏ 3 để tối đa hóa lần lượt, mảng là [1, 1, 2, 3, 3, 4], Amal loại bỏ 1, vì vậy mảng là [1,2,3,3,4], sau đó ở lượt tiếp theo Amal chọn [3,3, 4], sau đó Bimal sẽ loại bỏ 4 để tối đa hóa lượt. Vì vậy, sau đó Amal có thể loại bỏ 3 và mảng sẽ là [1,2,3], không có phần tử trùng lặp.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
lặp lại:=0
đối với tôi trong phạm vi từ 1 đến kích thước của nums, hãy thực hiện
nếu nums [i] giống nums [i-1] thì
lặp lại:=lặp lại + 1
trả về thương số của (số lần lặp lại + 1) / 2
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, nums): repeats = 0 for i in range(1, len(nums)): if nums[i] == nums[i-1]: repeats += 1 return (repeats + 1) // 2 ob = Solution() nums = [1, 1, 2, 3, 3, 3, 4] print(ob.solve(nums))
Đầu vào
[1, 1, 2, 3, 3, 3, 4]
Đầu ra
2