二维数组

题目In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.Example 1:Input: nums = [[1,2], [3,4]]r = 1, c = 4Output: [[1,2,3,4]]Explanation:The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.Example 2:Input: nums = [[1,2], [3,4]]r = 2, c = 4Output: [[1,2], [3,4]]Explanation:There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.Note:The height and width of the given matrix is in range [1, 100].The given r and c are all positive.题目地址讲解二维数组，重新堆叠的问题。java代码class Solution { public int[][] matrixReshape(int[][] nums, int r, int c) { if(nums.lengthnums[0].length != rc){ return nums; }else{ int[][] result = new int[r][c]; for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ int sum = i*c+j; int row = sum/nums[0].length; int column = sum%nums[0].length; result[i][j] = nums[row][column]; } } return result; } }} ...

题目A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.Now given an M x N matrix, return True if and only if the matrix is Toeplitz.Example 1:Input:matrix = [ [1,2,3,4], [5,1,2,3], [9,5,1,2]]Output: TrueExplanation:In the above grid, the diagonals are:"[9]", “[5, 5]”, “[1, 1, 1]”, “[2, 2, 2]”, “[3, 3]”, “[4]".In each diagonal all elements are the same, so the answer is True.Example 2:Input:matrix = [ [1,2], [2,2]]Output: FalseExplanation:The diagonal “[1, 2]” has different elements.Note:matrix will be a 2D array of integers.matrix will have a number of rows and columns in range [1, 20].matrix[i][j] will be integers in range [0, 99].Follow up:What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?What if the matrix is so large that you can only load up a partial row into the memory at once?讲解这道题我一开始在while里面只用了一个限制条件，后来发现不行的。其实多加一些可能会出现的条件是一种很好的习惯。Java代码class Solution { public boolean isToeplitzMatrix(int[][] matrix) { for(int i=0;i<matrix.length;i++){ int row=i; int column=0; while(row<matrix.length-1 && column<matrix[0].length-1){ if(matrix[row][column]!=matrix[row+1][column+1]){ return false; } column++; row++; } } for(int i=0;i<matrix[0].length;i++){ int column=i; int row=0; while(row<matrix.length-1 && column<matrix[0].length-1){ if(matrix[row][column]!=matrix[row+1][column+1]){ return false; } column++; row++; } } return true; }} ...

题目On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.Now, we walk in a clockwise spiral shape to visit every position in this grid. Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.) Eventually, we reach all R * C spaces of the grid.Return a list of coordinates representing the positions of the grid in the order they were visited.Example 1:Input: R = 1, C = 4, r0 = 0, c0 = 0Output: [[0,0],[0,1],[0,2],[0,3]]Example 2:Input: R = 5, C = 6, r0 = 1, c0 = 4Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]Note:1 <= R <= 1001 <= C <= 1000 <= r0 < R0 <= c0 < C题目地址讲解这道题花了我不少时间，主要在于没有找到规律。螺线中有一条很重要的规律，臂长的增长是有规律的：1 1 2 2 3 3 …然后就是结束条件如何设定，这里我使用了堆满结果空间就返回的方式。Java代码class Solution { public int[][] spiralMatrixIII(int R, int C, int r0, int c0) { int[][] result = new int[RC][2]; int count=0; result[0] = new int[]{r0, c0}; int size=0; while(count<RC-1){ size++; for(int j=1;j<=size;j++){ c0 = c0+1; if(r0>=0 && c0>=0 && r0<R && c0<C){ result[++count] = new int[]{r0, c0}; if(count==RC-1){ return result; } } } for(int j=1;j<=size;j++){ r0=r0+1; if(r0>=0 && c0>=0 && r0<R && c0<C){ result[++count] = new int[]{r0, c0}; if(count==RC-1){ return result; } } } size++; for(int j=1;j<=size;j++){ c0 = c0-1; if(r0>=0 && c0>=0 && r0<R && c0<C){ result[++count] = new int[]{r0, c0}; if(count==RC-1){ return result; } } } for(int j=1;j<=size;j++){ r0=r0-1; if(r0>=0 && c0>=0 && r0<R && c0<C){ result[++count] = new int[]{r0, c0}; if(count==RC-1){ return result; } } } } return result; }} ...

