一、图片平滑器

图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。

每个单元格的  平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。

如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。

思路:

双层for循环对二维数组遍历。如何处理每一个格子？就是将以它为中心周围有效格子的和加起来。周围的格子范围是for(int x=row-1;x<=row+1;x++) for(int y=col-1;y<=col+1;y++);三行三列。如何判断格子是否在有效范围里:遍历周围格子范围的时候加一个if条件判断if(x>=0&&x<row&&y>=0&&y<col)

代码：

class Solution {public int[][] imageSmoother(int[][] img) {int row=img.length;int col=img[0].length;int[][] res=new int[row][col];for(int i=0;i<row;i++){for(int j=0;j<col;j++){//开始遍历int sum=0;//总和int num=0;//number个数for(int x=i-1;x<=i+1;x++){for(int y=j-1;y<=j+1;y++){if(x>=0&&x<row&&y>=0&&y<col){sum+=img[x][y];num++;}}}res[i][j]=sum/num;}}return res;}
}

二、轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

思路：

1.将一个数组轮转，下标为<=size-1-k的部分，就会往后移动。如果下标是>size-1-k的这部分就会翻转到前面去。

2.因此首先将整个数组反转，这样往后移动的和往前移动的效果都达到了。但是局部的顺序是反的。所以还要将局部进行反转

3.一共需要进行三次反转。

代码：

class Solution {public void rotate(int[] nums, int k) {/**1.首先将整个数组翻转过来2.然后将(0,k%nums.length-1)这段数组正序 3.(k%nums.length,nums.length-1)*/int size=nums.length;reverse(nums,0,size-1);reverse(nums,0,k%size-1);reverse(nums,k%size,size-1);}public void reverse(int[] nums,int left,int right){while(left<right){int temp=nums[left];nums[left]=nums[right];nums[right]=temp;left++;right--;}}
}

三、旋转函数(公式推导)

暴力法(超时)：每次从nums[i]出发，依次用0 1 2 3乘以接下来的每一个数，然后求和。找一个最大值

代码：

class Solution {public int maxRotateFunction(int[] nums) {int max=Integer.MIN_VALUE;int size=nums.length;for(int i=0;i<size;i++){int sum=0;for(int j=0;j<size;j++){sum+=j*nums[(i+j)%size];}//System.out.println("第"+(i+1)+"次的sum为:"+sum);max=Math.max(max,sum);}return max;}
}

规律法:

F0=0*a0+1*a1+2*a2+3*a3

F1=0*a3+1*a0+2*a1+3*a2

F2=0*a2+1*a3+2*a0+3*a1

...

找规律：F1=F0+a0+a1+a2-3*a3  

                   =F0+sum-4*a3

              F2=F1+a3+a0+a1-3*a2

                  =F1+sum-4*a2

因此F(i)=F(i-1)+sum-(size)*ai;

代码：

class Solution {public int maxRotateFunction(int[] nums) {int size=nums.length;int[] dp=new int[size];int sum=0;for(int i=0;i<size;i++){sum+=nums[i];dp[0]+=i*nums[i];}//根据找出的规律进行计算int max=dp[0];for(int i=1;i<size;i++){dp[i]=dp[i-1]+sum-size*nums[size-i];max=Math.max(max,dp[i]);}return max;}
}

四、螺旋矩阵(容易混乱)

思路:

使用左右上下边界:rowStart,rowEnd,colStart,colEnd;

while条件是rowStart<=rowEnd&&colStart<=colEnd;

分四种情况:

1.从左往右,遍历完之后rowStart++（最上面一行直接扔掉）

2.从上往下,遍历完之后colEnd--（最右边一列直接扔掉）

3.从右往左，遍历完之后rowEnd--（最下面一行直接扔掉）。从右往左的时候要判断(rowStart<=rowEnd)

4.从下往上同理。

代码：

