Как написать функцию Python, чтобы максимизировать сумму N X N верхней левой подматрицы из заданной матрицы 2N X 2N?
Мне нужно решить следующую задачу: учитывая матрицу целых чисел 2N x 2N, вы можете перевернуть любую строку или столбец любое количество раз и в любом порядке. Задача состоит в том, чтобы вычислить максимальную сумму верхней левой подматрицы N X N, т.е. сумму элементов подматрицы от (0, 0) до (N – 1, N – 1). Например, для матрицы 4 X 4:
[112, 42, 83, 119,
56, 125, 56, 49,
15, 78, 101, 43,
62, 98, 114, 108]
Функция может поменять местами столбец 2 и строку 0, чтобы получить:
[119, 114, 42, 112,
56, 125, 101, 49,
15, 78, 56, 43,
62, 98, 83, 108]
а сумма верхних левых NXN(2X2) равна 119 + 114 + 56 + 125 = 414.
Я пробовал функцию ниже:
def seanMatrix(matrix):
n = len(matrix) // 2
rows = len(matrix)
columns = len(matrix[0])
for i in range(rows):
for j in range(columns // 2):
matrix[i][j], matrix[i][columns - j - 1] = matrix[i][columns - j - 1], matrix[i][j]
for i in range(rows // 2):
for j in range(columns):
matrix[i][j], matrix[rows - i - 1][j] = matrix[rows - i - 1][j], matrix[i][j]
leftSum= 0
for i in range(n):
for j in range(n):
leftSum += matrix[i][j]
return leftSum
Код дает мне 396 с той же матрицей, что неверно.
Вопрос: Как мне исправить код, чтобы получить правильный вывод? то есть иметь возможность получить максимальную сумму верхней левой матрицы 2 x 2.
@mozway Не совсем в любом месте, но что-то вроде этого. Мое решение Python уже короткое, но вы видите более короткую версию NumPy?
@Kelly да, возможно, не любой, но, вероятно, много возможностей (например, кубик Рубика), это была скорее интуиция, чем что-либо еще, я формально не анализировал проблему: p
@mozway Ты тоже кубер? :-)
Нет, я слишком плохо разбираюсь во всем, что требует запоминания тонн шаблонов, хотя мне нравится теория этого;)
@mozway Хорошо. Мне нравится и спидкубинг, и теория. Коммутаторы (которые я использовал в своем ответе) позволяют довольно легко решать многие запутанные головоломки. И видимо какие-то проблемы с кодировкой :-)
Ответы 1
Вы даже не пытаетесь максимизировать что-либо, вы просто слепо переворачиваете все один раз. На самом деле вы не должны делать никаких разворотов.
Вот что произойдет, если поменять местами строку i, затем столбец j, затем снова строку i, а затем снова столбец j:
j
•••••• •••••• •••••• •••••• ••••••
i •A••B• •B••A• •C••A• •A••C• •B••C•
•••••• => •••••• => •••••• => •••••• => ••••••
•••••• •••••• •••••• •••••• ••••••
•C•••• •C•••• •B•••• •B•••• •A••••
•••••• •••••• •••••• •••••• ••••••
Другие значения в строке i и столбце j перемещаются при первом развороте, но возвращаются при втором. Итак, в целом у нас есть только эти 3 цикла A, B и C. Все остальное там, где оно было в начале.
Этого достаточно, чтобы поместить наибольшее число каждой орбиты в верхний левый квадрант. Что такое орбита? Это четыре позиции, которые можно поменять местами, перевернув строку/столбец. Рассмотрим вашу матрицу:
[112, 42, 83, 119,
56, 125, 56, 49,
15, 78, 101, 43,
62, 98, 114, 108]
Одна орбита имеет числа 42, 83, 98, 114. Эти четыре могут меняться местами друг с другом и ни с кем другим. С двумя такими 3-циклами вы можете переместить число 114 в верхний левый квадрант, не изменяя никакие другие три орбиты. И ровно одна из четырех позиций орбиты находится в верхнем левом квадранте.
Итак, все, что вам нужно сделать, это посмотреть на все орбиты, найти наибольшее число каждой орбиты и сообщить их сумму.
A = [[112, 42, 83, 119],
[ 56, 125, 56, 49],
[ 15, 78, 101, 43],
[ 62, 98, 114, 108]]
n = len(A) // 2
print(sum(max(A[i][j], A[i][~j], A[~i][j], A[~i][~j])
for i in range(n)
for j in range(n)))
Вывод (Попробуйте онлайн!):
414
Примечание о ~: в контексте индексов я называю это оператором обратного индексирования. Python поддерживает отрицательные индексы: индекс -1 — это последний элемент, -2 — предпоследний и т. д. И ~0=-1, ~1=-2 и т. д. Таким образом, если i индексирует i-й элемент спереди, то ~i индексирует i-й элемент сзади. Очень удобно. Не нужно писать length-i-1.
Я только что попробовал это, и это сработало. Спасибо большое и за подробное объяснение.
@mozway Это вопрос, который я получил из набора для подготовки HackerRank. По-видимому, он должен переворачивать числа либо по строкам, либо по столбцам.