LeetCode 热题 100

力扣最受刷题发烧友欢迎的 100 道题 链接

哈希

两数之和 简单

#1 数组 哈希表

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const map = new Map()
  for (let i = 0; i <= nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i]
    } else {
      map.set(nums[i], i)
    }
  }
}

字母异位词分组 中等

#49 数组 哈希表 字符串 排序

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const map = new Map()
  for (const str of strs) {
    const changed = str.split('').sort().join('')
    // 先每一个子项排序，排序后的值都一样的才符合分组
    // hash存储原子项
    if (map.has(changed)) {
      map.get(changed).push(str)
    } else {
      map.set(changed, [str])
    }
  }
  return Array.from(map.values())
}

最长连续序列 中等

#128 数组 哈希表 并查集

/**暴力破解法，排序再遍历
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  if (nums.length === 0) return 0
  let max = 1
  let tmp = 1
  nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] === nums[i + 1]) {
      continue
    } else if (nums[i] + 1 === nums[i + 1]) {
      tmp++
    } else {
      tmp = 1
    }
    max = Math.max(tmp, max)
  }
  return max
}
longestConsecutive([100, 4, 200, 1, 3, 2])

/**hash表
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  const map = new Map()
  let max = 0
  for (const num of nums) {
    if (!map.has(num)) {
      const preLen = map.get(num - 1) || 0
      const nextLen = map.get(num + 1) || 0
      curLen = preLen + 1 + nextLen
      map.set(num, curLen)
      map.set(num - preLen, curLen)
      map.set(num + nextLen, curLen)
      max = Math.max(max, curLen)
    }
  }
  return max
}
longestConsecutive([100, 4, 200, 1, 3, 2])

双指针

移动零 简单

#283 数组 双指针

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
// 遇到非0的移动到慢指针
var moveZeroes = function (nums) {
  let j = 0
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[j] = nums[i]
      j++
    }
  }
  nums.fill(0, j)
}

console.log(moveZeroes([0, 1, 0, 3, 12]))