leetcode-75-76

leetcode75题76题:

leetcode75题(颜色分类):

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:
1
2
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var sortColors = function(nums) {
var p0 = 0;//表示0的最右边界
var p2 = nums.length-1;//表示2的最右边界
var curr = 0;//表示当前指针所在的位置
while(curr<=p2){
//当遇到当前元素是0的时候,交换元素后,p0向后挪一位,同时curr向后挪一位
if(nums[curr]==0){
temp = nums[p0];
nums[p0++] = nums[curr];
nums[curr++] = temp;
//当遇到当前元素是2的时候,交换元素后,p2向前挪一位,同时curr不动
}else if(nums[curr]==2){
temp = nums[p2];
nums[p2--] = nums[curr];
nums[curr] = temp;
//如果遇到的是1,那么直接curr向后挪一位
}else{
curr++;
}
}
};

leetcode76题(最小覆盖子串):

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。

示例:
1
2
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
解答:
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
var minWindow = function(s, t) {

var start = 0;
var minLen = Infinity;
var left = 0;
var right = 0;
var match = 0
var needs = {};
var window = {};
var count = 0;
for(var i=0;i<t.length;i++){
//新建两个对象,needs用来统计t中每个字符对应个数
//window对象用来统计现有的窗口中每个字符及其对应个数
if(needs[t[i]]==undefined){
needs[t[i]] = 1;
count++;
}else{
needs[t[i]]++;
}
window[t[i]] = 0;
}
while(right<s.length){
var rightVal = s[right];
if(needs[rightVal]!=undefined){
window[rightVal]++;
if(needs[rightVal]==window[rightVal]){
match++;
}
}
right++;
//当执行while循环的时候,说明上面的窗口已经包含了所需的所有字符,这次从左边开始进行缩减
while(match==count){
if(right-left<minLen){
start = left;
minLen = right-left;//得到目前包含所有t中字符的包含字符串长度的最小值
}
var leftVal = s[left];
if(window[leftVal]!=undefined){
window[leftVal]--;
if(needs[leftVal]>window[leftVal]){
match--;
}
}
left++;
}
}
return minLen==Infinity?"":s.substr(start,minLen);
};

小k

分享到