This is the third day of my participation in the August More text Challenge. For details, see:August is more challenging

The title of this article is all from LeetCode

Use the Typescript

This article is part of the column 3 Week Conquer Data structure-Leetcode

All the code and problem-solving steps in this article will be placed in the GitHub repository

DAY4

1. Reshape the matrix

In MATLAB, there is a very useful function 0, which can reshape one matrix into another new matrix of a different size, but keep its original data. Given a matrix represented by a two-dimensional array, and two positive integers, R and C, representing the number of rows and columns of the desired reconstructed matrix. The reconstructed matrix needs to fill all the elements of the original matrix in the same row traversal order. 0. If the shape operation with the given parameters is feasible and reasonable, output the new reshaping matrix; Otherwise, output the original matrix. Example 1: input: nums = [[1, 2], [3, 4]] r = 1, c = 4 output: [[1, 2, 3, 4]] : traveled through the nums as a result of [1, 2, 3, 4]. The new matrix is going to be a 1 by 4 matrix, and the new matrix is going to be filled row by row with the values of the previous elements. Example 2: input: nums = [[1,2], [3,4]] r = 2, c = 4 output: [[1,2], [3,4] explanation: there is no way to convert a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix. Note: the width and height range of the given matrix is [1, 100]. You're given positive r and positive c.Copy the code

Method 1: Double loop

  1. Pat down array
  2. According to the number of rowsrThe number of columnscRearrange the
function matrixReshape(mat: number[][], r: number, c: number) :number[] []{
    // Beat flat the two-dimensional array
    let newMat: any = mat.flat()
    
    // Determine whether the number is consistent
    if(r * c ! == newMat.length)return mat

    / / r line
    for (let i = 0; i < r; i++) {
        const item: number[] = []
        // Each row contains c
        for (let j = 0; j < c; j ++){
            // Remove the c elements from the header and put them into the temporary item array
            item.push(newMat.shift(newMat[i]))
        }
        // When the current row is collected, push it to the end of the new array
        newMat.push(item);
    }

    return newMat
};
Copy the code

Method 2: One-dimensional representation of a two-dimensional array

function matrixReshape(mat: number[][], r: number, c: number) :number[] []{
    const m = mat.length;
    const n = mat[0].length;
    if(m * n ! = r * c) {return mat;
    }

    const ans = new Array(r).fill(0).map(() = > new Array(c).fill(0));
    for (let x = 0; x < m * n; ++x) {
        ans[Math.floor(x / c)][x % c] = mat[Math.floor(x / n)][x % n];
    }
    return ans;
};
Copy the code

2. Yang Hui triangle

Given a non-negative integer numRows, generate the former numRows rows of the Poplar triangle. Example: input: 5 output: [[1], [1, 1], [1, 2, 1],,3,3,1 [1], [1,4,6,4,1]]Copy the code

Method 1:2 layer traversal solution

Yang Hui triangle is very interesting, we can easily find the law of ah

  1. The first and last element in a row will never be the sum of the previous levels, because it will always be 1
  2. The value of the next layer (x), the position (y) depends on the sum of the previous layers

The formula is:

X = current value y = Number of layers z = position x = y-1 [z-1] + y-1 [z + 1]Copy the code
function generate(numRows: number) :number[] []{
    const ret = []
    for(let i = 0; i < numRows; i++) {
        // Create rows and fill them with 1
        const row = new Array(i + 1).fill(1);
        // Fill each row, starting at 1 and ending at the penultimate
        for (let j = 1; j < row.length - 1; j++){
            // Current value = (current value of previous row - 1 [previous] value) + (current value of previous row [next] value)
            row[j] = ret[i - 1][j - 1] + ret[i - 1][j];
        }
        // Add the current row
        ret.push(row);
    }

    return ret;
};
Copy the code

Popular Science: Yang Hui triangle

Note: Pictures from the Internet

To draw Yang Hui's triangle, first place the "1" square at the vertex, then continuously place the numbers below in a triangular pattern. Each number is the sum of the two numbers above itCopy the code

regular

The first diagonal is all 1's, the next diagonal is positive integer, the third diagonal is triangle number, and the fourth diagonal is tetrahedron number.Copy the code

symmetry

The left and right sides of a Yanghui triangle are symmetric

Each row and

The sum of each row is twice the sum of the previous row (2^2).

There are a lot of content is not a list, interested friends can go to understand