মান ল করুন ০ এবং ১ ধারণকারী একটি তালিকা, আমরা তালিকার সামনে থেকে বা পিছন থেকে মান মুছে ফেলতে পারি। অবশেষে বাকি তালিকায় ০ এবং ১ সমান সংখ্যক থাকতে হবে। ন্যূনতম কতটি ডিলিশন লাগবে তা খুঁজে বের করতে হবে।
যদি ইনপুট হয় nums = [1, 1, 1, 0, 0, 1], তবে আউটপুট হবে ২, কারণ প্রথম ১ এবং শেষ ১ মুছে ফেললে দুটি ১ এবং দুটি ০ থাকবে।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- longest := 0
- d := একটি ম্যাপ যেখানে ০ কী-এর জন্য -1 মান আছে
- currSum := 0
- i কে ০ থেকে nums-এর আকার পর্যন্ত লুপ চালান:
- যদি nums[i] == 0, currSum := currSum - 1
- অন্যথায়, currSum := currSum + 1
- যদি currSum d-এ থাকে, longest := max(longest, i - d[currSum])
- অন্যথায়, d[currSum] := i
- nums-এর আকার - longest ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class Solution: def solve(self, nums): longest = 0 d = {0 : -1} currSum = 0 for i in range(len(nums)): if nums[i] == 0: currSum -= 1 else: currSum += 1 if currSum in d: longest = max(longest, i - d[currSum]) else: d[currSum] = i return len(nums) - longest ob = Solution() nums = [1, 1, 1, 0, 0, 1] print(ob.solve(nums))ইনপুট
[1, 1, 1, 0, 0, 1]
আউটপুট
2
