deque对象支持旋转操作,可以将元素向左或向右循环移动。
例如：
from collections import deque
dq = deque([1, 2, 3, 4])
dq.rotate(1)
执行后dq变为:
[4, 1, 2, 3]
元素向右移动了一位,最后一个元素到了最前面。
在这个问题中,我们有一个n*n的矩阵,利用deque来表示,旋转操作可以使列循环移动:
原矩阵:
[[1, 2, 3]
[4, 5, 6]]
旋转后:
[[3, 1, 2]
[6, 4, 5]]
第0列移动到最后,第2列移动到最前。
通过n次旋转,我们可以得到矩阵每种列排列顺序。
这样在每次旋转中计算対角线元素和,最终得到最大值。
所以这个rotate操作实现了按列的循环移位。
利用这个操作,结合记录最大对角线和,我们可以高效解决这个问题。
在deque的rotate方法中,正数表示向右旋转,负数表示向左旋转。
from collections import deque
dq = deque([1, 2, 3, 4])
向右旋转(rotate正数):
dq.rotate(1) # [4, 1, 2, 3]
dq.rotate(2) # [3, 4, 1, 2]
元素向右移动,最后一个元素moviel到最前面。
向左旋转(rotate负数):
dq.rotate(-1) # [2, 3, 4, 1]
dq.rotate(-2) # [3, 4, 1, 2]
元素向左移动,第一个元素moviel到最后面。
也就是:
正数表示向右循环旋转
负数表示向左循环旋转
在这个问题中,我们可以通过正数旋转实现按列循环移位,负数旋转实现按行循环移位。
那么向右/左旋转有什么不同呢?
向右旋转每次移动列
向左旋转每次移动行
旋转方向改变了移动的轴(列/行),但求最大对角线元素之和的逻辑是相同的。