-
Notifications
You must be signed in to change notification settings - Fork 59
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Find The Longest Substring #4
Comments
抛砖一个,模仿 kmp 滑动 function longestUniqueSubstr (str) {
str = String(str)
var index = {} // keys: char of a tentative substr, values: index
var tenLen = 0 // len of the tentative substr
var resLen = 0 // result len
for (let i = 0; i < str.length; i += 1) {
let ic = index[str[i]]
if (typeof ic !== 'undefined') {
if (tenLen > resLen) { resLen = tenLen }
i = ic + 1
index = {}
tenLen = 0
}
index[str[i]] = i
tenLen += 1
}
return Math.max(tenLen, resLen)
} console.assert(longestUniqueSubstr('abcabcbb') === 3, 'abcabcbb')
console.assert(longestUniqueSubstr('bbbbb') === 1, 'bbbbb')
console.assert(longestUniqueSubstr('pwwkew') === 3, 'pwwkew')
console.assert(longestUniqueSubstr('') === 0, '')
console.assert(longestUniqueSubstr('1') === 1, '1')
console.assert(longestUniqueSubstr('111') === 1, '111')
console.assert(longestUniqueSubstr('1234') === 4, '1234')
console.assert(longestUniqueSubstr('11234') === 4, '11234')
console.assert(longestUniqueSubstr('12344') === 4, '12344')
console.assert(longestUniqueSubstr('1234445678') === 5, '1234445678')
console.assert(longestUniqueSubstr('1234235678') === 7, '1234235678') |
微博上看到的,抛个砖,希望能坚持下去.已经watch function test(str) {
let map = {}
let currentLen = 0
let result = 0
for (let i = 0; i < str.length; i++) {
if (map[str[i]] === undefined) {
currentLen++
map[str[i]] = i
} else {
if (currentLen > result) {
result = currentLen
}
currentLen = 0
i = map[str[i]]
map = {}
}
}
return Math.max(currentLen, result)
} 写完之后才发现楼上的更好,更简洁,向楼上 |
console.assert(resolve('abbcdefdakngda') === 7);
function resolve(str) {
let maxLen = 0;
let map = {
length: 0
};
for(let i = 0, len = str.length; i < len; i++) {
if (map[str[i]]) {
maxLen = Math.max(map.length, maxLen);
i = map[str[i]] + 1;
map = {};
map.length = 0;
}
map[str[i]] = i;
map.length++;
}
return Math.max(map.length, maxLen);
} 写了一个,发现与 @crimx 的解法是一样的,应该还有更优解。 |
题目:找出一个字符串中最长的连续子串,输出这个子串的长度,要求:这个子串中没有重复的字符。 最简单的思路就是暴力遍历法,并在遍历的同时统计长度,找到重复字符就停止。最后给出最大的长度。 进一步优化的,可以使用hash表记录下来每个元素出现的索引值; 进一步优化,重用建立的hash记录,每次发现重复元素时进行更新; 代码如下: def resolve(seq):
stat = {}
index = 0
max_len, tmp_len = 0, 0
while(index < len(seq)):
if seq[index] not in stat:
tmp_len += 1
else:
if tmp_len > max_len:
max_len = tmp_len
tmp_len = index - stat[seq[index]]
# update stat record
stat[seq[index]] = index
index += 1
return max(max_len, tmp_len)
assert resolve('abcabcbb') == 3
assert resolve('bbbb') == 1
assert resolve('pwwkew') == 3
assert resolve('1') == 1
assert resolve('111') == 1
assert resolve('112345678') == 8 |
我同意 @YabZhang 的算法, @crimx 的算法并非最优。 function test(str) {
var index = {} // keys: char of a tentative substr, values: index
var tenLen = 0 // len of the tentative substr
var resLen = 0 // result len
for (let i = 0; i < str.length; i += 1) {
let ic = index[str[i]]
if (typeof ic !== 'undefined') {
if (tenLen > resLen) {
resLen = tenLen
}
tenLen = i - ic;
index[str[i]] = i;
} else {
tenLen += 1;
}
index[str[i]] = i
}
return Math.max(tenLen, resLen)
} |
@youngwind 确实记录每个字符最新的位置就不需要回溯了:thumbsup: 这样就保证了 i 到 ic 之间的字符必然是独立的。 |
@youngwind ,你算法有问题console.log(test('abccdefab')) 输出 7。计算速度1.4s |
找出一个字符串中最长的连续子串,输出这个子串的长度,要求:这个子串中没有重复的字符。
比如:
参考答案:https://github.com/barretlee/daily-algorithms/blob/master/answers/4.md
The text was updated successfully, but these errors were encountered: