刷题顺序参考：力扣刷题顺序
涉及题目
自己的解题思路： 题目上说不能使用另一个矩阵来旋转图像，那就只能一个一个的换位置了。和之前的一维数组向右移动三个的题目的想法差不多，可以看出来每次数组都会变四个，比如上图的n=3的时候，先变换位置的是四个角，然后是外圈剩下的四个，四个为一组进行变换。matrix[i][j]要变到的位置是matrix[j][n-i-1],这个时候matrix[j][n-i-1]的数要存到一个temp中，然后它也要换到它的最终位置。一个问题是如何判断一组四个循环结束，我的想法是把最开始的matrix[i][j]的值设置成-1001，这样如果又循环到了-1001，那么一组结束，这时需要开始下一组。开始下一组又有两种情况，一是直接往后移动一格，例如上图中，第一组是从1开始，结束后第二组要从2开始；第二种情况是如下图n=4时的情况，第三组是从9开始，但是第四组需要从4开始。设置两个标志位start和end，表示一层（即一圈）开始和结束的地方，最开始的时候start=0，end=n-1。如果第m组开始位置的列数为end-1，那么这次循环结束后就需要start++,end–。对于整个循环结束的标志，这里也是偷了个懒直接设置u为循环次数，循环的次数够了的时候，就可以停止了。整个思路其实不难，就是写代码写起来很麻烦。
public void rotate(int[][] matrix) {
int n = matrix.length;
int temp = matrix[0][0],tempi,temp1=matrix[0][0];
int start=0,end=n-1,u=1;
int i=start,j=start;
if(n>1){
matrix[0][0] = -1001;
while (u<=n*n){ temp1="matrix[j][n-i-1];" matrix[j][n-i-1]="temp;" temp="temp1;" if(n-i-1="=" end-1 && start++; end--; i="start;" j="start;" if(u!="n*n){" matrix[i][j]="-1001;" } else if(temp="=-1001){" }else { tempi="i;" u++; < code></=n*n){>
官网的题解： 第二个原地旋转的题解跟我的想法是一样的，不过把四次小的循环写到了一个里面，也更简单一些。第三个翻转的思想其实也想过，不过没想到到底怎么翻转，原来只要上下翻转再沿着对角线翻转就可以。还是比较简单的。
- 矩阵置零
自己的想法： 这个题目提交通过的时候感觉像个简单题。想法很简单，遍历第一次使用二维数组存储原数组0所在的行列，然后第二次遍历存储行列的数组，并且把相应的行列中的数都改成0。本来以为会超出时间限制，竟然没有。
public void setZeroes(int[][] matrix) {
int m=matrix.length,n=matrix[0].length;//mxn
int [][] array = new int[2][m*n];//每一列存数组中0的位置 i，j
int u=0;//表示数组中0的个数
for(int i=0;i<m;i++){ for(int j="0;j<n;j++){" if(matrix[i][j]="=0){" array[0][u]="i;" array[1][u]="j;" u++; } r="0;r<u;r++){" int row="array[0][r];" column="array[1][r];" i="0;i<n;i++){" matrix[row][i]="0;" matrix[j][column]="0;" < code></m;i++){>
官方题解： 用第一行和第一列来标记是否含0。但是第一行和第一列原本是否包含0需要用额外的标记。标记完之后再遍历一次，这次要从i=1和j=1开始，遇到对应的首行首列是0的那么这个位置的数就应该变成0。最后再根据首行首列的标记对首行首列进行更新。提交了一下发现运行的时间和内存和我的差不多。
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean flagCol0 = false, flagRow0 = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
flagCol0 = true;
}
}
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
flagRow0 = true;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (flagCol0) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
if (flagRow0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/set-matrix-zeroes/solution/ju-zhen-zhi-ling-by-leetcode-solution-9ll7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 生命游戏
自己的想法： 题目的字数很多看起来比较复杂，其实规则很简单，如果刚开始该位置的数为1，且周围1的数量等于2或者3，那么他还是1，否则变成0；如果刚开始该位置是0，且周围1的数量为3，那么他变为1。我的想法是用两个数组来存放1和0对应的位置。感觉这个和复制原数组作为规则提取是一样的想法，甚至我的还更麻烦一些。规则分成四角、外圈、内圈分别提取。写的太死太麻烦了有点。
public void gameOfLife(int[][] board) {
int m=board.length,n=board[0].length;
int [][] loc1 = new int[2][m*n];//存放活细胞所在的位置
int [][] loc0 = new int[2][m*n];
int num = 0;//记录周围活细胞数量
int u1=0,u0=0;//记录loc的长度
//四个角 外圈 内侧
if(m>1 && n>1){
for(int i=0;i<m;i++){ for(int j="0;j<n;j++){" num="0;" if(i="=0" && if(board[i][j+1]="=1)" num++; if(board[i+1][j]="=1)" if(board[i+1][j+1]="=1)" } else if(board[i][j-1]="=1)" if(board[i+1][j-1]="=1)" if(board[i-1][j]="=1)" if(board[i-1][j-1]="=1)" if(board[i-1][j+1]="=1)" if(j="=0){" else{ 内圈 if(board[i][j]="=1" (num="=2" || = i; loc1[1][u1]="j;u1++;}" {loc0[0][u0]="i;loc0[1][u0]=j;u0++;}" r="0;r<u1;r++){" board[loc1[0][r]][loc1[1][r]]="1;" board[loc0[0][r]][loc0[1][r]]="0;" { x="0;x<m;x++){" y="0;y<n;y++){" board[x][y]="0;" < code></m;i++){>
很多if，就很繁杂。参考题解中一位大佬的想法：用一个数组保存周边位置变化的坐标偏移值。通过一个循环遍历完周边的位置。这里只把偏移相关的代码粘上来以作参考。
int[] x = {0, 0, 1, 1, 1, -1, -1, -1};
int[] y = {1, -1, 1, -1, 0, 1, -1, 0};//存放坐标偏移
for(int k=0;k<8;k++){ curx="i+x[k];" cury="j+y[k];" if(curx<0 ||>=m || curY<0 || cury>=n) continue;
else if(board[curX][curY] >= 1) num++;
}
</0></8;k++){>
- 除自身以外数组的乘积
自己的想法： 不能用除法而且时间复杂度有要求。所以只能在输出数组和原数组上研究。除nums[i]以外的其余元素的乘积，分为两部分，左边的乘积和右边的乘积。那么就可以把output数组存放左边的乘积，nums数组存放右边的乘积，然后再相乘，就是最终结果。查看了官方题解改进了一下，右边的乘积可以直接用一个数值表示，每次更新数值即可，而且可以直接跟output相乘，省了一次遍历。
public int[] productExceptSelf(int[] nums) {
int[] output = new int[nums.length];//一个保存前i-1个数的乘积，一个保存后n-1-i个数的乘积
if(nums.length>0){
output[0]=1;
for(int i=1;i<nums.length;i++){ output是左边数组的乘积 output[i]="output[i-1]*nums[i-1];" } int te="1;//表示右边的乘积" for(int x="nums.length-1;x">=0;x--){
output[x] = te*output[x];
te = te*nums[x];
}
}
return output;
}
</nums.length;i++){>
思考： 今天已经把参考做题顺序的数组部分全部做完了。中间由于其实事情总是断断续续的在做，这个做题顺序确实很快，想出来一道题就可以解出来好几道，做题顺序还是很关键的。写了这么些个数组题发现，数组的旋转移动之类的题目其实都可以有两种方法来解答：一是替换，很麻烦。二是翻转，需要找到技巧。另外，学到了一个数组偏移的算法技巧，就是用偏移数组。有很多时候其实用一个数值可以代替用一个数组。数组题目到此结束！30道题成就达成，再接再厉！
Original: https://www.cnblogs.com/boboray/p/16219506.html
Author: 啵啵ray
Title: 力扣刷题之路-二维数组变换、前缀和数组
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/685590/
转载文章受原作者版权保护。转载请注明原作者出处！