Jico

leetcode

2022/04/27 Algorithm 共 9423 字，约 27 分钟

leetcode

[M]求最长回文字符串longestPalindrome

回文字符串即以中心元素左右对称的字符串结构 解题要点：

  • 双指针遍历，以index=0顺序遍历为基准，left– right++
  • mid为中心位，中心位可能包含至少一个，至多N个相同元素
  • index对应的值和right相同时，单指针right++递增，mid中心位拓展
    • 在拓展中心位的场景下，不需要考虑left–的情况，因为遍历从左至右，left都会包含 需要考虑的几种情况：
  • 所有字符无法回文时，返回第一个元素
var longestPalindrome = function(s) {
  const list = s.split(''), temp = []
  const everyOneIsSame = arr => arr.every((it, i, s) => it === s[0])
  for (let i = 0, len = list.length; i < len; i++) {
    // mid为中心位，可拓展多个相同元素
    let left = i - 1, right = i + 1, cur = list[i], mid = [cur]
    if (i === 0) {
      while (list[right] === list[i]) {
        mid.push(list[right])
        right ++
      }
    } else {
      while (left >= 0 && right <= len) {
        if (cur === list[right] && everyOneIsSame(mid)) {
          mid.push(list[right])
          right++
        } else if (list[left] === list[right]) {
          mid = [list[left], ...mid, list[right]]
          left--
          right++
        } else {
          break
        }
      }
    }
    temp[i] = mid
  }
  temp.sort((a, b) => b.length - a.length)
  return temp[0].join('')
};
longestPalindrome("babad") // bab或aba
longestPalindrome("abca") // a
longestPalindrome("bbbaad") // bbb
longestPalindrome("bbabbad") // bbabb
longestPalindrome("abbbc") // bbb

[L]两数之和twoSum

要点：

  • 一定要排除当前值，如果当前值为target / 2，很容易把当前值考虑进去
  • 这里是使用集合的形式，因为集合最开始是空的，所以不存在这个问题
var twoSum = function(nums, target) {
  const map = new Map()
  for (let i = 0, len = nums.length; i < len; i++) {
    let complete = target - nums[i]
    if (map.has(complete)) {
      return [map.get(complete), i]
    } else {
      map.set(nums[i], i)
    }
  }
};

[M]两数相加addTwoNumbers

要点：

  • 每一个节点的next都指向下一个节点，同样需要为一个ListNode结构
  • cur = cur.next移动节点，指向下一个
  • cur.next = new ListNode(val)将当前节点的next初始化为ListNode节点并赋值
var addTwoNumbers = function(l1, l2) {
  const result = new ListNode()
  let carry = 0, cur = result
  while(l1 !== null || l2 !== null) {
    let sum = 0
    if (l1 !== null) {
      sum += l1.val
      l1 = l1.next
    }
    if (l2 !== null) {
      sum += l2.val
      l2 = l2.next
    }
    sum += carry
    cur.next = new ListNode(sum % 10)
    carry = Math.floor(sum / 10)
    cur = cur.next
  }
  if (carry > 0) {
    cur.next = new ListNode(carry)
  }
  return result.next
};

[M]无重复字符的最长子串lengthOfLongestSubstring

var lengthOfLongestSubstring = function(s) {
  let list = s.split(''), cur = 0
  const temp = list.reduce((a, c) => {
    const index = (a[cur] || (a[cur] = [])).indexOf(c)
    if (index < 0) {
      a[cur].push(c)
    } else {
      const slice = a[cur].slice(index + 1).concat(c)
      cur++
      (a[cur] || (a[cur] = [])).push(...slice)
    }
    return a
  }, [])
  return temp.length ? temp.sort((a, b) => b.length - a.length)[0].length : 0
};

[M]三数之和threeSum

var threeSum = function(nums) {
  nums.sort((a, b) => a - b)
  let result = []
  for (let i = 0, len = nums.length; i < len - 2; i++) {
    if (i === 0 || nums[i] !== nums[i - 1]) {
      let start = i + 1, end = len - 1
      while (start < end) {
        let temp = [nums[i], nums[start], nums[end]]
        let sum = temp.reduce((a, c) => a + c, 0)
        if (sum === 0) {
          result.push(temp)
          start++
          end--
          while (start < end && nums[start] === nums[start - 1]) {
            start++
          }
          while (start < end && nums[end] === nums[end + 1]) {
            end --
          }
        } else if (sum < 0) {
          // 因为最开始排序了，所以需要移动指针，向更大的方向
          start++
        } else {
          // sum溢出了，需要指针向小的方向移动
          end--
        }
      }
    }
  }
  return result
};

