โปรแกรมหาผลรวมสูงสุดโดยพลิกองค์ประกอบแต่ละแถวใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี 2 มิติ สำหรับแถวหรือคอลัมน์ใดๆ ในเมทริกซ์ที่กำหนด เราสามารถพลิกบิตทั้งหมดได้ หากเราสามารถดำเนินการเหล่านี้จำนวนเท่าใดก็ได้ และเราถือว่าแต่ละแถวเป็นเลขฐานสอง เราต้องหาผลรวมที่ใหญ่ที่สุดที่สามารถสร้างได้จากตัวเลขเหล่านี้

ดังนั้นหากอินพุตเป็นแบบ

0	1	0
0	0	1

แล้วผลลัพธ์จะเป็น 11 ราวกับว่าเราพลิกทั้งสองแถวเราจะได้ 101 และ 110 ผลรวมคือ 5 + 6 =11

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

สำหรับแต่ละแถว r ในเมทริกซ์ ทำ
- ถ้า r[0] เหมือนกับ 0 แล้ว
  - สำหรับฉันในช่วง 0 ถึงขนาดของ r ทำ
    - r[i] :=-r[i] + 1
สำหรับ j ในช่วง 1 ถึงขนาดคอลัมน์ของเมทริกซ์ ทำ
- cnt :=0
- สำหรับ i ในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ ทำ
  - cnt :=cnt + 1 ถ้า matrix[i, j] เป็น 1 มิฉะนั้น -1
- ถ้า cnt <0 แล้ว
  - สำหรับ i ในช่วง 0 ถึงขนาดแถวของเมทริกซ์ ทำ
    - เมทริกซ์[i, j] :=-เมทริกซ์[i, j] + 1
ตอบ :=0
สำหรับแต่ละแถว r ในเมทริกซ์ ทำ
- a :=0
- สำหรับแต่ละ v ใน r ทำ
  - a :=2 * a + v
- ans :=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]]