始于
分类:LeetCode
Tags: [ LeetCode ]
LeetCode 百题计划 - 3. Longest Substring Without Repeating Characters - dp
LeetCode 3. Longest Substring Without Repeating Characters
今天乍一看哎哟woc, 我做的这个题目单是Top 100 liked 而不是什么Top 100 Classic或者easiest, 算了, 既然上了车车门焊死了, 也就不要下车了.
地址: https://leetcode.com/problemset/top-100-liked-questions/
3. Longest Substring Without Repeating Characters
Difficulty: medium
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: “pwwkew”
Output: 3
Explanation: 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.
乍一眼一看, 这不就是搞两根”筷子”夹着substrings, 然后慢慢夹出一个最大的.
我们开一个二维数组(momery[x][y])来存x和y之间的所有子字符串有没有重复. 用1表示可以使用, 0表示不能使用, 2表示还没有计算.
但是而后想一想, emmm, 这样做不就是暴力嘛! 你不超时谁超时…
换一种思路, 字符总数量也就200+个嘛, 干脆直接使用记忆化, 还是用两筷子.
Only Version
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> arr(260, false);
int l, r;
l = r = 0;
int ans = 0;
while (r < s.size()) {
if (arr[s[r]]) {
arr[s[l]] = false;
++l;
} else {
arr[s[r]] = true;
++r;
}
cout << arr[s[l]] << " ";
ans = max(ans, r - l);
}
return ans;
}
};
好了, 说实话这思路是讨论区剽的. 菜是原罪.
解释一下思路, 通过上面的方法, 可以把所有无重复字母的局部最大子串的长度全部统计出来. 分别取最大就好了.
其他方法不考虑了. 这就是最好的方法.
Rate:
Runtime: 32 ms, faster than 34.30% of C++ online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 10.4 MB, less than 70.91% of C++ online submissions for Longest Substring Without Repeating Characters.