Two dimensional array of "100 lectures on zero basis of algorithm"

catalogue

Lesson 3 matrix

1, Knowledge points

2, Title

1. Total assets of richest customers

2. Special position in binary matrix

3. Flip the image

4. Rotate the image

5. Transpose matrix

6. Convert one-dimensional array into two-dimensional array

7. Judge whether the matrix is consistent after rotation

8. Two dimensional network migration

9. Spiral matrix

Lesson 3 matrix

1, Knowledge points

1. Mathematically, matrix; Program, two-dimensional array.

2. The horizontal reversal of the matrix is to reverse the elements of each row of the matrix.

ret[i][j] = image [i] [c-1-j] C is imageColSize[0]

3. The vertical flip of the matrix is to reverse the elements of each column of the matrix.

4. Rotate the matrix clockwise. At this time, the rows and columns will exchange.

5. Transpose of matrix: rows and columns are exchanged, and the first column becomes the first row

ret[i][j] = matrix[j][i];

2, Title

1. Total assets of richest customers

1672. Total assets of richest customers - LeetCode (LeetCode CN. Com)

Function parameter transfer of two-dimensional array

```int diagonalSum(int** mat, int matSize, int* matColSize){

}```

matSize represents the number of rows, int *matColSize is a one-dimensional array, representing the number of columns,

matColSize[i] indicates that row I has column matColSize[i]

```int maximumWealth(int** accounts, int accountsSize, int* accountsColSize){
int m=accountsSize;
int n=accountsColSize[0];
int max=0;
for( int i=0;i<m;++i){
int sum=0;
for(int j=0;j<n;++j){
sum+=accounts[i][j];
}
if(sum>max)
max=sum;
}
return max;
}```
```class Solution {
public:
int maximumWealth(vector<vector<int>>& accounts) {
int max=0;
for(int i=0;i<accounts.size();i++){
int sum=0;
for(int j=0;j<accounts[i].size();j++){
sum+=accounts[i][j];
}
if(sum>max)
max=sum;
}
return max;
}
};```

2. Special position in binary matrix

1582. Special position in binary matrix - LeetCode (LeetCode CN. Com)

```int check(int** mat, int matSize, int matColSize, int r, int c) {
int i;
if(mat[r][c] != 1) {
return 0;
}
for(i = 0; i < matSize; ++i) {
if(i != r && mat[i][c]) {
return 0;
}
}//(1)
for(i = 0; i < matColSize; ++i) {
if(i != c && mat[r][i]){
return 0;
}
}//(2)
return 1;
}

int numSpecial(int** mat, int matSize, int* matColSize){
int i, j;
int sum = 0;
for(i = 0; i < matSize; ++i) {
for(j = 0; j < matColSize[i]; ++j) {
sum += check(mat, matSize, matColSize[i], i, j);
}
}
return sum;
}```

(1) Row r, column c, mat[r][c] is 1, then when ， I in mat[i][c] is not equal to r, the column is 0, and then the problem stem is satisfied. If ， mat[i][j] = = 1 ， and all other elements in row ， I ， are ， 0 ， and I= r & & mat[i][c] indicates the intersection of other rows except row r and column c. if there is 1, it will return 0, and if there is 1, it will not meet the problem stem

(2) Similarly (1)

```class Solution {
public:
int numSpecial(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
int ans = 0;
vector<int> rows(m, 0), cols(n, 0);
for(int i = 0; i < m; i ++){
for(int j = 0; j < n; j ++){
rows[i] += mat[i][j];
cols[j] += mat[i][j];
}
}
for(int i = 0; i < m; i ++){
for(int j = 0; j < n; j ++){
if(mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1){
ans ++;
}
}
}
return ans;
}
};

```

Mark how many 1s are in each row or column

3. Flip the image

832. Flip image - LeetCode (LeetCode CN. Com)

