# Day24 ---- Rotate Image

12th鐵人賽

Ted

團隊貓肥加潤五倍祝福

2020-10-01 22:12:20

760 瀏覽

分享至

Day24 Leetcode Array系列---- Rotate Image

本次題目 Rotate Image by JS

這一次的題目敘述非常容易懂，請把陣列向右轉 90 度，但是不可以借助第二個陣列，意思是說，不可以做一個空陣列把原陣列的值一傳過去重新排好，只能在原陣列中藉由移動位置達成向右轉 90 度

input1= [
  [1,2,3],
  [4,5,6],
  [7,8,9]]
  
output1 = [
  [7,4,1],
  [8,5,2],
  [9,6,3]]
  
input2 = [
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]]
  
output2 = [
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]]

思考路線

先畫圖分析陣列旋轉每個元素位置變化的狀況
因為不能使用外部陣列，所以只能在內部陣列中移動，可以一次移動四個元素，一起轉大風吹
這 4 個元素的交換順序
要從這一圈的哪個元素開始旋轉
一圈需要轉幾次才可以將整圈的元素換到正確位置
考慮內外圈的問題
內外圈選轉次數有什麼規律
外圈轉好了要怎麼設定才會轉內圈
這裡可能需要用迴圈，要什麼條件下迴圈終止
如何用現有資料表達出 4 個點，且隨著迴圈進行可以對應到整圈的元素
如何用選外圈 4 個點的模式選到內圈的 4 個點讓它們旋轉

Coding Time

先從畫圖分析開始

matrix = [
[1,2]
[3,4]
]
changed_matrix =[
[3,1]
[4,2]
]

matrix[0][0] 的值跑到 [0][1]
matrix[0][1] 的值跑到 [1][1]
matrix[1][1] 的值跑到 [1][0]
matrix[1][0] 的值跑到 [0][0]

如果從 matrix[0][0] 開始轉動，交換順序可能是

        temp = matrix[0][0]
matrix[0][0] = matrix[1][0]
matrix[1][0] = matrix[1][1]
matrix[1][1] = matrix[0][1]
matrix[0][1] = temp

依照這樣的交換順序可以一次性換掉 4 個元素，且不會有元素被覆蓋的問題，因為我準備個 temp 來挪出空間裝元素

接著是考慮要轉多少次才能把一圈的元素轉到正確位置

//2x2
input= [
  [1,2],
  [3,4]]
   1
//3x3
input1= [
  [1,2,3],
  [4,5,6],
  [7,8,9]]
   1 2

//4x4
input2 = [
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]]
    1  2  3

一次旋轉 4 個點， 2x2 的陣列要轉 1 次就可以轉好 1 圈， 3x3 只要轉 2 次， 4x4 要轉 3 次，看到的規律是要轉好 1 圈的次數是每 1 排的元素 -1

接著是觀察內外圈旋轉次數， 3x3 外圈轉 2 次內圈轉 0 次， 4x4 外圈轉 3 次內圈轉 1 次，規律可能是內圈旋轉次數＝外圈次數 -2

要如何轉內圈

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

原本是從 [0][0] [0][3] [3][0] [3][3] 開始旋轉，
現在要轉內圈需要縮小範圍 [1][1] [1][2] [2][1] [2][2] 旋轉

要何時終止旋轉，目前知道外圈或內圈要旋轉幾次才能轉完全部元素(總旋轉次數)，所以當旋轉次數達到總旋轉次數就中止

以下是我想出來的寫法

input1= [
  [1,2,3],
  [4,5,6],
  [7,8,9]]
output1 = [
  [7,4,1],
  [8,5,2],
  [9,6,3]]
input2 = [
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]]
output2 = [
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]]
function rotation(ary){
  let start = 0                //用來縮限範圍用的，[0][0]
  let end = ary.length - 1     //用來縮限範圍用的，[3][3]
  let turn = 0                 //目前是第幾圈
  let max_turn = ary.length-1  //總旋轉次數
  
  while( start <  end){        //當範圍縮限到不見就結束
    // 這邊是 4 個點用變數表達的方法
    temp = ary[start][start+turn] 
    ary[start][start+turn] = ary[end-turn][start]   
    ary[end-turn][start] = ary[end][end-turn]       
    ary[end][end-turn] = ary[start+turn][end]       
    ary[start+turn][end] = temp                     
    
    turn +=1        //轉完 4 個點要增加一次旋轉次數
    if( turn == max_turn){  //當外圈轉完之後要轉內圈
      start += 1    //從外圈縮到內圈
      end   -= 1
      max_turn -=2  //調整成內圈的最大旋轉次數
      turn = 0      //調整內圈條件後旋轉圈數要重設
    }
  }
  return ary
}
function expect(a,b){
  console.log(JSON.stringify(a)==JSON.stringify(b))
  
expect(rotation(input1),output1)
expect(rotation(input2),output2)

如果把原陣列的值丟到空陣列重新排列，這題就非常簡單，只要依照傳入陣列的大小去填入對應數量的空陣列，再用雙迴圈把原陣列的值一個一個拔到空陣列重新排放即可，只要注意要拔對值與塞到正確的空陣列

input1= [
  [1,2,3],
  [4,5,6],
  [7,8,9]]
output1 = [
  [7,4,1],
  [8,5,2],
  [9,6,3]]
input2=[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]]
output2=[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]
function rotation(ary){
  y = ary.length 
  x = ary[0].length 
  result=[]
  console.log(result)
  for(let k = 0 ; k < y ; k++){
    result.push([])
  }
  for(let i = 0 ; i < y ; i++ ){
    for(let j = 0; j < x ; j++){
      result[j].unshift(ary[i][j])
    }
  }
  console.log(result)
  return result
}
function expect(a,b){
    console.log(JSON.stringify(a)==JSON.stringify(b))
}
expect(rotation(input1),output1)
expect(rotation(input2),output2)

當然網路上的高手有更強的做法

input1= [
  [1,2,3],
  [4,5,6],
  [7,8,9]]
output1 = [
  [7,4,1],
  [8,5,2],
  [9,6,3]]
input2 = [
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]]
output2 = [
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]]
function rotate(matrix) {          
  const N = matrix.length - 1;   
  // use arrow functions and nested map;
  const result = matrix.map((row, i) =>
       row.map((val, j) => {
                            console.log(`row: ${row}, i: ${i}, j: ${j}, matrix: ${matrix[N - j][i]}`) 

                            return matrix[N - j][i]} )
  );
  matrix.length = 0;       // hold original array reference
  matrix.push(...result);  // Spread operator
  console.log(matrix)
  return matrix;
}
// rotate(input1)
rotate(input2)

這一題其實非常生活應用，日常拿起手機拍照，有時會將照片向右或向左選轉，這個時候其實運用的程式與這題極為相似，照片其實就是一個大陣列，每一個 1px 都是 [r,g,b] 這樣的資料，向右選轉就是將這整個大陣列轉動

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