ধরুন আমাদের একটি 2D বাইনারি ম্যাট্রিক্স আছে। প্রদত্ত ম্যাট্রিক্সের যেকোনো সারি বা কলামের জন্য আমরা সমস্ত বিট ফ্লিপ করতে পারি। যদি আমরা এই ক্রিয়াকলাপগুলির যে কোনও সংখ্যা সম্পাদন করতে পারি এবং প্রতিটি সারিকে একটি বাইনারি সংখ্যা হিসাবে বিবেচনা করি তবে আমাদের এই সংখ্যাগুলি দিয়ে তৈরি করা যেতে পারে এমন বৃহত্তম যোগফল খুঁজে বের করতে হবে৷
সুতরাং, যদি ইনপুট মত হয়
0 | 1 | 0 |
0 | 0 | 1 |
তাহলে আউটপুট হবে 11, যেমন আমরা উভয় সারি ফ্লিপ করলে আমরা 101 এবং 110 পাব, তাহলে যোগফল হবে 5 + 6 =11
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- ম্যাট্রিক্সে প্রতিটি সারির জন্য, করুন
- যদি r[0] 0 এর মত হয়, তাহলে
- আমি 0 থেকে r এর পরিসরে, কর
- r[i] :=-r[i] + 1
- আমি 0 থেকে r এর পরিসরে, কর
ম্যাট্রিক্সের 1 থেকে কলাম সাইজের রেঞ্জের j-এর জন্য - যদি r[0] 0 এর মত হয়, তাহলে
- cnt :=0
- আমি 0 থেকে ম্যাট্রিক্সের সারি গণনার পরিসরের জন্য, কর
- cnt :=cnt + 1 যদি ম্যাট্রিক্স[i, j] 1 হয় অন্যথায় -1
- যদি cnt <0, তারপর
- ম্যাট্রিক্সের 0 থেকে সারির আকারের মধ্যে,
- করুন
- ম্যাট্রিক্স[i, j] :=-ম্যাট্রিক্স[i, j] + 1
- ম্যাট্রিক্সের 0 থেকে সারির আকারের মধ্যে,
- উত্তর :=0
- ম্যাট্রিক্সে প্রতিটি সারির জন্য, করুন
- a :=0
- র প্রতিটি v এর জন্য, করুন
- a :=2 * a + v
- উত্তর :=ans + a
- উত্তর ফেরত দিন
- করুন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution: def solve(self, matrix): for r in matrix: if r[0] == 0: for i in range(len(r)): r[i] = -r[i] + 1 for j in range(1, len(matrix[0])): cnt = 0 for i in range(len(matrix)): cnt += 1 if matrix[i][j] else -1 if cnt < 0: for i in range(len(matrix)): matrix[i][j] = -matrix[i][j] + 1 ans = 0 for r in matrix: a = 0 for v in r: a = 2 * a + v ans += a return ans ob = Solution() matrix = [ [0, 1, 0], [0, 0, 1] ] print(ob.solve(matrix))
ইনপুট
[[0, 1, 0],[0, 0, 1]]
আউটপুট
11