 class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> list=new ArrayList<>();int rowEnd=matrix.length-1;int colEnd=matrix[0].length-1;int rowStart=0;int colStart=0;while(rowStart<=rowEnd&&colStart<=colEnd){//从左往右for(int i=colStart;i<=colEnd;i++){list.add(matrix[rowStart][i]);}rowStart++;//第二行了//从上往下for(int i=rowStart;i<=rowEnd;i++){list.add(matrix[i][colEnd]);}colEnd--;//少一列了//上右往左if(rowStart<=rowEnd){for(int i=colEnd;i>=colStart;i--){list.add(matrix[rowEnd][i]);}}rowEnd--;//少一行了//从下往上if(colStart<=colEnd){for(int i=rowEnd;i>=rowStart;i--){list.add(matrix[i][colStart]);}}colStart++;//列往右移动}return list;}
}

五、对角线遍历(我曹....)

六、旋转图像(有技巧)

技巧:先沿着对角线(右上到左下,统一一个方向就行)对称交换，然后按照列对称翻折。

案例：

1.先沿着对角线对称翻折交换 24换 37换 68换

2.然后沿着中间列，两边列对称交换。

17/28/39

代码：

class Solution {public void rotate(int[][] matrix) {/*** 有技巧的：先按照对角线翻折，然后再列翻折*/// 沿对角线翻折int size = matrix.length;for (int i = 0; i < size; i++) {for (int j = 0; j < i; j++) {swap(matrix, i, j, j, i);}}printfArr(matrix);// 然后按照列翻折for (int i = 0; i < size; i++) {for (int j = 0; j < size / 2; j++) {swap(matrix, i, j, i, size - 1 - j);}}printfArr(matrix);}public void swap(int[][] nums, int a, int b, int x, int y) {int temp = nums[a][b];nums[a][b] = nums[x][y];nums[x][y] = temp;}public void printfArr(int[][] nums) {System.out.println("===================================");for (int[] num : nums) {for (int number : num) {System.out.print(number + " ");}System.out.println("");}}
}

七、矩阵置零

思路：

首先遍历一遍数组，将元素值为0的横纵坐标记录下来。使用两个set集合,Set<Integer> zeroRow,

Set<Integer>zeroCol,(Set集合中的元素不能重复也没关系，因为如果碰到两个第0列，都是为了将第0列的元素置为0)；

代码：

class Solution {public void setZeroes(int[][] matrix) {int row=matrix.length;int col=matrix[0].length;Set<Integer> zeroRows=new HashSet<>();Set<Integer> zeroCols=new HashSet<>();//先把所有为0的点都找出来for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(matrix[i][j]==0){zeroRows.add(i);zeroCols.add(j);}}}//然后对行置零for(int r:zeroRows){for(int j=0;j<col;j++){matrix[r][j]=0;}}//对列置零for(int c:zeroCols){for(int i=0;i<row;i++){matrix[i][c]=0;}}}
}

八、生命游戏(和图片平滑器类似)

题目意思：就是判断每一个格子周围的八个格子中活细胞的个数(以该格子为中心)。然后根据活细胞的个数对该格子的细胞的状态进行判断。

注意的点：活细胞的个数是周围八个格子中的个数，不包含自身。然后不能判断完就修改格子的状态。这样会影响到其他格子的判断。所以应该创建一个nextState[i][j];

思路:

和图片平滑器类似，遍历每一个点,然后又遍历每一个点的周围八个点，如果越界的就不考虑

代码：

class Solution {public void gameOfLife(int[][] board) {int row = board.length;int col = board[0].length;int[][] nextState = new int[row][col];for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {// 然后对每一个细胞格子进行判断int live = 0;for (int x = i - 1; x <= i + 1; x++) {for (int y = j - 1; y <= j + 1; y++) {if (x >= 0 && x < row && y >= 0 && y < col) {live += board[x][y];}}}live -= board[i][j];// 要去掉当前细胞的值if (board[i][j] == 1 && (live < 2 || live > 3))nextState[i][j] = 0;else if (board[i][j] == 1 && (live == 2 || live == 3))nextState[i][j] = 1;else if (board[i][j] == 0 && live == 3)nextState[i][j] = 1;else {nextState[i][j] = board[i][j];}}}for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {board[i][j] = nextState[i][j];}}}
}

九、除自身以外数组的乘积(不让用除法)

思路：

对角线都是1(因为是除了自己以外，其他的都要相乘)

左下三角里:B[1]和右上三角里:B[1] 乘起来就是除了该元素以外，其他元素的乘积。

因此先求左下三角，再求右上三角，然后累乘就OK。

左下三角：

b[0]=1;从b1开始->b[1]=b[0]*a[0];

b[2]=b[1]*a[1]; 因此找到规律：

for(int i=1;i<size;i++){b[i]=b[i-1]*a[i-1];
}

右上三角:

左下三角是从1开始的，那么右下三角就从size-2开始;int temp=1;

temp*=a[i+1]//每一行都会积累 eg:最后一行是1 倒数第二行是1*5 倒数第三行是1*4*5

b[i]*=temp;//之前左下三角的累积 再乘以右上三角的累积

int temp=1;
for(int i=size-2;i>=0;i--){temp=a[i+1];b[i]*=temp;
}

代码：

class Solution {public int[] productExceptSelf(int[] nums) {int len = nums.length;if (len == 0) return new int[0];int[] ans = new int[len];ans[0] = 1;int tmp = 1;for (int i = 1; i < len; i++) {ans[i] = ans[i - 1] * nums[i - 1];}for (int i = len - 2; i >= 0; i--) {tmp *= nums[i + 1];ans[i] *= tmp;}return ans;}
}