前端算法题 | 这道题效率最高的算法，你可能不知道？

zgbgx 发布于2019-08-23 13:42 / 2010人阅读

摘要：当循环到的时候，记录一下这个最后一次出现的位置在哪里。最后，这道算法题的出处来自里面有各种各样的实现方法，可以作为参考。觉得本文对你有帮助请分享给更多人关注妙味前端加星标，关注更多内容

寻找最长的不含有重复字符的子串

可能看标题不会明白这个题到底什么意思，来看看下面的例子：

abcabcbb ➡ abc ➡ 3

bbbb ➡ b ➡ 1

pwwkew ➡ wke ➡ 3

看了栗子是不是明白了呢？

其实需求很简单，实现的方法也很多，不过在这里我要来写一种效率最高的算法，只需要一次循环就可解决：

function findNoRepeatMaxLenStr (str) {
  let lastPositions = {}
  let start = 0
  let maxLen = 0

  for (let i=0; i= start) {
              start = lastPositions[s] + 1
        }
        if (i - start + 1 > maxLen) {
              maxLen = i - start + 1
        }
    lastPositions[s] = i
  }
  return maxLen
}

// test
console.log(findNoRepeatMaxLenStr("abcabcbb"))  // 3

那么看完代码，请自己先胡思乱想一下，能看得懂不？
…

行了，看到这我就知道你没看懂，那么来解释一下吧。
思路是这样的，假如下面的图形是一个字符串，每个格子代表一个字符：

此时咱们开始使用 for 循环扫描整个字符串，当扫描到 x（x 代表任意位置的任意的字符串）的时候，那么咱们应该怎么做呢？

首先要记录一个 start 起始位置，当然一开始就是 0 了，那么 start 在循环中不仅仅只是表示字符串从 0 开始，还表示当前不含有最长重复子串的开始，那么咱们要做的事情就一件：保证从 start 到 x 之间没有重复的字符串，再说的通俗点就是看检查 start 到 x 之间有没有重复的 x 。

那么怎么做到检查这个动作呢?

这个时候 lastPositions 就派上用场了。当循环到 x 的时候，记录一下这个 x 最后一次出现的位置在哪里。

那么记录完毕之后，当进行检查 start 到 x 之间是否有重复的 x 的时候，咱们就去问 lastPositions[x]，此时会有2种情况：

第一种情况是 x 从来没有出现过或者出现在了 start 之前；

第二种情况是 x 出现在 start 到 x 中间。

那么对于第一种情况，咱们不用去管。而第二种情况自然是不满足条件的情况了，此时，咱们就要更新 lastPositions[x]，将这个 x 的位置更新为 lastPositions[x] + 1。

总结下来就是：

lastPositions[x] 不存在或 < start 满足条件，无需操作

lastPositions[x] 存在并且 >= start 不满足条件，更新 lastPositions[x]++

那么在结合上面的代码，逻辑就清晰了，唯一有些绕圈圈的地方就是第二个 if 中的 +1 操作，原因就是字符串的索引是从 0 开始的，那么假如第一个为 x 满足条件，实际索引是0，那么长度应该是 0 + 1 = 1。

最后，这道算法题的出处来自：

https://leetcode.com/problems...

里面有各种各样的实现方法，可以作为参考。

觉得本文对你有帮助？请分享给更多人

关注【妙味前端】加星标，关注更多内容

GPU云服务器云服务器可能不知道地方最难的算法题最小二乘拟合的算法效率最高频率单词算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/99409.html

一道有意思的面试算法题

摘要：解决方案异或操作异或运算是对于二进制数字而言的，比如说一个有两个二进制，如果两个值不相同，则异或结果为。比如说，本质上其实是和的每一对比特位执行异或操作，等价于下面数字对应的二进制数字对应的二进制数字对应的二进制因此的结果就为啦。新年第一篇文章，先祝大家新年快乐！！那么接下来进入正文。前言前阵子突发奇想，突然开始刷leetcode。其中刷到了一道有意思的题目，发现这道题是当时秋招...

maxmin 2019-08-23 14:28 评论0 收藏0
一道看似简单的面试题

摘要：二进制本身就是为这个数字而使用的，所以说这道面试题直指二进制的使用是没错的。正负在二进制中，第一位为的是负数，是正数。 showImg(https://segmentfault.com/img/bVbd7d0?w=1580&h=732); 前言使用PHP,给定一个数,判断这个数是否是二的N次方这样看似简单的一个面试题, 实际牵出了很多基础知识,本章在为大家补习基础知识的情况下来解答...

kid143 2019-07-01 10:21 评论0 收藏0
从一道前端面试题谈起

摘要：但是题目非要弄成链表的形式，说实在的，我真没有见过前端什么地方还需要用链表这种结构的除了面试的时候，所以说这种题目对于实际工作是没什么用处的，但是脑筋急转弯的智商题既然这样出了，我们就来看看怎么解决它吧。今天在知乎上看到一个回答《为什么前端工程师那么难招？》，作者提到说有很多前端工程师甚至连单链表翻转都写不出来。说实话，来面试的孩子们本来就紧张，你要冷不丁问一句单链表翻转怎么写，估计...

darkbaby123 2019-08-23 17:53 评论0 收藏0
前端--通用知識 - 收藏集 - 掘金

摘要：闭包有多重前端知识点大百科全书前端掘金，，技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 Vue全家桶实现还原豆瓣电影wap版 - 掘金用vue全家桶仿写豆瓣电影wap版。最近在公司项目中尝试使用vue，但奈何自己初学水平有限，上了vue没有上vuex，开发过程特别难受。于是玩一玩本项目，算是对相关技术更加熟悉了。原计划仿写完所有页面，碍于豆瓣的接口API有限，实现页面也有...

王笑朝 2019-08-20 16:57 评论0 收藏0