動機

很有因緣的一題

當初自己有解出來，不過那個index的方式十分可怕，加上自己本來就不喜歡index的題目(很多時候都是考細不細心而已，想法很簡單，但是實作細節很多) 所以解完就放著了

結果某次offsite就遇到了，同時OJ的網站還十分爛，用stdout當作解答輸出!? 都什麼年代了!? debug的輸出與解答的輸出混在一起，十分痛苦

同時那個OJ還要裝browser plugin，來錄音與錄影!!?? 還讓我的mac一直叫!!

因此超不喜歡這種題目，讓人感覺回到高中或是大一 得不到演算法設計有關的啟發，就是比細心的題目 但就是有人offsite會放這種題目…

所以就重新解一次吧，把當時的錯愕了結於此

同時對於所有rotate的題目都用reverse去做就好，不然很痛苦

Problem

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

 

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Example 3:

Input: matrix = [[1]]Output: [[1]]

Example 4:

Input: matrix = [[1,2],[3,4]]Output: [[3,1],[4,2]]

 

Constraints:

  • matrix.length == n
  • matrix[i].length == n
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Sol

長度帶3，來推推看怎麼設定

從大的走法到小的走法

  1. 大的走法: 一圈一圈由外往內，直到中心點
for i in range((len(ms)+1)//2):
    n = len(ms)-i*2-1+i # end of range
    # (0,0) -> (1,1)
    # ....
  1. 小的走法: 把4個點轉一圈
# (0,0) -> (0,2) -> (2,2) -> (2,0)
# (0,1) -> (1,2) -> (2,1) -> (1,0)

# (0,+1)   (+1,0)   (0,-1)   (-1,0)

# 用把0設定成i, 2設定成n
# (i,i) -> (i,n) -> (n,n) -> (n,i)
# (i,i+1) -> (i+1,n) -> (n,n-1) -> (n-1,i)
# 把遞增量設定成a
tmp = ms[i][i+a]
ms[i][i+a] = ms[n-a][i]
ms[n-a][i] = ms[n][n-a]
ms[n][n-a] = ms[i+a][n]
ms[i+a][n] = tmp
  1. 小的走法要走幾次: n-i次 (目前處理範圍的總長-1次，最後一個不用轉，n與i都是index所以直接相減就是總長-1)

四個四個轉，這種座標就只能用推的

class Solution:
    def rotate(self, ms: List[List[int]]) -> None:
        n,a,b,prev = len(ms),0,0,ms[0][0]
        # (a,b) is the starting point of each ring
        while n > 0:
            for k in range(n-1):
                # 0,0 : 0,n-1 : n-1,n-1 : n-1,0
                # 0,1 : 1,n-1 : n-1,n-1-1 : n-1-1, 0
                ms[a][b+k], ms[a+k][b+n-1], ms[a+n-1][b+n-1-k], ms[a+n-1-k][b] = ms[a+n-1-k][b], ms[a][b+k], ms[a+k][b+n-1], ms[a+n-1][b+n-1-k]
            a, b = a+1, b+1
            n -= 2

case study

用對角線(1,5,9)去swap對面的值，之後每個row做reverse

1  2  3　　　 　　 1  4  7　　　　　     7  4  1

4  5  6　　-->　　 2  5  8　　 -->  　  8  5  2　　

7  8  9 　　　 　　3  6  9　　　　       9  6  3

class Solution {
public:
    void rotate(vector<vector<int>>& mx) {
        for(int i=0;i<mx.size();i++) {
            for(int j=i+1;j<mx.size();j++) {
                swap(mx[i][j],mx[j][i]);
            }
            reverse(mx[i].begin(),mx[i].end());
        }
    }
};