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] 子串的信息上就好了。
顺着这个思路再试试看?
继续加油!:)
132022-12-14
相似问题