[M]删除链表的倒数第 N 个结点removeNthFromEnd

var removeNthFromEnd = function(head, n) {
  // 边界问题，只有一个节点；使用双指针思路
  let preNode = new ListNode()
  preNode.next = head

  let n1 = n2 = preNode
  for (let i = 0; i <= n; i ++) {
    // n2提前三个身位，则当n2为null时，直接将n1 = n1.next.next即可
    n2 = n2.next
  }
  while (n2 !== null) {
    n1 = n1.next
    n2 = n2.next
  }
  n1.next = n1.next.next
  return preNode.next
};

[L]有效的括号isValid

var isValid = function(s) {
  let list = s.split(''), len = list.length
  if (len % 2 === 1) {
    return false
  }
  // 使用堆栈模拟
  const stack = []
  const map = new Map([
    ['(', ')'],
    ['{', '}'],
    ['[', ']']
  ])
  for (let i = 0; i < len; i++) {
    let hit = map.get(list[i])
    if (hit) {
      stack.push(hit)
    } else {
      if (list[i] !== stack.pop()) {
        return false
      }
    }
  }
  return stack.length === 0
};

[L]合并两个有序链表mergeTwoLists

var mergeTwoLists = function(list1, list2) {
  let startNode = new ListNode()
  let resultNode = startNode

  while(list1 !== null && list2 !== null) {
    if (list1.val < list2.val) {
      startNode.next = list1
      list1 = list1.next
    } else {
      startNode.next = list2
      list2 = list2.next
    }
    startNode = startNode.next
  }
  if (list1 !== null) {
    startNode.next = list1
  } else {
    startNode.next = list2
  }
  return resultNode.next
};

[M]两两交换链表中的节点swapPairs

var swapPairs = function(head) {
  let fakeNode = new ListNode()
  fakeNode.next = head
  let current = fakeNode
  // 交换需要借助三个节点；且当下面只存在一个节点时，不需要交换
  while(current.next !== null && current.next.next !== null) {
    let n1 = current.next
    let n2 = current.next.next
    current.next = n2
    n1.next = n2.next
    n2.next = n1
    current = n1
  }
  return fakeNode.next
};

[M]字母异位词分组groupAnagrams

步骤：

  • 检查是否为空数组
  • 建立一个长度为26的数组，起始值为0
  • 遍历所有字符串，将字母的出现频率放到数组的对应位置(利用ASCII码)
  • 遍历数组，按照相同字母出现频率进行分组归类(使用hashMap)
  • 遍历map，将结果返回

比较笨的方法：

  • 将字幕进行排序，看是否相同，相同的字母位置对应的原字母即互为异位
var groupAnagrams = function(strs) {
  if (strs.length === 1) {
    return [strs]
  }
  let result = []
  const map = new Map()
  for (let str of strs) {
    const arr26 = Array.from({length: 26}, _ => 0)
    for (let i = 0, len = str.length; i < len; i++) {
      // ASCII a=97
      const ascii = str.charCodeAt(i) - 97
      arr26[ascii]++
    }
    const key = arr26.join('_')
    if (map.has(key)) {
      map.set(key, [...map.get(key), str])
    } else {
      map.set(key, [str])
    }
  }
  for (let arr of map) {
    result.push(arr[1])
  }
  return result
};

[L]最大子数组和maxSubArray

核心：

  • 我们知道必须是连续的子数组之和
  • 我们只需要考虑下一个值和当前值+下一个值两者大小关系，取其大者；小的舍弃
var maxSubArray = function(nums) {
  const temp = []
  temp[0] = nums[0]
  for (let i = 1, len = nums.length; i < len; i++) {
    // temp中每一位都存储的是前面数字之和或者当前值其大者
    temp[i] = Math.max(nums[i] + temp[i - 1], nums[i])
  }
  let max = nums[0]
  for (let i = 1, len = temp.length; i < len; i++) {
    max = Math.max(max, temp[i])
  }
  // temp.sort((a, b) => b - a)
  return max
};

