登录
原创

JS基础算法(数据结构之二维矩阵篇)

专栏JS算法基础篇
发布于 2020-12-15 阅读 368
  • 前端
  • 面试
  • 算法
原创

螺旋矩阵

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

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

示例 2:

输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

拆解成一步一步的,而且要拆成每一步是相同的
第一圈是第一行全部,第二行到倒数第二行是第一个和最后一个,最后一行全部,接着里面的作为一个新的矩阵,继续重复这个步骤。


[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12],
  [5, 6, 7, 8],
  [9,10,11,12]
]

export default (arr) => {
    // 处理每一圈的数据遍历过程
    let map = (arr, r = []) => {
        for (let i = 0, len = arr.length; i < len; i++) {
            // 第一行
            if (i === 0) {
                r = r.concat(arr[i])
            } else if (i === len - 1) {// 最后一行
                r = r.concat(arr[len - 1].reverse())
            } else {// 其它行最后一个
                r.push(arr[i].pop())
            }
        }
        // 去掉第一行
        arr.shift()
        // 去掉最后一行
        arr.pop()
        // 去掉剩余行的第一个,并放入结果数组
        for (let i = arr.length - 1; i >= 0; i--) {
            r.push(arr[i].shift())
        }
        // 还有其它行没处理
        if (arr.length) {
            return map(arr, r)
        } else {// 否则直接返回结果数组r
            return r
        }
    }
    return map(arr, [])
}

旋转图像

给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明:
你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵,使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

示例 2:

给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

原地旋转输入矩阵,使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

找到456这个轴,交换后再以753为轴,交换后即可

13.png

function rotateImg(arr){

}
export default (arr) => {
    // 获取n的维度
    let vecor = arr.length
        // 垂直翻转
    for (let i = 0, len = vecor / 2; i < len; i++) {
        for (let j = 0, tmp; j < vecor; j++) {
            tmp = arr[i][j]
            arr[i][j] = arr[vecor - i - 1][j]
            arr[vecor - i - 1][j] = tmp
        }
    }
    // 对角线翻转
    for (let i = 0; i < vecor; i++) {
        for (let j = 0, tmp; j < i; j++) {
            tmp = arr[i][j]
            arr[i][j] = arr[j][i]
            arr[j][i] = tmp
        }
    }
    return arr
}

评论区

timing
3粉丝

励志做一条安静的咸鱼,从此走上人生巅峰。

0

0

0

举报