题目Given a matrix A, return the transpose of A.The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.Example 1:Input: [[1,2,3],[4,5,6],[7,8,9]]Output: [[1,4,7],[2,5,8],[3,6,9]]Example 2:Input: [[1,2,3],[4,5,6]]Output: [[1,4],[2,5],[3,6]]Note:1 <= A.length <= 10001 <= A[0].length <= 1000题目地址讲解转置一个矩阵，简单。Java代码class Solution { public int[][] transpose(int[][] A) { int[][] result = new int[A[0].length][A.length]; for(int i=0;i<A.length;i++){ for(int j=0;j<A[i].length;j++){ result[j][i] = A[i][j]; } } return result; }}

题目We have a two dimensional matrix A where each value is 0 or 1.A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.Return the highest possible score.Example 1:Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]Output: 39Explanation:Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39Note:1 <= A.length <= 201 <= A[0].length <= 20A[i][j] is 0 or 1.题目地址讲解这道题我刚开始没看懂，我先入为主以为0和1的总数是不变的，你把多少个0变成1，就要把其他的相应个数的1变为0。后来看懂了，flip可以是行或者列，每个flip操作把该行或者列的所有0变成1，所有1变成0。然后每行看做一个二进制数，把所有行加起来作为返回结果。问怎么翻转结果才最大？看懂题目之后，我们来想一下，二进制数有个特点，第一个数比其他数加起来还重要，意思是比如：1000比0111还大。所以我们要让第一位变成1，不惜任何代价，哪怕其他三位全都因此变成0。第二步，我们要在保证第一步，也就是所有行首为1的前提下，再次优化。那么我就想到，按列进行优化，如果这一列的0比1多，就flip一下。Java代码class Solution { public int matrixScore(int[][] A) { for(int i=0;i<A.length;i++){ if(A[i][0]!=1){ flip(A[i]); } } for(int i=0;i<A[0].length;i++){ dealColumn(A, i); } int result=0; for(int i=0;i<A.length;i++){ int column=0; for(int j=0;j<A[0].length;j++){ System.out.print(A[i][j]); column <<= 1; if(A[i][j]==1){ column += A[i][j]; } } System.out.println("\n"); result += column; } return result; } private void flip(int[] A){ for(int i=0;i<A.length;i++){ if(A[i]==0){ A[i] = 1; }else{ A[i] = 0; } } } private void flipColumn(int[][] A, int columnNum){ for(int i=0;i<A.length;i++){ if(A[i][columnNum]==0){ A[i][columnNum]=1; }else{ A[i][columnNum]=0; } } } private void dealColumn(int[][] A, int columnNum){ int count=0; for(int i=0;i<A.length;i++){ if(A[i][columnNum]==0){ count++; } } if(count>A.length/2){ flipColumn(A, columnNum); } }} ...

Delete Columns to Make SortedWe are given an array A of N lowercase letter strings, all of the same length.Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.For example, if we have an array A = [“abcdef”,“uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”, “vyz”], and the remaining columns of A are [“b”,“v”], [“e”,“y”], and [“f”,“z”]. (Formally, the c-th column is [A[0][c], A[1][c], …, A[A.length-1][c]].)Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.Return the minimum possible value of D.length.Example 1:Input: [“cba”,“daf”,“ghi”]Output: 1Explanation: After choosing D = {1}, each column [“c”,“d”,“g”] and [“a”,“f”,“i”] are in non-decreasing sorted order.If we chose D = {}, then a column [“b”,“a”,“h”] would not be in non-decreasing sorted order.Example 2:Input: [“a”,“b”]Output: 0Explanation: D = {}Example 3:Input: [“zyx”,“wvu”,“tsr”]Output: 3Explanation: D = {0, 1, 2}Note:1 <= A.length <= 1001 <= A[i].length <= 1000这一题又是考察二维数组的操作，比较简单。涉及到一个很简单的算法就是：判断序列是否有序，最简单直接的判定是遍历一遍序列，只要后面一个数比前面一个数大，就是升序的，反之如果后面一个数都比前面一个数小，就是降序。需要考虑的边角条件（corner case）就是如果序列只有一个数，那么我们直接判定序列是有序的。java代码class Solution { public int minDeletionSize(String[] A) { int result = 0; char[][] a = new char[A.length][A[0].length()]; for(int i=0;i<A.length;i++){ a[i] = A[i].toCharArray(); } for(int i=0;i<a[0].length;i++){ if(!isNoDecreasing(a, i)){ result++; } } return result; } private boolean isNoDecreasing(char[][] c, int ColumnNums){ if(c[0].length<2){ return true; } for(int i=1;i<c.length;i++){ if(c[i-1][ColumnNums]>c[i][ColumnNums]){ return false; } } return true; }}