[M]螺旋矩阵spiralOrder

要点：

  • 如果数组为空，返回空数组
  • 定义4个边界以及当前方向
  • 当左边界小于等于右边界，且上边界小于等于下边界时，执行while循环；按照右，下，左，上的顺序，依次将路径上的字符添加到结果里
  • while循环结束后，返回结果
var spiralOrder = function(matrix) {
  if (matrix.length === 0) {
      return []
  }
  let top = 0, right = matrix[0].length - 1, bottom = matrix.length - 1, left = 0
  let direction = 'right', result = []
  while (left <= right && top <= bottom) {
    if (direction === 'right') {
      for (let i = left; i <= right; i++) {
        result.push(matrix[top][i])
      }
      top++
      direction = 'bottom'
    } else if (direction === 'bottom') {
      for (let i = top; i <= bottom; i++) {
        result.push(matrix[i][right])
      }
      right--
      direction = 'left'
    } else if (direction === 'left') {
      for (let i = right; i >= left; i--) {
        result.push(matrix[bottom][i])
      }
      bottom--
      direction = 'top'
    } else {
      for (let i = bottom; i >= top; i--) {
        result.push(matrix[i][left])
      }
      left++
      direction = 'right'
    }
  }
  return result
};

[M]跳跃游戏canJump

var canJump = function(nums) {
  // 贪心算法
  let maxJump = nums.length - 1
  for (let i = nums.length - 2; i >= 0; i--) {
    if (nums[i] + i >= maxJump) {
      maxJump = i
    }
  }
  return maxJump === 0
};

[M]合并区间merge

var merge = function(intervals) {
  if (intervals.length < 2) {
    return intervals
  }
  intervals.sort((a, b) => a[0] - b[0])
  let curr = intervals[0], result =[]
  for (let interval of intervals) {
    if (curr[1] >= interval[0]) {
      curr[1] = Math.max(curr[1], interval[1])
    } else {
      result.push(curr)
      curr = interval
    }
  }
  if (curr.length !== 0) {
    result.push(curr)
  }
  return result
};

[M]不同路径uniquePaths

var uniquePaths = function(m, n) {
  const memo = []
  for (let i = 0; i < n; i++) {
    memo.push([])
  }
  for (let row = 0; row < n; row++) {
    memo[row][0] = 1
  }
  for (let col = 0; col < m; col++) {
    memo[0][col] = 1
  }
  for (let row = 1; row < n; row++) {
    for (let col = 1; col < m; col++) {
      memo[row][col] = memo[row - 1][col] + memo[row][col - 1]
    }
  }
  return memo[n - 1][m - 1]
};

[L]加一plusOne

var plusOne = function(digits) {
  for (let i =digits.length - 1; i >= 0; i--) {
    if (digits[i] !== 9) {
      digits[i]++
      return digits
    } else {
      digits[i] = 0
    }
  }
  const result = [1, ...digits]
  return result
};

[L]爬楼梯climbStairs

var climbStairs = function(n) {
  // memo[i-2] 3
  // memo[i-1] 5
  // memo[i] = memo[i-2]+memo[i-1] 8
  const memo = []
  memo[1] = 1
  memo[2] = 2
  // 1,2
  // 1,1,1 2,1
  // 3 = memo[1]+memo[2]
  for (let i = 3; i < n; i++) {
    memo[i] = memo[i-2]+memo[i-1]
  }
  return memo[n]
};

[M]矩阵置零setZeroes

要点：

  • 检查并标记第一行和第一列是否有0(firstColHasZero和firstRowHasZero)
  • 使用第一行和第一列，来标记其余行列是有含有0
  • 接下来，利用第一行和第一列的标0情况，将matrix中的数字标0
  • 最后，处理第一行和第一列，如果firstColHasZero等于true，将第一列全设为0；如果firstRowHasZero等于true，将第一列全设为0
