LN : leetcode 3 Longest Substring Without Repeating Characters
2024-08-23 16:05:00
lc 3 Longest Substring Without Repeating Characters
3 Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
- Given "abcabcbb", the answer is "abc", which the length is 3.
- Given "bbbbb", the answer is "b", with the length of 1.
- Given "pwwkew", the answer is "wke", with the length of 3. Note that
the answer must be a substring, "pwke" is a subsequence and not a
substring.
动态规划 Accepted##
index数组用来标记该位是否第一次出现,invalid变量用来表示当前研究的子串头部的前一位,length用来表示当前研究的子串的长度。用动态规划的方法可以把时间复杂度降到最低的O(n)。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> index(256, -1);
int length =0;
for (int invalid = 0, i = 0; i < s.length(); i++) {
invalid = max(index[s[i]]+1, invalid);
index[s[i]] = i;
length = max(length, i-invalid+1);
}
return length;
}
};
最新文章
- Android笔记——Application的作用
- datatables中的Options总结(3)
- mac-文本编辑器
- Oracle外键不加索引会引起死锁问题
- delphi 基础之四 delphi 组织结构
- SPA初试-1
- Codeforces Bubble Cup 8 - Finals [Online Mirror]H. Bots 数学
- 不用第三个变量,将a,b两个值互换,会出现什么样的异常?
- hdu 4512 吉哥系列故事——完美队形I LCIS
- Zend Studio 如何配置本地apache服务器使用xdebug调试php脚本
- 看AngularJS
- mysql提示Column count doesn&#39;t match value count at row 1错误
- UNIX DOMAIN SOCKET效率
- PHP的Memcached简单实现
- Codeforces.612E.Square Root of Permutation(构造)
- py2和py3的区别总结
- Django之form总结
- 目前最全的IT技术问答、社区、科技服务网站合集
- 小米笔记本装MAC(黑苹果),外接USB蓝牙,禁止笔记本自带的蓝牙方法
- Hibernate中对象的三种状态及相互转化