904.水果成篮
解题思路
简而言之，是为了找最长连续两个数的序列。
前面的理解了，自己上手又有点不行。自己写的↓，感觉思路是对的，却不行。(发现for循环初始化搞错了)
/**
* @param {number[]} fruits
* @return {number}
*/
var totalFruit = function(fruits) {
let i = 0
let flag = []
let typeF = 0
let maxLen = 0
for(let j=fruits.length;j<fruits.length;j++){
flag.push(fruits[j])
if(!flag.includes(fruits[j])){ //如果篮子里没有这种水果则加入这种水果
// flag.push(fruits[j])
typeF++
}
if(typeF > 2){ //如果篮子里水果种类 > 2
maxLen = Math.max(maxLen,j-i+1) //获取当前的序列长度
//删除一种水果
deletedF = flag.shift()//确定删除的这种水果
i = flag.lastIndexOf(deleteF) != -1 ? flag.lastIndexOf(deleteF) : i+1 //找到这种水果最后出现的位置，变更i的位置
flag = flag.slice(i-1)//删除i之前的
typeF--
}
}
return flag.length
};
改正之后是
var totalFruit = function(fruits) {
let i = 0
let flag = []
let typeF = 0
let maxLen = 0
for(let j=0;j<fruits.length;j++){
// if(flag.lastIndexOf(fruits[j]) == -1){ //如果篮子里没有这种水果则加入这种水果
// typeF++
// } 这样也可以
if(!flag.includes(fruits[j])){ //如果篮子里没有这种水果则加入这种水果
typeF++
}
flag.push(fruits[j])
// typeF = Array.from(new Set(flag)).length //获取现在的水果种类数
// console.log(typeF)
if(typeF > 2){ //如果篮子里水果种类 > 2
//删除一种水果
// deletedF = flag.shift()//确定删除的这种水果
// i = flag.lastIndexOf(deleteF) != -1 ? flag.lastIndexOf(deleteF) : i+1 //找到这种水果最后出现的位置，变更i的位置
// flag = flag.slice(i-1)//删除i之前的
// typeF--
flag.shift() //删除最前面的
i++ //变更i的位置
typeF = Array.from(new Set(flag)).length //获取现在的水果种类数
}
maxLen = Math.max(maxLen,j-i+1) //获取当前的序列长度
}
return flag.length
//return maxLen 也可以
};
去看了别人的题解，是最大滑窗和最小话长的区别，感觉总结的很好：
- 最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度。
while j < len(nums):
判断[i, j]是否满足条件
while 满足条件：
不断更新结果(注意在while内更新！)
i += 1 （最大程度的压缩i，使得滑窗尽可能的小）
j += 1
//作者：frostep
//链接：https://leetcode.cn/problems/fruit-into-baskets/solution/shen-du-jie-xi-zhe-dao-ti-he-by-linzeyin-6crr/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。
while j < len(nums):
判断[i, j]是否满足条件
while 不满足条件：
i += 1 （最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）
不断更新结果（注意在while外更新！）
j += 1
//作者：frostep
//链接：https://leetcode.cn/problems/fruit-into-baskets/solution/shen-du-jie-xi-zhe-dao-ti-he-by-linzeyin-6crr/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
JavaScript解法代码
var totalFruit = function(fruits) {
let i = 0
const blanket = new Map()
let maxLen = 0
for(let j=0;j<fruits.length;j++){
blanket.set(fruits[j], (blanket.get(fruits[j]) || 0) + 1)
while(blanket.size > 2){
blanket.set(fruits[i], blanket.get(fruits[i]) - 1);
if (blanket.get(fruits[i]) == 0) {
blanket.delete(fruits[i]);
}
++i;
}
maxLen = Math.max(maxLen, j-i+1)
}
return maxLen
};
Python解法代码
自己的
虽然可以AC，但其实是有问题的。
class Solution(object):
def totalFruit(self, fruits):
"""
:type fruits: List[int]
:rtype: int
"""
fruitsType = 0
blanket = []
for j in range(len(fruits)):
if(fruits[j] not in blanket):
fruitsType+=1
blanket.append(fruits[j])
if(fruitsType > 2):
del(blanket[0])
fruitsType = len(list(set(blanket)))
return len(blanket)
滑动窗口
class Solution(object):
def totalFruit(self, fruits):
"""
:type fruits: List[int]
:rtype: int
"""
blanket = {}
maxLen = 0
i = 0
for j in range(len(fruits)):
count =( blanket.get(fruits[j]) or 0)+1
blanket[fruits[j]] = count
while(len(blanket) > 2):
count = blanket.get(fruits[i])-1
blanket[fruits[i]] = count
if (blanket[fruits[i]] == 0):
del blanket[fruits[i]]
i+=1
maxLen = max(maxLen,j-i+1)
return maxLen
76.最小覆盖子串
解题思路
用滑动窗口找最短的字符串。
出现的问题
没有对对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量这个限制条件作出处理，所以对于如"aa","aa"这中例子处理不了。
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
let i = 0
let substr = ''
let allExist
let minLen = Number.MAX_VALUE
let minstr =''
for(let j=0;j<s.length;j++){
substr += s[j]
//判断条件 substr是否包含了t内的每个字符
allExist= [...t].every(char => substr.includes(char));
while(allExist){
temp = minLen
minLen = Math.min(minLen,j-i+1)
if(minLen < temp){ //字符串改变了，变短了，则存储此时的字符串
minstr = substr
console.log(minstr)
}
substr = substr.substr(1) //删除第一个字符
allExist= [...t].every(char => substr.includes(char)); //判断allExist 是否仍满足条件
i++
}
}
if(t.length < minstr.length){
return ""
}
else{
return minstr
}
};
使用Map解决了上述的问题，但是提交的时候因为有个例子非常长，所以超出了时间限制。
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
let tDict = new Map();
[...t].forEach(element => {
tDict.set(element, (tDict.get(element) || 0) + 1)
})
let i = 0;
let substr = '';
let substrDict = new Map();
let allExist;
let minLen = Number.MAX_VALUE;
let minstr ='';
for(let j=0;j<s.length;j++){
substr += s[j]
substrDict.set(s[j],(substrDict.get(s[j]) || 0)+1)
//判断条件 substr是否包含了t内的每个字符
// allExist= [...t].every(char => [...substrDict.keys()].join('').includes(char));
allExist= [...t].every(char => substr.includes(char));
[...t].forEach(element => {
if(substrDict.get(element) < tDict.get(element)){ //如果少于，则allExist = false
allExist = false
}
})
while(allExist){
temp = minLen
minLen = Math.min(minLen,j-i+1)
if(minLen < temp){ //字符串改变了，变短了，则存储此时的字符串
// minstr = [...substrDict.keys()].join('')
minstr = substr
console.log('minstr：',minstr)
}
//删除第一个字符
substr = substr.substr(1)
substrDict.set(s[i],substrDict.get(s[i])-1)
if (substrDict.get(s[i]) == 0) {
substrDict.delete(s[i]);
}
allExist= [...t].every(char => substr.includes(char));
//"对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。"
//判断t中字符的长度 与 substr比较
[...t].forEach(element => {
if(substrDict.get(element) < tDict.get(element)){ //如果少于，则allExist = false
allExist = false
}
})
i++
}
}
return minstr
};
看了答案，还没参悟。
ta也是用Map，但是对map的size有更灵活的运用。
JavaScript解法代码
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function (s, t) {
const target = new Map();
let minChar;
let nowChar = "";
[...t].forEach(element => {
target.set(element, (target.get(element) || 0) + 1)
})
let size = target.size
let i= 0
for (let j=0; j < s.length; j++) {
if (target.has(s[j])) target.set(s[j], target.get(s[j]) - 1);
if (target.get(s[j]) === 0) size--
// console.log('size: ',size, !size)
while (!size) {
nowChar = s.substring(i, j + 1);
// console.log('nowChar: ',nowChar)
if (target.has(s[i])) {
target.set(s[i], target.get(s[i]) + 1)
if (target.get(s[i]) === 1) {
size++
console.log(!minChar || minChar.length > nowChar.length)
if (!minChar || minChar.length > nowChar.length) minChar = nowChar; //!minChar 判断minChar不为空（不为初始值）
// console.log(minChar)
}
}
i++;
}
}
return minChar ? minChar : '';
};
Python解法代码
//待完成
总结：
- map集合的操作要注意：包括set、get、has的运用
target.set(element, (target.get(element) || 0) + 1) - 滑动窗口通用解总结：
- 最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度。
while j < len(nums):
判断[i, j]是否满足条件
while 满足条件：
不断更新结果(注意在while内更新！)
i += 1 （最大程度的压缩i，使得滑窗尽可能的小）
j += 1
//作者：frostep
//链接：https://leetcode.cn/problems/fruit-into-baskets/solution/shen-du-jie-xi-zhe-dao-ti-he-by-linzeyin-6crr/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。
while j < len(nums):
判断[i, j]是否满足条件
while 不满足条件：
i += 1 （最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）
不断更新结果（注意在while外更新！）
j += 1
//作者：frostep
//链接：https://leetcode.cn/problems/fruit-into-baskets/solution/shen-du-jie-xi-zhe-dao-ti-he-by-linzeyin-6crr/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