var setZeroes = function(matrix) {
  let firstColHasZero = false, firstRowHaszero = false
  // 检查第一列是否有0
  for (let i = 0;i < matrix.length; i++) {
    if(matrix[i][0] === 0) {
      firstColHasZero = true
    }
  }
  // 检查第一行是否有0
  for (let i = 0;i < matrix[0]; i++) {
    if(matrix[0][i] === 0) {
      firstRowHaszero = true
    }
  }
  // 使用第一行和第一列，来标记其余行列是否含有0
  for (let row = 1; row < matrix.length; row++) {
    for (let col = 1; col < matrix[0].length;col++) {
      if (matrix[row][col] === 0) {
        matrix[row][0] = 0
        matrix[0][col] = 0
      }
    }
  }
  // 接下来，利用第一行和第一列的标0情况，将matrix中的数字标0
  for (let row = 1; row < matrix.length; row++) {
    for (let col = 1; col < matrix[0].length; col++) {
      if (matrix[row][0] === 0 || matrix[0][col] === 0) {
        matrix[row][col] = 0
      }
    }
  }
  // 最后，处理第一行和第一列
  // 如果firstColHasZero等于true，将第一列全设为0
  if (firstColHasZero) {
    for (let i=0; i<matrix.length;i++) {
      matrix[i][0] = 0
    }
  }
  // 如果firstRowHaszero等于true，将第一行全设为0
  if (firstRowHaszero) {
    for (let i=0; i<matrix[0].length;i++) {
      matrix[0][i] = 0
    }
  }
  return matrix
};

[L]删除排序链表中的重复元素deleteDuplicates

var deleteDuplicates = function(head) {
  let current = head
  while(current !== null && current.next !== null) {
    if (current.val === current.next.val) {
      current.next = current.next.next
    } else {
      current = current.next
    }
  }
  return head
};

[H]接雨水

感觉这道题并不应该算hard难度，其实挺简单的，只要知道如何求当前index的雨水值就好：

  • 根据木桶原理，每一个坐标位置可以装下的雨水为：左侧最高点和右侧最高点较小者 减去自身高度
  • 这个左侧最高和右侧最高都可以包含自身
// 暴力解 复杂度n*n
var trap = function (height) {
  if (!height.length) {
    return 0
  }
  // 根据木桶原理，每一个坐标位置可以装下的雨水为：左侧最高点和右侧最高点较小者 减去自身高度
  let result = 0
  // 左右两个边界肯定不能装水，所以排除
  for (let i = 1, len = height.length; i < len - 1; i++) {
    let left_max = Math.max(...height.slice(0, i))
    let right_max = Math.max(...height.slice(i, len))
    let val = Math.min(left_max, right_max) - height[i]
    result += val > 0 ? val : 0
  }
  return result
};

// 双循环，提前计算每个点位左右两侧最大值，将复杂度降低到n
// ! 需要注意，这里有一个把简单问题复杂化的地方：计算左右两侧没有包含自身
var trap = function (height) {
  if (!height.length) {
    return 0
  }
  // 根据木桶原理，每一个坐标位置可以装下的雨水为：左侧最高点和右侧最高点较小者 减去自身高度
  let result = 0, len = height.length
  let left_max = [0]
  // 这里比较特殊，需要注意len-1为最后一个元素，因为是右边界，右侧最大值不存在，设为0
  let right_max = [0]
  let i = 1, j = len - 2
  while (i < len || j > 0) {
    left_max.push(Math.max(left_max[i - 1], height[i - 1]))
    right_max.unshift(Math.max(right_max[0], height[j + 1]))
    i++
    j--
  }

  // 左右两个边界肯定不能装水，所以排除
  for (let i = 1; i < len - 1; i++) {
    let val = Math.min(left_max[i], right_max[i]) - height[i]
    result += val > 0 ? val : 0
  }
  return result
};

// 最优解 通过双指针，一次遍历完成
function trap(height) {
  let l = 0, r = height.length - 1;
  let maxl = 0, maxr = 0;
  let res = 0;
  while(l < r) {
    maxl = Math.max(height[l], maxl);
    maxr = Math.max(height[r], maxr);
    if(maxl < maxr) {
      res += maxl - height[l];
      l++;
    } else {
      res += maxr - height[r];
      r--;
    }
  } 
  return res;
}
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]))

Search

    Table of Contents