2021 年 08 月 03 日

这是我参与8月更文挑战的第3天,活动详情查看:8月更文挑战

本文题目全部来自 LeetCode

使用 Typescript

本篇文章全部收藏于专栏 3周攻克数据结构-LeetCode

本文所有代码和解题步骤将放置 GitHub仓库

DAY4

1. 重塑矩阵

在MATLAB中,有一个非常有用的函数 reshape,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。

给出一个由二维数组表示的矩阵,以及两个正整数r和c,分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。

示例 1:

输入: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
输出: 
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
示例 2:

输入: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
输出: 
[[1,2],
 [3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
注意:

给定矩阵的宽和高范围在 [1, 100]。
给定的 r 和 c 都是正数。
重塑矩阵1 重塑矩阵2

方法1:双循环

  1. 拍平数组
  2. 按照行数r,列数c 重新排列
function matrixReshape(mat: number[][], r: number, c: number): number[][] {
    // 拍平二维数组
    let newMat: any = mat.flat()
    
    // 判断个数是否一致,一致才能重塑
    if (r * c !== newMat.length) return mat

    // r 行
    for (let i = 0; i < r; i++) {
        const item: number[] = []
        // 每行c个
        for (let j = 0; j < c; j ++){
            // 将c个元素从头部拿出,并放入暂存的item数组
            item.push(newMat.shift(newMat[i]))
        }
        // 当前行收集完毕,推入新数组的尾部
        newMat.push(item);
    }

    return newMat
};

方法2:二维数组一维表示

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;
};

2. 杨辉三角

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

PascalTriangleAnimated2

方法1:2层遍历求解

杨辉三角非常有意思,我们很容易就可以找到呀的规律

  1. 每行的第一个元素和最后一个元素永远不会是上一层的和,因为他永远都是1
  2. 下一层的值(x),位置(y) 取决上一层的和 得出公式:
x = 当前值
y = 层数
z = 位置

x = y - 1 [ z -1 ] + y - 1 [ z + 1 ]
function generate(numRows: number): number[][] {
    const ret = []
    for(let i = 0; i < numRows; i++) {
        // 创建行,用 1 填充
        const row = new Array(i + 1).fill(1);
        // 填充每一行数据,左右2边不填充, 从 1 开始,结束于倒数第二个
        for (let j = 1; j < row.length - 1; j++){
            // 当前的值 = (上一行的当前个 - 1 [上一个] 值  ) + ( 上一行的当前个数 [下一个] 值 )
            row[j] = ret[i - 1][j - 1] + ret[i - 1][j];
        }
        // 添加当前行
        ret.push(row);
    }

    return ret;
};

科普篇:杨辉三角

注:图片来自网络

要想画杨辉三角,先把 "1" 方在顶点,然后连续在下面按三角形的模式放上数字。
每个数是它上面两个数的和

image.png

规律

image.png

第一条对角线全是 "1"
下一条对角线是 [正整数]
第三条对角线是 [三角形数]
第四条对角线是 [四面体数]

对称

杨辉三角形左右2边是对称的

image.png

每行的和

每行的和是上一行的和的 两倍 (2^2)

内容有很多就不一一列举了,感兴趣的朋友可以去了解下


© 2021, 滇ICP备19003866号本网站版权归本站作者Ruoduan所有原创文章遵循CC BY-SA 4.0授权许可,转载请注明出处