美文网首页
LeetCode 764. Largest Plus Sign

LeetCode 764. Largest Plus Sign

作者: 微微笑的蜗牛 | 来源:发表于2020-02-29 20:37 被阅读0次

    @(LeetCode)

    问题描述

    在一个二维的表格中,从 (0, 0)(N-1, N-1),每个格子里都包含一个 1,除了在 mines 中的格子除外,它包含 0。那么,由 1 组成的最大的十字符号是多少?返回十字符的阶数。如果不存在,返回 0

    k 阶由 1 组成的十字符定义如下:存在某个中心点 grid[x][y] = 1,且它的上下左右都有 k-1 个连续的 1。看下面的图形描述应该就很清楚了。

    1 阶:
    000
    010
    000
    
    2 阶:
    00000
    00100
    01110
    00100
    00000
    
    3 阶:
    0000000
    0001000
    0001000
    0111110
    0001000
    0001000
    0000000
    

    栗 1:

    输入:N = 5, mines = [[4, 2]]
    输出:2
    

    其中的一个十字符如下,用粗体标出:
    1 1 1 1 1
    1 1 1 1 1
    1 1 1 1 1
    1 1 1 1 1
    1 1 0 1 1

    栗 2:

    输入: N = 2, mines = []
    输出: 1
    

    栗 3:

    输入: N = 1, mines = [[0, 0]]
    输出: 0
    解释:不存在十字符,返回 0
    

    注意:

    1. N 是一个整数,且其范围在 [1, 500]
    2. mine 的长度至多 5000
    3. mine[i] 有 2 个元素,且为整数,其范围为 [0, N-1]

    想看英文原文的戳这里

    解题思路

    暴力解法

    这题最直观最容易想到的思路就是穷举遍历法。

    如果为 k 阶,则中心点四周的 1 的长度为 k - 1

    • k = 1,只要 grid 中存在 1 即满足。
    • k = 2,那么至少需要上下各留一行,左右各留一列才能满足。即 x >= 1 && x <= N - 2y >= 1 && y <= N - 2
    • 同理,当 k = 3,上下至少需要各留 2 行,左右各留 2 列才满足。即 x >= 2 && x <= N - 3y >= 2 && y <= N - 3

    因此 ,当为 k 阶时可以推导出如下限制条件:
    x >= k && x <= N - k - 1y >= k && y <= N - k - 1。逐个遍历 x, y 的取值,判断是否能满足条件。

    判断是否能组成十字符也挺简单,分别从中心点往上下左右四个方向,找出是否存在 k - 1 个连续的 1 即可。

    若矩阵为 N * N,那么其最大的阶数为:maxOrder = (N - 1) / 2 + 1

    那么我们可以从最大阶数往下遍历,只要满足条件,则直接返回当前阶数即可。

    代码如下:

    /**
     * @param {number} N
     * @param {number[][]} mines
     * @return {number}
     */
    // Time Limit Exceeded
    var orderOfLargestPlusSign = function(N, mines) {
    
        // 预处理 mines
        let map = new Map()
        mines.map((array) => {
            if (array.length === 2) {
                const key = `${array[0]}-${array[1]}`
                map.set(key, true)
            }
        })
    
        let maxOrder = Math.floor((N - 1) / 2) + 1
    
        let k = maxOrder
        let i, j
        while (k >= 1) {
    
            for (i = k - 1; i <= N - k; i++) {
                for (j = k - 1; j <= N - k; j++) {
                    // 计算是否满足条件
                    if (hasPlusSign(i, j, k, map)) {
                        return k
                    }
                }
            }
    
            k -= 1
        }
    
        return 0
    };
    
    var hasPlusSign = function(i, j, k, map) {
         // 计算是否满足条件
         const key = `${i}-${j}`
         if (!map.has(key)) {
             // 左
             let m = j - 1
             while (m >= j - (k - 1)) {
                 const key = `${i}-${m}`
    
                 // 为 0,不满足
                 if (map.has(key)) {
                     return false
                 }
                 m -= 1
             }
    
             // 右
             m = j + 1
             while (m <= j + (k - 1)) {
                 const key = `${i}-${m}`
    
                 // 为 0,不满足
                 if (map.has(key)) {
                     return false
                 }
                 m += 1
             }
    
             // 下
             m = i - 1
             while (m >= i - (k - 1)) {
                 const key = `${m}-${j}`
    
                 // 为 0,不满足
                 if (map.has(key)) {
                     return false
                 }
                 m -= 1
             }
    
             // 下
             m = i + 1
             while (m <= i + (k - 1)) {
                 const key = `${m}-${j}`
    
                 // 为 0,不满足
                 if (map.has(key)) {
                     return false
                 }
                 m += 1
             }
    
             return true
         }
    
         return false
    }
    

    但是很可惜,这种解法会出现 Time Limit Exceeded,因为时间复杂度太高了,为 O(n^3)

    以上代码可查看 暴力解法

    动态规划

    换个思路,其实一个中心点的最大阶数是由其上下左右最短的 1 的长度决定的。所以我们只需要求出每个点的最大阶数,遍历即可。

    而求每个点的最大阶数,需要算出其上下左右 1 的长度才能得到。如果对于每个点,分别去求四个方向的长度,计算量还是比较大。

    其实对于 grid[i][j],假设其左边的长度为 l。那么对于它右边的格子 grid[i][j+1] 来说,如果其值为 0,则长度为 0;如果其值为 1,则长度为 l+1。这就是使用动态规划的思想,根据前一个值来进行计算,减少重复工作,真是比较妙啊。

    以计算左边长度为例,其状态转移方程为:

    // left[i][j] 存储点 (i, j) 左边的长度
    若 grid[i][j] == 0, 则 left[i][j] = 0
    若 grid[i][j] == 1,则 left[i][j] = left[i][j-1] + 1
    

    举个栗子:

    假设矩阵某一行为 11101,那么每个数对应的左边长度为 12301。从最左开始遍历,根据前一个值累加。

    同理,右边的长度则从最右开始遍历累加,为 32101

    对于某一列来说:

    1
    0
    1
    1
    

    上边的长度从最上开始计算,结果为:

    1
    0
    1
    2
    

    下边的长度从最下开始计算,结果为:

    1
    0
    2
    1
    

    这样就可以分别出计算上下左右的长度,取最小的长度即为当前点的最大阶数。这样一看,可能需要四个数组来保存上下左右的长度值,但是优化后,只需要一个数组。

    比如我们先计算出左边的长度 l 保存下来,当在计算右边长度 r 时,只需计算 min(l, r) ,这样始终只记录最小的长度。在计算上边/下边长度时也一样。

    当计算第四个方向时,这时已经知道当前点的阶数,整体最大阶数与其进行比较即可。

    因此,大致思路为:

    • 对于一行,从左往右遍历,计算左边长度;从右往左遍历,计算右边长度
    • 对于一列,从上往下遍历,计算上边长度;从下往上遍历,计算下边长度
    • 始终记录最小长度
    • 计算完成,得到当前点阶数。最大阶数与其进行比较,进行更新

    代码如下:

    /**
     * @param {number} N
     * @param {number[][]} mines
     * @return {number}
     */
    // Time Limit Exceeded
    var orderOfLargestPlusSign = function(N, mines) {
    
        // 预处理 mines
        let map = new Map()
        mines.map((array) => {
            if (array.length === 2) {
                const key = `${array[0]}-${array[1]}`
                map.set(key, true)
            }
        })
    
        // 初始化数组为 0
        let dp = new Array()
        for (let r = 0; r < N; r++) {
            let array = new Array()
            for (let c = 0; c < N; c++) {
                array.push(0)
            }
            dp.push(array)
        }
    
        let maxOrder = 0
        // 以行遍历
        for (let r = 0; r < N; r++) {
            let len = 0
            // 计算左边
            for (let c = 0; c < N; c++) {
                const key = `${r}-${c}`
                if (map.has(key)) {
                    len = 0
                } else {
                    len += 1
                }
    
                dp[r][c] = len
            }
    
            // 计算右边
            len = 0
            for (c = N - 1; c >= 0; c--) {
                const key = `${r}-${c}`
                if (map.has(key)) {
                    len = 0
                } else {
                    len += 1
                }
    
                // 这里记录最小长度
                dp[r][c] = Math.min(len, dp[r][c])
            }
        }
    
        // 以列遍历
        for (let c = 0; c < N; c++) {
            let len = 0
            // 计算上边
            for (let r = 0; r < N; r++) {
                const key = `${r}-${c}`
                if (map.has(key)) {
                    len = 0
                } else {
                    len += 1
                }
    
                // 这里记录最小长度
                dp[r][c] = Math.min(len, dp[r][c])
            }
    
            // 计算下边
            len = 0
            for (r = N - 1; r >= 0; r--) {
                const key = `${r}-${c}`
                if (map.has(key)) {
                    len = 0
                } else {
                    len += 1
                }
    
                // 这里记录最小长度
                dp[r][c] = Math.min(len, dp[r][c])
    
                // 最后一个方位计算完毕,则可确定该点的 order
                maxOrder = Math.max(maxOrder, dp[r][c])
            }
        }
    
        return maxOrder
    }
    

    以上代码可查看 动态规划解法

    相关文章

      网友评论

          本文标题:LeetCode 764. Largest Plus Sign

          本文链接:https://www.haomeiwen.com/subject/cylvhhtx.html