[LintCode/LeetCode] Rotate Image

BenCHou 发布于2019-08-14 15:22 / 2673人阅读

摘要：两种方法，转置镜像法和公式法。首先看转置镜像法原矩阵为转置后水平镜像翻转后所以，基本的思路是两次遍历，第一次转置，第二次水平镜像翻转变换列坐标。公式法是应用了一个翻转的公式如此翻转四次即可。二者均可，并无分别。

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;
            }
        }
    }
}

混合云服务器托管 Rotate 旋转-rotate image java image

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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