ধরুন আমাদের কাছে জোড় দৈর্ঘ্যের একটি অ্যারে সংখ্যা আছে আরেকটি মান সীমা। এক পদক্ষেপে, আমরা সংখ্যা থেকে যেকোনো মানকে 1 এবং সীমার মধ্যে অন্য মান দিয়ে প্রতিস্থাপন করতে পারি, অন্তর্ভুক্ত। অ্যারেটিকে পরিপূরক বলা হয় যদি সমস্ত সূচক i, nums[i] + nums[n-1-i] একই সংখ্যার সমান হয়। তাই আমাদেরকে সংখ্যার পরিপূরক করার জন্য প্রয়োজনীয় নূন্যতম সংখ্যক চাল খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি nums =[1,4,2,3] limit =4 এর মত হয়, তাহলে আউটপুট হবে 1 কারণ এক চালে আমরা সূচক 1 থেকে 2 এ উপাদান তৈরি করতে পারি, তাই অ্যারে হবে [1,2] ,2,3], তারপর nums[0] + nums[3] =4, nums[1] + nums[2] =4, nums[2] + nums[1] =4, nums[3] + nums[ 0] =4
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=সংখ্যার আকার
- মধ্য :=n/2 এর ভাগফল
- zero_moves :=পূর্ণসংখ্যা টাইপের মানের একটি খালি মানচিত্র
- শুরু করুন :=আকারের একটি অ্যারে (2 * সীমা + 1), এবং 0 দিয়ে পূরণ করুন
- শেষ :=আকারের একটি অ্যারে (2 * সীমা + 1), এবং 0 দিয়ে পূরণ করুন
- res :=অসীম
- আমি 0 থেকে মধ্য - 1 রেঞ্জের জন্য, কর
- x :=সংখ্যা[i]
- y :=সংখ্যা[n - 1 - i]
- zero_moves[x + y] :=zero_moves[x + y] + 1
- শুরু [1 + ন্যূনতম x, y] 1 দ্বারা বাড়ান
- শেষ [সীমা + সর্বোচ্চ x, y] 1 দ্বারা বাড়ান
- ব্যবধান :=0
- পরিসীমা 2 থেকে সীমা*2 এর মধ্যে লক্ষ্যের জন্য, করুন
- ব্যবধান :=অন্তর + শুরু[লক্ষ্য]
- খরচ :=2 *(মধ্য - ব্যবধান) + ব্যবধান - শূন্য_চল[লক্ষ্য]
- res :=ন্যূনতম রেস এবং খরচ
- ব্যবধান :=অন্তর - শেষ[লক্ষ্য]
- রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
from collections import defaultdict
def solve(nums, limit):
n = len(nums)
mid = n // 2
zero_moves = defaultdict(int)
start = [0] * (2 * limit + 1)
end = [0] * (2 * limit + 1)
res = float('inf')
for i in range(mid):
x = nums[i]
y = nums[n - 1 - i]
zero_moves[x + y] += 1
start[min(x, y) + 1] += 1
end[max(x, y) + limit] += 1
intervals = 0
for target in range(2, limit * 2 + 1):
intervals += start[target]
cost = 2 * (mid - intervals) + intervals - zero_moves[target]
res = min(res, cost)
intervals -= end[target]
return res
nums = [1,4,2,3]
limit = 4
print(solve(nums, limit)) ইনপুট
[1,4,2,3], 4
আউটপুট
1
