校园二手物品交易网站怎么做,网站开发技术与应用课程设计,discuz做服务网站,wordpress终极用户中心前段时间和小米的某面试官聊天。因为我一直在做 算法文章 的更新#xff0c;就多聊了几句算法方面的知识。
并且在聊天过程中获得了一个“重要情报”#xff1a;只要他来面试#xff0c;基本上每次的算法题#xff0c;都会去考察关于 子串和子序列 的问题。
的确#xf…前段时间和小米的某面试官聊天。因为我一直在做 算法文章 的更新就多聊了几句算法方面的知识。
并且在聊天过程中获得了一个“重要情报”只要他来面试基本上每次的算法题都会去考察关于 子串和子序列 的问题。
的确如果说哪种算法更容易在面试中被考察到子串、子序列 的问题想必能排在 数一数二 的位置上。 在之前的 「动态规划」 系列文章中我们讲到了 最长公共子序列 和 最长回文子序列 的问题今天我们继续来探讨力扣上一个关于 子串 的问题。
3.无重复字符的最长子串
给定一个字符串 s 请你找出其中 不含有重复字符 的 最长 子串 的长度。 示例 1 输入 s “abcabcbb” 输出 3 解释 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2: 输入 s “bbbbb” 输出 1 解释 因为无重复字符的最长子串是 “b”所以其长度为 1。 小 tips 要注意分清楚子串 和 子序列 的区别哟~ 子串 必须连续子序列 可以不连续 思路分析
这里回顾一个 重要思想 对于 子串和子序列 的题目可以按如下方式进行思考 考虑 以 i 位置为结尾 的情况下答案如何选取 该思想在 数组求和-2 这篇文章中也有提到哦~
因此对于本题来说
考虑若以每个位置作为结尾时子串能够向前延伸多长最长的子串长度就是我们要求的答案。
那么问题就进一步转化为
在给定一个结尾的字符时应该如何向前延伸呢延伸的长度会受到哪些因素影响呢
稍加思考
由于要找到最长无重复的子串因此一定与该字符 相同的前一个字符 的位置有关。 例如假设 3 到 8 下标之间没有再出现a字符则以 9 号下标为结尾的a字符往前延伸的距离最多只能到下标 3 处。
除了因素 1 外也与该字符的 前一个字符 向前延伸的位置有关。 同样例子假设下标为 9 的a字符的前一个字符是b 6 到 7 下标之间没有再出现b字符则以 8 号下标为结尾的b字符往前延伸的距离最多只能到下标 6 处。进而导致了下标为 9 的a字符往前延伸的距离最多也只能到下标 6 处。
确定了影响最终答案的因素后思路便豁然开朗了
两个因素中结果较大的下标即为该位置所能扩充的最远距离。
需要解决能够找到前一个相同字符下标的方法使用map设置存储前一个字符 最远能够向前扩充的下标 变量。取 12 中 较大的下标 即为该位置字符的答案。
代码
public static int lengthOfLongestSubstring(String s) {if (s null || s.equals()) {return 0;}char[] str s.toCharArray();// 这里并没有直接使用 map , 与 map 功能类似// 该 map 数组中存放的是 该字符 上一次出现时 的 下标int[] map new int[256];for (int i 0; i 256; i) {map[i] -1;}// 最新的答案即此前最长的子串长度int len 0;// 前一个字符能够向前扩充的最远位置在哪int pre -1;// 当前位置字符能够向前扩充的最远位置在哪int cur 0;for (int i 0; i ! str.length; i) {// 取两个因素中的最大值pre Math.max(pre, map[str[i]]);// 此时能够扩充的最大距离cur i - pre;// 更新答案len Math.max(len, cur);// 更新最新该字符出现的位置map[str[i]] i;}return len;
}理解了本题的思想之后上述代码也不难看懂。小伙伴们仔细思考一下哟
写在最后
前面的算法文章更新了许多 专题系列 。包括滑动窗口、动态规划、加强堆、二叉树递归套路 等。
还没读过的小伙伴可以关注同名号在主页中点击对应链接查看哦~
接下来的一段时间将持续 「力扣高频题」 系列文章想刷 力扣高频题 的小伙伴也可以关注一波哦 ~
~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~
关注 回复「ACM紫书」获取 ACM 算法书籍 ~ 回复「算法导论」获取 算法导论第3版 ~
在看 转发
让你的小伙伴们一起来学算法吧
