Leetcode 1781 传统遍历方法超时

来源:1-5 大厂面试为什么总考算法?

甲骨文_0001

2022-12-12

老师,我做了今日一题,还是用的朴素的遍历方法,因为直观直接, 哈哈哈,leetcode是报了超时,然后我也看了您的代码,没领会。。。
图片描述

/**
 * @param {string} s
 * @return {number}
 */
var beautySum = function(s) {
    let res = 0; // 存放结果
    for( let i = 0; i < s.length; i ++ ){
        // [i, j]之前的美丽值
        let map = {};
        for( let j = i; j < s.length; j ++ ){
            // [i, j]
            // 得到出现频率最高的次数与频率最低的次数
            for( let k = i; k <= j; k ++ ){
                let nowCh = s[k];
                map[nowCh] = map[nowCh] || 0;
                map[nowCh]++;

            } // for k

            // 在map中找到 => 出现频率最高的次数与频率最低的次数
            let arr = Object.entries(map);
            arr.sort((a, b)=>b[1]-a[1]); // 排序
            res += (arr[0][1] - arr[arr.length-1][1]);

            map = {}; // 处理完 [i, j]这一段子字符串后,map清空
        } // for j

    } //for i
    return res;
};

==========================更新1 =================================

    let res = 0; // 存放结果
    for( let i = 0; i < s.length; i ++ ){
        // [i, j]之前的美丽值
        let map = {};
        for( let j = i; j < s.length; j ++ ){
            let nowCh = s[j];
            map[nowCh] = map[nowCh] || 0; // 对nowCh未出现的情况初始化为0
            map[nowCh] ++;

            // 在map中找到 => 出现频率最高的次数与频率最低的次数
            let arr = Object.entries(map);
            arr.sort((a, b)=>b[1]-a[1]); // 排序
            res += (arr[0][1] - arr[arr.length-1][1]);

        } // for j

    } //for i
    return res;
};

图片描述

写回答

1回答

liuyubobobo

2022-12-13

你的算法即使不计算 map 的复杂度,也至少是 n^3 的级别。500^3 = 1.25*10^8,肯定超时。(回忆一下,在这个课程中我介绍过,一般 10^7 这个级别已经撑死了。)


在你的算法中,i 是遍历的子串的起始位置;j 是遍历的子串的终止位置。k 每次在 [i, j] 之间再遍历一次,实际上,每次 j 向后移动 1,即考虑 [i, j + 1] 的时候,k 没必要从 i 重新遍历一次,直接把 j + 1 位置的信息添加到 [i, j] 子串的信息上就好了。


顺着这个思路再试试看?


继续加油!:)

1
3
甲骨文_0001
回复
liuyubobobo
谢谢老师,您很专业,我受益匪浅: )
2022-12-14
共3条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程