字典

Frank
  • 算法
  • 字典
大约 4 分钟约 1140 字...

简介

与集合类似,字典也是一种存储唯一值的数据结构,但它是以键值对的形式来存储。

ES6 中有字典,名为Map

字典的常用操作:键值对的增删改查

LeetCode:349. 两个数组的交集

LeetCode:349. 两个数组的交集open in new window

  • 解题思路

求 nums1 和 nums2 都有的值

用字典建立一个映射关系,记录 nums1 里都有的值

遍历 nums2 找出 nums1 里也有的值

  • 解题步骤

新建一个字典,遍历 nums1,填充字典

遍历 nums2 遇到字典里的值就选出,并从字典中删除

/*
 * @lc app=leetcode.cn id=349 lang=javascript
 *
 * [349] 两个数组的交集
 */

// @lc code=start
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  // 集合
  // return [...new Set(nums1)].filter((item) => {
  //     return nums2.includes(item)
  // })
  // 字典
  let m = new Map()
  nums1.forEach(item => {
    m.set(item, true)
  })
  let res = []
  nums2.forEach(item => {
    if (m.get(item)) {
      res.push(item)
      m.delete(item)
    }
  })
  return res
}
// @lc code=end

LeetCode:20.有效的括号

LeetCode:20.有效的括号open in new window使用字典建立左右括号映射关系

/*
 * @lc app=leetcode.cn id=20 lang=javascript
 *
 * [20] 有效的括号
 */

// @lc code=start
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 有手就行
  const stack = []
  const map = new Map()
  map.set('{', '}')
  map.set('(', ')')
  map.set('[', ']')
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      stack.push(s[i])
    } else {
      const top = stack[stack.length - 1]
      if (map.get(top) === s[i]) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}
// @lc code=end

LeetCode:1. 两数之和

LeetCode:1. 两数之和open in new window

  • 解题思路

把 nums 想象成相亲者

把 target 想象成匹配条件

用字典建立一个婚姻介绍所,存储相亲者的数字和下标

  • 解题步骤

新建一个字典作为婚姻介绍所。

nums 里的值,逐个来介绍所找对象,没有合适的就先登记着,有合适的就牵手成功。

/*
 * @lc app=leetcode.cn id=1 lang=javascript
 *
 * [1] 两数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let map = new Map()
  for ([index, val] of nums.entries()) {
    let n = target - val
    if (map.has(n)) {
      return [map.get(n), index]
    } else {
      map.set(val, index)
    }
  }
}
// @lc code=end

LeetCode:3. 无重复字符的最长子串

LeetCode:3. 无重复字符的最长子串open in new window

  • 解题思路

先找出所有的不包含重复字符的子串

找出长度最大那个子串,返回其长度即可。

  • 解题步骤

用双指针维护一个滑动窗口(slice),用来剪切子串。

不断移动右指针,遇到重复字符,就把左指针移动到重复字符的下一位。

过程中,记录所有窗口的长度,并返回最大值。

有个坑

如果输入的为“abbcdea”,无重复字符的最长子串的长度应该为 5("bcdea"),此时左指针在索引为 2 的那一项,当右指针要马上指向最后一个 a 时,发现 map 中已经有一个 a 了,所以会移动左指针到索引为 1 的位置,这就导致输出结果为 6 了

解决方法:移动左指针时,必须确保重复字符的索引必须大于左指针的索引

/*
 * @lc app=leetcode.cn id=3 lang=javascript
 *
 * [3] 无重复字符的最长子串
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let l = 0
  let r = 0
  let res = 0
  let map = new Map()
  for (r = 0; r < s.length; r++) {
    if (map.has(s[r]) && map.get(s[r]) >= l) {
      l = map.get(s[r]) + 1
    }
    res = Math.max(res, r - l + 1)
    map.set(s[r], r)
  }
  return res
}
// @lc code=end

LeetCode:76. 最小覆盖子串

LeetCode:76. 最小覆盖子串open in new window

  • 解题思路

先找出所有的包含 T 的子串。

找出长度最小那个子串,返回即可。

  • 解题步骤

用双指针维护一个滑动窗口。

移动右指针,找到包含 T 的子串,移动左指针,尽量减少包含 T 的子串的长度。

循环上述过程,找出包含 T 的最小子串

提示

substring 参数为左闭右开区间,substring(a,b)可以得到从 a 开始到 b 结束(不包括 b 处)的子串

/*
 * @lc app=leetcode.cn id=76 lang=javascript
 *
 * [76] 最小覆盖子串
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  let l = 0
  let r = 0
  let res = ''
  // 需要
  const need = new Map()
  for (let c of t) {
    need.set(c, need.has(c) ? need.get(c) + 1 : 1)
  }
  let needType = need.size
  while (r < s.length) {
    const c = s[r]
    if (need.has(c)) {
      need.set(c, need.get(c) - 1)
      if (need.get(c) === 0) needType--
    }
    while (needType === 0) {
      let newRes = s.substring(l, r + 1)
      if (!res || newRes.length < res.length) res = newRes
      const c2 = s[l]
      if (need.has(c2)) {
        need.set(c2, need.get(c2) + 1)
        if (need.get(c2) === 1) needType++
      }
      l++
    }
    r++
  }
  return res
}
// @lc code=end
上次编辑于:
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.14.1