这里记录在 freeCodeCamp 遇到的一些问题和解法。
无重复字符的最长子串
longest-substring-without-repeating-characters
题目:给定一个字符串,找出不含有重复字符的最长子串的长度。
示例
1 | // 输入: "abcabcbb" |
一、暴力解法
逐个检查所有子字符串,判断是否含有重复的字符;
就通过逐个检查就能想到这个方法肯定有很多层循环,还是一个一个的判断很消耗时间,虽然最终也能拿到正确的值,但是其时间复杂度很大。
1 | // 判断给定的子串是否包含重复字符 |
时间复杂度: O(n^3)
i循环,j循环,isUnquie中的循环,3次循还嵌套
时间复杂度很高,容易超时
二、滑动窗口解法
滑动窗口,通过字面意思猜出一个大概,应该是把一个空间类似为窗口的移动,一段一段的进行操作;
其具体的说法是:
滑动窗口是数组/字符串问题中常用的抽象概念;
窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)(左闭,右开);
而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i, j) 向右滑动1个元素,则它将变为 [i+1, j+1)(左闭,右开)。
回到问题:
通过找到定义字符到索引的映射,当我们找到重复的字符时,我们可以立即跳过该窗口。
也就是说,如果 s[j] 在 [i, j) 范围内有与 j有重复的字符,我们不需要逐渐增加 i 。 我们可以直接跳过 [i,j) 范围内的所有元素,并将 i 变为 j + 1。
1 | function childStrMaxLenNumEvent(strData) { |
时间复杂度: O(n),只有索引 j 迭代了一遍,比暴力法好多了
最长回文子串
之前在其他地方,看到了这样的一道题目
题目描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:
输入: “cbbd”
输出: “bb”
回文是在回文中心两侧互为镜像,因此,可以从它的中心展开,并且2n-1个中心。使用中心扩展法
1 | function longestPalindrome(s) { |
- 本文作者: Jambo
- 版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!