leetcode刷题记录day006:48和344

48、难度中等:

要求:在 原地 旋转图像

方法一:自外向内顺时针循环:

class Solution {
    public void rotate(int[][] matrix) {
        if(matrix.length == 0 || matrix.length != matrix[0].length) { //若传来的数组不是等边的或者元素为0那就返回
            return;
        }
        int nums = matrix.length; //二维数组的行长
        int times = 0; //最外层框是0,往内逐层+1。取0开始是因为数组下标从0开始
        //nums >> 1意为nums除2^1,也就是自外向内共有多少层框。times代表层数,<=其代表不超过最大层数
        while(times <= (nums >> 1)){ //循环每层框。用小于等于原因看下面解释
            int len = nums - (times << 1); //times << 1意为times*2^1。len为当前框边长
            //将当前框的四条边进行元素交换。每条边有len个元素(0~len-1个),所以循环len-1次,每次循环交换四条边的各一个元素
            for(int i = 0; i < len - 1; ++i){ 
                //下面交换部分如果想象不出请结合输入数组的结构观看
                int temp = matrix[times][times + i]; 
                matrix[times][times + i] = matrix[times + len - i - 1][times];
                matrix[times + len - i - 1][times] = matrix[times + len - 1][times + len - i - 1];
                matrix[times + len - 1][times + len - i - 1] = matrix[times + i][times + len - 1];
                matrix[times + i][times + len - 1] = temp;
            }
            ++times; //结束一层框的工作后开始对下一层框进行操作
        }       
    }
}

自外向内一共有不超过 n/2 层(单个中心元素不算一层)矩形框。
(为什么是n/2层:因为每向下一层宽度减2,所以n*n的矩阵最多有n/2层)
对于第 times 层矩形框,其框边长 len=nums−(times∗2),
(times从0开始,最外层是第0层、nums是传来二维数组的行长)
将其顺时针分为 4 份 len−1 的边,对四条边进行元素的循环交换即可。

关键部分:交换元素:
int temp = matrix[times][times + i]; 
matrix[times][times + i] = matrix[times + len - i - 1][times];
matrix[times + len - i - 1][times] = matrix[times + len - 1][times + len - i - 1];
matrix[times + len - 1][times + len - i - 1] = matrix[times + i][times + len - 1];
matrix[times + i][times + len - 1] = temp;

1、第一行代码:
用temp保存第一个元素的值,然后把第二个元素的值存到第一个元素地址中,第三个元素的值存到第二个元素的地址中…把temp的值存到最后一个元素的地址中。
leetcode刷题记录day006:48和344

2、第二行代码:
第一个元素matrix[times] [times + i]:times表示当前框的层级(也就是要处理的起始元素所在二维数组的行位置,第一个元素从当前框的第一行取)times+1表示当前元素在当前边中处于第几位(也就是处在当前二维数组当前行中的第几列)二者结合起来就是当前元素处于当前二维数组的位置,随着 i 的递增+1遍历当前框边的每一个元素。

第二个元素matrix[times + len - i - 1] [times]:times + len - i - 1表示无论上一个元素所处行位置在哪,直接加上最大行数(+len),此时可能存在溢出,所以再减去上一个元素的行位置(-i),因为行位置的下标从0开始计数,而我们此前加的是len而非len-1,所以再-1(-1)。由于第二个元素从当前框的第一列取,所以列的位置写times不变。
leetcode刷题记录day006:48和344

第三个元素matrix[times + len - 1] [times + len - i - 1]:times + len - 1中因为len是动态变化的,随着当前框的层数变化而变化,所以times+len-1永远不会溢出。times为第一个元素的行数,只需加上最大len-1,就是第三个元素的行数(也就是相对第一个元素所处行的对称行)。times + len - i - 1:直接看下面的图:
leetcode刷题记录day006:48和344

第四个元素matrix[times + i] [times + len - 1]:times + i是因为行数是从上到下的,所以 i +1递增。times + len - 1是因为列与第二个元素的列对称,所以直接最大值len-1。
leetcode刷题记录day006:48和344

全图如下:
leetcode刷题记录day006:48和344

我们发现一个很巧的事情:
①、第一个元素的列取值times + i书写与第四个元素的行取值times + i相同,
②、第二个元素的列取值times书写与第一个元素的行取值times相同,
③、第三个元素的列取值times + len - i - 1与第二个元素的行取值相同,
④、第四个元素的列取值times + len - 1与第三个元素的行取值相同。

对①、二者都是从基础值递增+1,所以times+i。并且据图可知基础值都是times(第一个元素的是同一行+1、第四个元素的是同一列+1)
对②、二者的取值都是不变的,都是取基础值不变。第一个元素是第一行不变,第二个元素是第一列不变。
对③、二者的取值都是从最后一位往前直到基础值。
对④、二者的取值都是最后一位不变。

为什么 while(times <= (nums >> 1)) 中使用 <= :

int nums = matrix.length;结果:若数组matrix为 [ 6 ] [ 10 ] 那么nums就是6
times从0开始
nums >> 1结果为3
这么一看框数有3层,但我们从0开始到3总共处理了4层。
然而leetcode中无论我们使用 <= 还是 < 结果都是正确的,消耗时间也相同。这就很离谱。

方法2:两次翻转:

class Solution {    
	public void rotate(int[][] matrix){
        if(matrix.length == 0 || matrix.length != matrix[0].length) {
            return;
        }
        int nums = matrix.length;
        for (int i = 0; i < nums; ++i){
            for (int j = 0; j < nums - i; ++j){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[nums - 1 - j][nums - 1 - i];
                matrix[nums - 1 - j][nums - 1 - i] = temp;
            }
        }
        for (int i = 0; i < (nums >> 1); ++i){ //水平中线上下反转
            for (int j = 0; j < nums; ++j){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[nums - 1 - i][j];
                matrix[nums - 1 - i][j] = temp;
            }
        }
    }
}

原理:先沿左上 - 右下的对角线翻转,再沿水平中线上下翻转,可以实现顺时针 90 度的旋转效果。可以拿一个纸片自己测试。

代码中的第一个for循环可用下图表示:原理:当前元素和它关于主对角线对称元素:当前元素的行和对称元素的行无关系,但当前元素的列和对称元素的行相关,由下图可知,最大行数(nums-1)减去当前元素的列数(j)就是其行。
由于我们只要替换上三角区域就等于替换完了全区域,所以当我们处理第0行时需要处理所有列 nums - i = nums - 0 = nums。随着行数处理完的递增,我们所需处理的列也递减,所以 nums - i。
leetcode刷题记录day006:48和344

344、难度简单:

方法一:双指针:时间复杂度:O(N),空间复杂度:O(1)

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }
}
上一篇:内容协商,与content-type,httpMessageConverter


下一篇:leetcode 344. 反转字符串