leetcode 无重复字符的最长子串

概要

定义两个变量res和left,其中res用来记录最长无重复子串的长度,lefts指向该无重复子串左边的起始位置,然后我们遍历整个字符串,对于每一个遍历到的字符,如果哈希表中该字符串对应的值为0,说明没有遇到过该字符,则此时计算最长无重复子串,i - left +1,其中i是最长无重复子串最右边的位置,left是最左边的位置,还有一种情况也需要计算最长无重复子串,就是当哈希表中的值小于left,这是由于此时出现过重复的字符,left的位置更新了,如果又遇到了新的字符,就要重新计算最长无重复子串。最后每次都要在哈希表中将当前字符对应的值赋值为i+1

无重复字符的最长子串

给定一个字符串,找出不含有重复字符的最长子串的长度。

示例:

1
2
3
4
5
给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。

给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。

给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串,"pwke" 是 子序列 而不是子串。

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let hash = {}
let start = 0
let ans = 0

for (var i = 0; i < s.length; i++){
let item = s[i]
if (!hash[item]) {
hash[item] = true
} else {
for (;;) {
if (s[start] === item) {
start++;
break;
}
hash[s[start]] = false
start++
}

}
ans = Math.max(ans, i - start + 1)
}
return ans
}

解法二

下面这种写法是上面解法的精简模式,思路都一样:

1
2
3
4
5
6
7
8
9
10
11
12
var lengthOfLongestSubstring = function(s) {
var res = 0
var left = -1
var m = []
m.fill(-1)
for (var i = 0; i < s.length; i++) {
left = Math.max(left, m[s.charAt(i)])
m[s.charAt[i]] = i
res = Math.max(res, i - left)
}
return res
}

解法三

下面这种解法使用了set,核心算法和上面的很类似,把出现过的字符都放入set中,遇到set中没有的字符就加入set中并更新结果res,如果遇到重复的,则从左边开始删字符,直到删到重复的字符停止:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var lengthOfLongestSubstring = function(s) {
var res = 0
var left = 0
var right = 0
var t = new Set()
while (right < s.length){
if (!t.has(s.charAt(right))) {
t.add(s.charAt(right++))
res = Math.max(res, t.size)
} else {
t.delete(s.charAt(left++))
}
}
return res
}

两个排序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))
示例 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

示例 2:

1
2
3
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5

解题思路

这道题让我们求两个有序数组的中位数,而且限制了时间复杂度为O(log (m+n)),看到这个时间复杂度,自然而然的想到了应该使用二分查找法来求解。但是这道题被定义为Hard也是有其原因的,难就难在要在两个未合并的有序数组之间使用二分法,这里我们需要定义一个函数来找到第K个元素,由于两个数组长度之和的奇偶不确定,因此需要分情况来讨论,对于奇数的情况,直接找到最中间的数即可,偶数的话需要求最中间两个数的平均值。下面重点来看如何实现找到第K个元素,首先我们需要让数组1的长度小于或等于数组2的长度,那么我们只需判断如果数组1的长度大于数组2的长度的话,交换两个数组即可,然后我们要判断小的数组是否为空,为空的话,直接在另一个数组找第K个即可。还有一种情况是当K = 1时,表示我们要找第一个元素,只要比较两个数组的第一个元素,返回较小的那个即可。

解法1

1
2
3
4
5
6
7
8
9
10
var findMedianSortedArrays = function(nums1, nums2) {
var s = nums1.concat(nums2);
s.sort(function(a, b) {
return a - b;
});

var len = s.length;
if (len & 1) return s[~~(len / 2)];
else return (s[len / 2 - 1] + s[len / 2]) / 2;
};

解法2

此题还能用二分搜索法来解,是一种相当巧妙的应用,讲解在这个帖子中写的十分清楚,等有时间我再来写写分析过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var findMedianSortedArrays = function(nums1, nums2) {
var m = nums1.length;
var n = nums2.length;
if (m < n) {
return findMedianSortedArrays(nums2, nums1)
}
if (n == 0) {
return (nums1[(m - 1) / 2] + nums1[m / 2]) / 2.0
}
var left = 0,
right = 2 * n
while (left <= right) {
var mid2 = (left + right) / 2;
var mid1 = m + n - mid2;
var L1 = mid1 == 0 ? 0 : nums1[(mid1 - 1) / 2];
var L2 = mid2 == 0 ? 0 : nums2[(mid2 - 1) / 2];
var R1 = mid1 == m * 2 ? 0 : nums1[mid1 / 2];
var R2 = mid2 == n * 2 ? 0 : nums2[mid2 / 2];
if (L1 > R2) {
left = mid2 + 1;
}else if (L2 > R1) {
right = mid2 - 1;
}else {
return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
}
}
};