ধরুন আমাদের একটি বাইনারি তালিকা (তালিকায় 1s এবং 0s) এবং আরেকটি মান k। সংখ্যার প্রতিটি মান একটি কারাগারের অবস্থার প্রতিনিধিত্ব করে যেখানে 1 দখলকৃত কোষ নির্দেশ করে এবং 0 খালি ঘর নির্দেশ করে। প্রতিটি দিনে যখন একটি কক্ষের দুটি সংলগ্ন কোষ থাকে যা উভয়ই দখলকৃত বা উভয়ই খালি থাকে, তখন এটি দখল হয়ে যায়। অন্যথায়, এটি খালি হয়ে যায়। তাই আমাদের কারাগারের অবস্থা খুঁজে বের করতে হবে k দিন পর।
সুতরাং, ইনপুট যদি nums =[1, 0, 1, 0, 0, 0, 0, 0] k =1 এর মত হয়, তাহলে আউটপুট হবে [0, 1, 1, 0, 1, 1, 1, 0], আমরা লক্ষ্য করতে পারি প্রথম এবং শেষ সূচক কখনই দখল করা যাবে না কারণ তাদের কখনই 2 প্রতিবেশী থাকতে পারে না।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:
- একটি ফাংশন সংজ্ঞায়িত করুন next_day_state()। এটি কোষ গ্রহণ করবে
- new_cells :=কোষের একটি অনুলিপি
- নতুন_কোষ[0] :=0, নতুন_কোষ[7] :=0 1 থেকে 6 রেঞ্জে j-এর জন্য
- করুন
- যদি কোষ[j - 1] কোষের মতো হয়[j + 1], তাহলে
- নতুন_কোষ[j] :=1
- অন্যথায়,
- নতুন_কোষ[j] :=0
- যদি কোষ[j - 1] কোষের মতো হয়[j + 1], তাহলে
- নতুন_কোষ ফিরিয়ে দিন
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
- দেখা হয়েছে :=একটি নতুন মানচিত্র
- পতাকা :=মিথ্যা, i :=0
- যখন i
- ns :=next_day_state(cells)
- যদি ns দেখা না যায়, তাহলে
- এনএসকে দেখা হিসাবে চিহ্নিত করুন
- অন্যথায়,
- পতাকা :=সত্য
- লুপ থেকে বেরিয়ে আসুন
- কোষ :=ns
- i :=i + 1
- N :=N mod (দেখা আইটেমের সংখ্যা)
- i :=0
- যখন i
- ns :=next_day_state(cells)
- i :=i + 1
- কোষ :=ns
আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:
উদাহরণ
import copy class Solution: def next_day_state(self, cells): new_cells = copy.copy(cells) new_cells[0] = 0 new_cells[7] = 0 for j in range(1, 7): if cells[j - 1] == cells[j + 1]: new_cells[j] = 1 else: new_cells[j] = 0 return new_cells def solve(self, cells, N): seen = dict() flag, i = False, 0 while i < N: ns = self.next_day_state(cells) if tuple(ns) not in seen: seen[tuple(ns)] = True else: flag = True break cells = ns i += 1 if flag: N = N % len(seen) i = 0 while i < N: ns = self.next_day_state(cells) i += 1 cells = ns return cells ob = Solution() nums = [1, 0, 1, 0, 0, 0, 0, 0] k = 1 print(ob.solve(nums, k))
ইনপুট
[4, 7, 2, 5], 6
আউটপুট
[0, 1, 1, 0, 1, 1, 1, 0]