关于算法:2125银行中的激光束数量-算法leetode附思维导图-全部解法300题

27次阅读

共计 2284 个字符,预计需要花费 6 分钟才能阅读完成。

零 题目:算法(leetode,附思维导图 + 全副解法)300 题之(2125)银行中的激光束数量

一 题目形容



二 解法总览(思维导图)

三 全副解法

1 计划 1

1)代码:

// 计划 1“间接计数 - 模拟法”。// 思路:// 1)状态初始化:map 寄存每一层寄存 安全设备 的状况。// 2)外围 1:遍历 bank 的每一层。// 2.1)遍历以后层的每一列。// 2.1.1)若 i 层的 j 列 为 安全设备,则 通过 map、对 相应的值进行 +1 操作。// 3)外围 2:2 层遍历。// 3.1)若 以后 i、j 层均存在安全设备 且 介于 (i, j) 层 均无安全设备,// 则 resCount += (map.get(i) * map.get(j))。// 4)返回后果 resCount。var numberOfBeams = function(bank) {
    // isValid 办法:介于 top、bottom 均没有安全设备,阐明是“非法的”。const isValid = (top, bottom, map) => {
        let resBool = true;

        for (let i = top + 1; i < bottom; i++) {if (map.get(i)) {
                resBool =  false;
                break;
            }
        }

        return resBool;
    };

    // 1)状态初始化:map 寄存每一层寄存 安全设备 的状况。const l = bank.length;
    let map = new Map(),
        resCount = 0;

    // 2)外围 1:遍历 bank 的每一层。for (let i = 0; i < l; i++) {const tempStr = bank[i],
            tempStrLength = tempStr.length;
        
        // 2.1)遍历以后层的每一列。for (let j = 0; j < tempStrLength; j++) {
            // 2.1.1)若 i 层的 j 列 为 安全设备,则 通过 map、对 相应的值进行 +1 操作。if (tempStr[j] === '1') {if (map.has(i)) {map.set(i, map.get(i) + 1);
                }
                else {map.set(i, 1);
                }
            }
        }
    }

    // 3)外围 2:2 层遍历。for (let i = 0; i < l; i++) {for (let j = i + 1; j < l; j++) {// 3.1)若 以后 i、j 层均存在安全设备 且 介于 (i, j) 层 均无安全设备,// 则 resCount += (map.get(i) * map.get(j))。if (map.get(i) && map.get(j) && isValid(i, j, map)) {resCount += (map.get(i) * map.get(j));
            }
        }
    }

    // 4)返回后果 resCount。return resCount;
};

2 计划 2

1)代码:

// 计划 2“简洁的 1 次遍历法”。// 思路:// 1)状态初始化:pre = 0, resCount = 0。// 2)外围 1:从 [0, l-1] 遍历 bank 的每一层。// 2.1)取得以后 i 层 的安全设备个数。// 2.2)若 以后 i 层 的安全设备个数 大于 0,则 resCount += pre * cur; pre = cur。// 3)返回后果 resCount。var numberOfBeams = function(bank) {
    // getCountByLevel 办法:获取 bank 的 level 层 的安全设备个数。const getCountByLevel = (level) => {const tempStr = bank[level],
            tempStrLength = tempStr.length;
        let resNum = 0;

        for (let i = 0; i < tempStrLength; i++) {if (tempStr[i] === '1') {resNum++;}
        }

        return resNum;
    };

    // 1)状态初始化:pre = 0, resCount = 0。const l = bank.length;
    let pre = 0,
        resCount = 0;

    // 2)外围:从 [0, l-1] 遍历 bank 的每一层。for (let i = 0 ; i < l; i++) {
        // 2.1)取得以后 i 层 的安全设备个数。const cur = getCountByLevel(i);
        // 2.2)若 以后 i 层 的安全设备个数 大于 0,则 resCount += pre * cur; pre = cur。if (cur > 0) {
            resCount += pre * cur;
            pre = cur;
        }
    }

    // 3)返回后果 resCount。return resCount;
}

3 计划 3

1)代码:

// 计划 3“4 行代码(因为有 4 个分号)- 装 X 法”。// n 个元素 变成 1 个元素 ---> 优先思考数组的 reduce 办法。// 思路:// 1)通过 数组的 map 办法,计算 bank 的每层安全设备个数 —— 顺次寄存入数组(“假设其名为 tempList”)中,
// 2)通过 数组的 reduce 办法,一直依据 以后层的安全设备个数(cur)、更新 以后激光束的总数量(acc)并返回。var numberOfBeams = function(bank) {
    let pre = 0;

    return bank.map(item => item.split('').filter(itemInner => itemInner ==='1').length)
        .reduce((acc, cur) => {if (cur > 0) {
                // 注:这 1 行 等同于 上面 2 行代码。[acc, pre] = [acc + (pre * cur), cur];
                // acc += pre * cur;
                // pre = cur;
            }
            return acc;
        }, 0);
}

四 资源分享 & 更多

1 历史文章 – 总览

2 博主简介

码农三少,一个致力于编写 极简、但齐全题解(算法 )的博主。
专一于 一题多解、结构化思维,欢送一起刷穿 LeetCode ~

正文完
 0