``` int **myMalloc(int r, int c, int* returnSize, int** returnColumnSizes) {
int i;
int **ret = (int **)malloc( sizeof(int *) * r );
*returnColumnSizes = (int *)malloc( sizeof(int) * r );
*returnSize = r;
for(i = 0; i < r; ++i) {
ret[i] = (int *)malloc( sizeof(int) * c );
(*returnColumnSizes)[i] = c;
}
return ret;
}/*Memory application template
The first malloc statement indicates to apply for the memory of a matrix. The number of rows is r, the first address is ret, and the type of the two-dimensional array is int * *. The type of each element in the two-dimensional array is a first-class pointer, that is, int *, which corresponds to the expression sizeof(int *);

The second malloc statement applies for an array for the column to record the number of columns in each row, so the length of this column array is r, which needs to be returned to the caller as a parameter, so the caller knows the reference

The third malloc statement applies for the memory space of each row of the matrix, and the length of each row is the number of columns c
*/
int** flipAndInvertImage(int** image, int imageSize, int* imageColSize, int* returnSize, int** returnColumnSizes){
int i, j;
int r = imageSize, c = imageColSize[0];
int **ret = myMalloc(r, c, returnSize, returnColumnSizes);
for(i = 0; i < r; ++i) {
for(j = 0; j < c; ++j) {
ret[i][j] = 1 - image[i][ c-1-j ];
}
}
return ret;
}```

4. Rotate the image

48. Rotating image - LeetCode (LeetCode CN. Com)

5. Transpose matrix

867. Transpose matrix - LeetCode (LeetCode CN. Com)

``` int **myMalloc(int r, int c, int* returnSize, int** returnColumnSizes) {
int i;
int **ret = (int **)malloc( sizeof(int *) * r );
*returnColumnSizes = (int *)malloc( sizeof(int) * r );
*returnSize = r;
for(i = 0; i < r; ++i) {
ret[i] = (int *)malloc( sizeof(int) * c );
(*returnColumnSizes)[i] = c;
}
return ret;
}

int** transpose(int** matrix, int matrixSize, int* matrixColSize, int* returnSize, int** returnColumnSizes){
int i, j;
int r = matrixColSize[0], c = matrixSize;     //Transpose matrix, row becomes column, column becomes row
int **ret = myMalloc(r, c, returnSize, returnColumnSizes);
for(i = 0; i < r; ++i) {
for(j = 0; j < c; ++j) {
ret[i][j] = matrix[j][i];
}
}
return ret;
}```

6. Convert one-dimensional array into two-dimensional array

2022. Transform one-dimensional array into two-dimensional array LeetCode (LeetCode CN. Com)

```   int **myMalloc(int r, int c, int* returnSize, int** returnColumnSizes) {
int i;
int **ret = (int **)malloc( sizeof(int *) * r );
*returnColumnSizes = (int *)malloc( sizeof(int) * r );
*returnSize = r;
for(i = 0; i < r; ++i) {
ret[i] = (int *)malloc( sizeof(int) * c );
(*returnColumnSizes)[i] = c;
}
return ret;
}
int** construct2DArray(int* original, int originalSize, int m, int n, int* returnSize, int** returnColumnSizes){
int **ret, i, j;
if (originalSize != n*m) {
*returnSize = 0;
return ret;
}
ret = myMalloc(m, n, returnSize, returnColumnSizes);
for(i = 0; i < m; ++i) {
for(j = 0; j < n; ++j) {
ret[i][j] = original[ i * n + j ];
}
}
return ret;
} ```

7. Judge whether the matrix is consistent after rotation

1886. Judge whether the matrix is consistent after rotation - LeetCode (leetcode-cn.com)

8. Two dimensional network migration

1260. Two dimensional mesh migration LeetCode (LeetCode CN. Com)

9. Spiral matrix

54. Spiral matrix - LeetCode (LeetCode CN. Com)

Keywords: Algorithm linear algebra

Added by Dustin013 on Sun, 06 Feb 2022 08:54:09 +0200