資訊專欄INFORMATION COLUMN
摘要：兩種方法，轉(zhuǎn)置鏡像法和公式法。首先看轉(zhuǎn)置鏡像法原矩陣為轉(zhuǎn)置后水平鏡像翻轉(zhuǎn)后所以，基本的思路是兩次遍歷，第一次轉(zhuǎn)置，第二次水平鏡像翻轉(zhuǎn)變換列坐標。公式法是應用了一個翻轉(zhuǎn)的公式如此翻轉(zhuǎn)四次即可。二者均可，并無分別。
Problem
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Given a matrix
[
[1,2],
[3,4]
]
rotate it by 90 degrees (clockwise), return
[
[3,1],
[4,2]
]
Challenge
Do it in-place.
Note兩種方法，轉(zhuǎn)置鏡像法和公式法。
首先看轉(zhuǎn)置-鏡像法：
原矩陣為：
1 2 3 4 5 6 7 8 9 (original)
轉(zhuǎn)置后：(matrix[i][j] --> matrix[j][i])
1 4 7 2 5 8 3 6 9 (transposed)
水平鏡像翻轉(zhuǎn)后：(matrix[i][j] --> matrix[i][matrix.length-1-j])
7 4 1 8 5 2 9 6 3 (flipped horizontally)
所以，基本的思路是兩次遍歷，第一次轉(zhuǎn)置，第二次水平鏡像翻轉(zhuǎn)（變換列坐標）。
需要注意的是，轉(zhuǎn)置操作是對于左上角-右下角對角線所分割的右側(cè)三角形矩陣進行的，即只對二分之一個矩陣進行轉(zhuǎn)置；水平鏡像翻轉(zhuǎn)時，對列不做完全循環(huán)，而是從0到n/2。否則翻轉(zhuǎn)后的前二分之一列坐標會再次被翻轉(zhuǎn)回去。
公式法是應用了一個翻轉(zhuǎn)90°的公式：newRow = width - oldCol, newCol = oldRow,
如此翻轉(zhuǎn)四次即可。
需要注意遍歷矩陣時的循環(huán)邊界條件，有兩種寫法:
1.
for (int i = 0; i < (n+1)/2; i++) {
for (int j = 0; j < n/2; j++) {
2.
for (int i = 0; i < n; i++) {
for (int j = i; j < n-1-i; j++) {
第一種寫法是翻轉(zhuǎn)左上方四分之一個矩陣；第二種寫法是翻轉(zhuǎn)以對角線分割的上方的三角形矩陣。二者均可，并無分別。
Solution轉(zhuǎn)置-鏡像法
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;
}
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65698.html
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...
摘要：而后吾當依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結(jié)點，令快指針先行數(shù)日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進。快慢指針亦止于其所焉。舞動長劍，中宮直入，直取首級，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業(yè)已成。 Problem Given a list, rotate the list to the right by k places, where k is...
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...
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...
摘要：建立兩個堆，一個堆就是本身，也就是一個最小堆另一個要寫一個，使之成為一個最大堆。我們把遍歷過的數(shù)組元素對半分到兩個堆里，更大的數(shù)放在最小堆，較小的數(shù)放在最大堆。同時，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...
閱讀 3251·2023-04-25 20:35
閱讀 3612·2019-08-30 15:54
閱讀 1992·2019-08-30 15:43
閱讀 2183·2019-08-29 15:14
閱讀 1889·2019-08-29 11:17
閱讀 3380·2019-08-26 13:36
閱讀 695·2019-08-26 10:15
閱讀 2835·2019-08-23 15:41
