字典
- 與集合類似姻成，字典也是一種存儲唯一值的數(shù)據(jù)結(jié)構(gòu)也祠，但它是以鍵值對的形式來存儲
- ES6中有字典谴供，名為Map
- 字典的常用操作：鍵值對的增刪改查
const map = new Map()
// 增加
map.set('a': 'aa')
map.set('b': 'bb')
// 獲取
map.get('a')
// 改
map.set('a': 'aaa')
// 刪除
map.delete('b')
// 刪除所有
map.clear()
兩個數(shù)組的交集
leeCode第349題
- 之前使用集合來解決，現(xiàn)在使用字典來解決
- 求 nums1 和 nums2 都有的值
- 用字典建立一個映射關(guān)系齿坷，記錄 nums1 里有的值，填充字典
- 遍歷 nums2数焊，遇到字典里的值就選出永淌，并從字典中刪除
const intersection = function(nums1, nums2) {
const map = new Map()
nums1.forEach(num => {
map.set(num, true)
});
const res = []
nums2.forEach(num => {
if(map.get(num)) {
res.push(num)
map.delete(num)
}
})
return res
};
const arr1 = [1,2,2,1] // [4,9,5]
const arr2 = [1,2] // [9,4,9,8,4]
const res = intersection(arr1, arr2)
console.log(res)
有效的括號
leeCode第20題
- 之前是使用棧來解決的，現(xiàn)在使用字典來解決
- 通過定義字典佩耳，左括號則入棧遂蛀，否則取出棧頂字典值判斷是否一致
- 之前解法為了兼容里面有非括號，但是重新看了一下題目其實已經(jīng)說了輸入只有括號符干厚，所以沒必要特地去處理其他字符
const isValid = function(s) {
if (s.length % 2) return false
const stack = []
const map = new Map()
map.set('(', ')')
map.set('{', '}')
map.set('[', ']')
for (let i = 0; i < s.length; i++) {
const c = s[i]
if (map.has(c)) {
stack.push(c)
} else {
const t = stack[stack.length - 1]
if (map.get(t) === c) {
stack.pop()
} else {
return false
}
}
}
return !stack.length
}
console.log(isValid("()"))
console.log(isValid("()[]{}"))
console.log(isValid("([)]"))
console.log(isValid("{[]}"))
console.log(isValid("{[]"))
兩數(shù)之和
leeCode第1題
- target為匹配條件
- 先進入的nums為匹配者李滴，如果沒找到合適的則記錄本身匹配答案
const twoSum = function(nums, target) {
const map = new Map()
for (let i = 0; i < nums.length; i++) {
const n = nums[i]
const n2 = target - n
if (map.has(n2)) {
return [map.get(n2), i]
} else {
map.set(n, i)
}
}
}
console.log(twoSum([2,7,11,15], 9))
console.log(twoSum([3,2,4], 6))
console.log(twoSum([3,3], 6))
無重復(fù)字符的最長子串
leeCode第3題
- 用雙指針維護一個滑動窗口螃宙，用來剪切字符串
- 不斷移動右指針，遇到重復(fù)字符所坯，就把左指針移動到重復(fù)字符的下一位
- 找出長度最大那個子串谆扎，返回其長度即可
const lengthOfLongestSubstring = function(s) {
let l = 0
let res = 0
const map = new Map()
for (let r = 0; r < s.length; r++) { // 不停移動右指針
if (map.has(s[r]) && map.get(s[r]) >= l) { // 如果重復(fù)的數(shù)字比左指針下標(biāo)少則證明被排除在外了，無需管
l = map.get(s[r]) + 1
}
res = Math.max(res, r - l + 1) // 記錄字符最大值
map.set(s[r], r) // 記錄該字符下標(biāo)
}
return res
}
console.log(lengthOfLongestSubstring('abcabcbb'))
console.log(lengthOfLongestSubstring('bbbbb'))
console.log(lengthOfLongestSubstring('pwwkew'))
console.log(lengthOfLongestSubstring('abbcdea'))
最小覆蓋子串
leeCode第76題
- 用雙指針維護一個滑動窗口
- 移動右指針芹助，找到包含T的子串堂湖，移動左指針，盡量減少包含T的子串的長度
- 循環(huán)上述過程状土，找到包含T的最小子串
const minWindow = function(s, t) {
let l = 0
let r = 0
const map = new Map()
for (let c of t) {
map.set(c, map.has(c) ? map.get(c) + 1 : 1)
}
let needType = map.size
let res = ''
while (r < s.length) {
const c = s[r]
if (map.has(c)) {
map.set(c, map.get(c) - 1)
if (map.get(c) === 0) needType--
}
while (needType === 0) {
const newRes = s.substring(l, r + 1)
if (!res || newRes.length < res.length) res = newRes
const c2 = s[l]
if (map.has(c2)) {
map.set(c2, map.get(c2) + 1)
if (map.get(c2) === 1) needType++
}
l++
}
r++
}
return res
}
console.log(minWindow('ADOBECODEBANC', 'ABC'))
console.log(minWindow('a', 'a'))
