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的值存到最后一个元素的地址中。
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不变。
第三个元素matrix[times + len - 1] [times + len - i - 1]:times + len - 1中因为len是动态变化的,随着当前框的层数变化而变化,所以times+len-1永远不会溢出。times为第一个元素的行数,只需加上最大len-1,就是第三个元素的行数(也就是相对第一个元素所处行的对称行)。times + len - i - 1:直接看下面的图:
第四个元素matrix[times + i] [times + len - 1]:times + i是因为行数是从上到下的,所以 i +1递增。times + len - 1是因为列与第二个元素的列对称,所以直接最大值len-1。
全图如下:
我们发现一个很巧的事情:
①、第一个元素的列取值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。
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;
}
}
}