#LeetCode:48. Rotate Image

LeetCode 48.

可以將這題分解成上圖的樣子,先從外層一層一層往內處理(圖中圈圈的部分),對於每一層都從四個角落開始向一個方向巡覽並交換其值(圖中三角形的部分),這樣即可得解。

C++(4ms)

/*******************************************************/
/* LeetCode 48. Rotate Image                           */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/04/14                                 */
/*******************************************************/
#include <vector>
using namespace std;

class Solution {
public:
  void fourSwap(int& a, int& b, int& c, int& d){
    swap(a, b);
    swap(a, c);
    swap(a, d);
  }

  void rotate(vector<vector<int>>& matrix) {
    if(matrix.size() <= 1) return;

    int layer = matrix.size() / 2;
    for(int i = 0 ; i < layer ; ++i){
      int lastIndex = matrix.size() - i - 1;
      for(int j = 0 ; j < lastIndex - i; ++j){
        fourSwap(
          matrix[i][i + j],
          matrix[i + j][lastIndex],
          matrix[lastIndex][lastIndex - j],
          matrix[lastIndex - j][i]
        );
      }
    }
  }
};

回應

目前無留言,歡迎留言!

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: