高枕枕のBlog

Appearance

Leecode ​

HOT 100

两数之和 ​

辅助哈希表

两数相加 ​

链表略

无重复字符的最长子串 ​

遍历+indexOf

最长回文子串 ​

‘#’隔开+遍历+每个做中央查找两边是否一样得回文数

js
function longestPalindrome(s) {
  let n = s.length
  let t = '#'
  for (let i = 0; i < n; i++) {
    t += s[i] + '#'
  }
  let c = 0,
    max = 0

  for (let i = 0; i < t.length; i++) {
    let temp = 0
    let ii = 1
    while (t[i - ii] && t[i + ii] && t[i - ii] === t[i + ii]) {
      temp += 1
      ii += 1
    }
    if (temp > max) {
      max = temp
      c = i
    }
  }
  let ans = ''
  for (const i of t.slice(c - max, c + max)) i !== '#' && (ans += i)
  return ans
}

盛最多水的容器 ​

两端往中间走 一边走一边算 直到相遇

js
function maxArea(nums) {
  let i = 0,
    j = nums.length - 1,
    ans = 0
  while (i < j) {
    let area = Math.min(nums[i], nums[j]) * (j - i)
    area > ans && (ans = area)
    nums[i] > nums[j] ? j-- : i++
  }
  return ans
}

三数之和 ​

先排序 拿出一个数做二数之和 大于零了直接返回

js
var threeSum = function (nums) {
    nums.sort((a, b) => a - b)
    let ans = []
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) return ans
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue
        }
        let front = i + 1
        let rear = nums.length - 1
        while (front < rear) {
            let sum = nums[i] + nums[front] + nums[rear]
            if (sum === 0) {
                ans.push([nums[i], nums[front], nums[rear]])
                while (front < rear && nums[front] === nums[front + 1]) {
                    front++
                }
                while (front < rear && nums[rear] === nums[rear - 1]) {
                    rear--
                }
                front++
                rear--
            } else if (sum < 0) {
                front++
            } else {
                rear--
            }
        }
    }
    return ans
}

电话号码的字母组合 ​

递归回溯是最佳方法 但此处直接循环遍历 重点至于进循环前造好前项

js
function letterCombinations(s) {
  if (s === '') return []
  let m = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  let save = []
  for (let i of s) save.push(m[+i - 2])
  let allOut = save.shift().split('')
  for (let i of save) {
    let out = []
    for (let j of i) for (let k of allOut) out.push(k + j)
    allOut = out
  }
  return allOut
}

删除链表的倒数第 N 个结点 ​

链表略

有效括号 ​

奇数直接返回 左入栈又出栈消消乐

js
function isValid(s) {
  let arr = [],
    $ = {
      '(': ')',
      '[': ']',
      '{': '}',
    }
  for (let i of s) {
    if ($[i]) arr.push($[i])
    else if (arr.pop() !== i) return false
  }
  if (arr.length !== 0) return false
  else return true
}

合并两个有序链表 ​

链表略

括号生成 ​

循环在碰到)之前每处都加一个括号

js
function generateParenthesis(n) {
  let all = ['()']
  for (let i = 1; i < n; i++) {
    let out = []
    for (let j of all) {
      for (let k = 0; k < j.length; k++) {
        if (j[k] == ')') break
        if (k === 0) out.push('()' + j)
        out.push(j.slice(0, k + 1) + '()' + j.slice(k + 1))
      }
    }
    all = [...out]
  }
  return all
}

下一个排列 ​

从右往左冒泡排序

搜索旋转排序数组 ​

indexOf

在排序数组中查找元素的第一个和最后一个位置 ​

indexOf lastIndexOf

组合总和 ​

上手直接排序 然后递归

js
var combinationSum = function(candidates, target) {
    let res = [], path = []
    candidates.sort((a,b)=>a-b)

    function backtracking(startIndex, sum) {
        if (sum === target) {
            res.push([...path])
            return
        }
        for(let i = startIndex; i < candidates.length; i++ ) {
            const temp = candidates[i]
            if(temp + sum > target) return
            path.push(temp)
            sum += temp
            backtracking(i, sum)
            path.pop()
            sum -= temp
        }
    }
    backtracking(0, 0)
    return res
}

接雨水 ​

从左往右 到达最高峰结束 从右往左 到达最高峰结束

js
function trap(nums) {
  const length = nums.length
  let ans = 0
  let ii
  left: for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      if (nums[j] >= nums[i]) {
        for (let k = i + 1; k < j; k++) ans += nums[i] - nums[k]
        i = j - 1
        break
      }
      if (j === length - 1) {
        ii = i
        break left
      }
    }
  }
  for (let i = length - 1; i > ii - 1; i--) {
    for (let j = i - 1; j > ii - 1; j--) {
      if (nums[j] >= nums[i]) {
        for (let k = j + 1; k < i; k++) ans += nums[i] - nums[k]
        i = j + 1
        break
      }
    }
  }
  return ans
}

全排列 ​

递归回溯

js
function permute(nums) {
  if (nums.length === 1) return [nums]
  if (nums.length === 2)
    return [
      [nums[0], nums[1]],
      [nums[1], nums[0]],
    ]
  let ans = []
  for (const i of permute(nums.slice(1))) {
    for (let j = 0; j < i.length+1; j++) {
      let temp = [...i]
      temp.splice(j, 0, nums[0])
      ans.push(temp)
    }
  }
  return ans
}

旋转图像 ​

nums[i] <==> nums[len - i - 1] 中轴两边对调

nums[i][j] <==> nums[j][i]] 斜轴两边对调

字母异位词分组 ​

排序一样的放一起

最大子数组和 ​

最简单的动态规划

js
function maxSubArray(nums) {
  for (let i = 1; i < nums.length; i++)
    nums[i] = nums[i] + (nums[i - 1] > 0 ? nums[i - 1] : 0)
  return Math.max(...nums)
}

跳跃游戏 ​

步数能否达到length

js
function canJump(nums) {
  const len = nums.length
  let step = 0
  for (let i = 0; i <= step; i++) {
    if (nums[i] + i > step) step = nums[i] + i
    if (step >= len - 1) return true
  }
  return false
}

合并区间 ​

用第一个值排序 然后合并

不同路径 ​

画m/n表格 新值为两边和 二维动态规划

js
function uniquePaths(m, n) {
  const net = new Array(m).fill(0).map(() => new Array(n).fill(0))
  for (let i = 0; i < m; i++) net[i][0] = 1
  for (let j = 0; j < n; j++) net[0][j] = 1
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      net[i][j] = net[i - 1][j] + net[i][j - 1]

  return net[m - 1][n - 1]
}

最小路径和 ​

二维动态规划 新值+=两边小值

爬楼梯 ​

一维动态规划

n数组 n1=1 n2=2种 ans[i] = ans[i - 1] + ans[i - 2]

颜色分类 ​

sort

子集 ​

循环上新

js
const subsets = nums => {
  const ans = [[]]
  for (const i of nums) for (const j of [...ans]) ans.push([...j, i])
  return ans
}