[LintCode/LeetCode] Rotate Image

BenCHou 發布于2019-08-14 15:22 / 2839人閱讀

摘要：兩種方法，轉置鏡像法和公式法。首先看轉置鏡像法原矩陣為轉置后水平鏡像翻轉后所以，基本的思路是兩次遍歷，第一次轉置，第二次水平鏡像翻轉變換列坐標。公式法是應用了一個翻轉的公式如此翻轉四次即可。二者均可，并無分別。

Problem

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

Example

Given a matrix

[
    [1,2],
    [3,4]
]

rotate it by 90 degrees (clockwise), return

[
    [3,1],
    [4,2]
]

Challenge

Do it in-place.

Note

兩種方法，轉置鏡像法和公式法。
首先看轉置-鏡像法：
原矩陣為：

1  2  3             
4  5  6
7  8  9
(original)

轉置后：(matrix[i][j] --> matrix[j][i])

1  4  7
2  5  8
3  6  9
(transposed)

水平鏡像翻轉后：(matrix[i][j] --> matrix[i][matrix.length-1-j])

7  4  1
8  5  2
9  6  3
(flipped horizontally)

所以，基本的思路是兩次遍歷，第一次轉置，第二次水平鏡像翻轉（變換列坐標）。
需要注意的是，轉置操作是對于左上角-右下角對角線所分割的右側三角形矩陣進行的，即只對二分之一個矩陣進行轉置；水平鏡像翻轉時，對列不做完全循環，而是從0到n/2。否則翻轉后的前二分之一列坐標會再次被翻轉回去。

公式法是應用了一個翻轉90°的公式：newRow = width - oldCol, newCol = oldRow,
如此翻轉四次即可。
需要注意遍歷矩陣時的循環邊界條件，有兩種寫法:

for (int i = 0; i < (n+1)/2; i++) {
    for (int j = 0; j < n/2; j++) {

for (int i = 0; i < n; i++) {
    for (int j = i; j < n-1-i; j++) {

第一種寫法是翻轉左上方四分之一個矩陣；第二種寫法是翻轉以對角線分割的上方的三角形矩陣。二者均可，并無分別。

Solution

轉置-鏡像法

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n/2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n-1-j];
                matrix[i][n-1-j] = temp;
            }
        }
    }
}

公式法I.

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < (n+1)/2; i++) {
            for (int j = 0; j < n/2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
    }
}

公式法II.

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n-1-i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
    }
}

云服務器 GPU云服務器 Rotate 旋轉-rotate image java image

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65698.html

[LintCode/LeetCode] Rotate Array

Problem Given an array, rotate the array to the right by k steps, where k is non-negative. Example Example 1: Input: [1,2,3,4,5,6,7] and k = 3Output: [5,6,7,1,2,3,4]Explanation:rotate 1 steps to the r...

chanthuang 2019-08-16 12:44 評論0 收藏0
[LintCode/LeetCode] Rotate List

摘要：而后吾當依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結點，令快指針先行數日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進。快慢指針亦止于其所焉。舞動長劍，中宮直入，直取首級，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業已成。 Problem Given a list, rotate the list to the right by k places, where k is...

Blackjun 2019-08-14 15:22 評論0 收藏0
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 評論0 收藏0
[LintCode/LeetCode] First Unique Character in a S

Problem Given a string, find the first non-repeating character in it and return its index. If it doesnt exist, return -1. Example Given s = lintcode, return 0. Given s = lovelintcode, return 2. Tags A...

Xufc 2019-08-15 13:27 評論0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立兩個堆，一個堆就是本身，也就是一個最小堆另一個要寫一個，使之成為一個最大堆。我們把遍歷過的數組元素對半分到兩個堆里，更大的數放在最小堆，較小的數放在最大堆。同時，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 評論0 收藏0