leetcode 部分题解~~~~~~~~~~~~~一直更新~~~~~~~~~~~~~
发布于 8 个月前 作者 BengBu-YueZhang 1106 次浏览 来自 分享

image

前言

2018年年底, 呆了不到一年的公司就这样解散了。遥想当初3月份刚刚加入公司的时候, 公司刚刚拿到数亿的B轮融资。6月份又是数亿元的B+轮融资。又是换写字楼又是在外滩大屏幕上打广告好不热闹,结果12月公司就关门了。真是世事无常啊。

1. 两数之和

原题

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

给定 nums = [2, 7, 11, 15], target = 9。因为 nums[0] + nums[1] = 2 + 7 = 9。所以返回 [0, 1]

思路

最简单的方法是通过两层for循环进行遍历, 使用暴力的查找两个子元素。但是这种方法的时间复杂度为O(n^2)。在大数据量的测试用例的情况下执行时间超时。那么我们有什么办法可以将时间复杂度降下来吗?这时我们可以用到HashMap。通过HashMap我们可以将时间复杂度降为O(2n)。如果是有序数组的情况下, 时间复杂度可以是O(n), 详见下题

代码


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let hashMap = new Map()
  // 初始化hashMap
  for (let i = 0; i < nums.length; i++) {
    if (!hashMap.has(nums[i])) {
      hashMap.set(nums[i], i)
    }
  }
  for (let i = 0; i < nums.length; i++) {
    let diff = target - nums[i]
    if (hashMap.has(diff) && hashMap.get(diff) !== i) {
      return [i, hashMap.get(diff)]
    }
  }
};

167. 两数之和 II - 输入有序数组

本题是1. 两数之和的引伸问题。如果将无限数组变为有序数组, 有什么更好的办法解决问题吗?

思路

这一题我们可以使用对撞指针或者说双指针的思路解决它, 并可以将时间复杂度控制在O(n)。具体思路见下图。

image

代码

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
  const len = numbers.length
  let start = 0
  let end = len - 1
  while (start < end) {
    if (numbers[start] + numbers[end] === target) {
      return [start + 1, end + 1]
    } else if (numbers[start] + numbers[end] < target) {
      start += 1
    } else {
      end -= 1
    }
  }
  return []
};

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

原题

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

输入: “abcabcbb”。输出: 3 。解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

输入: “bbbbb”。输出: 1。解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

思路

比较简单的思路是依旧使用双层for循环。代码如下。时间复杂度为O(n^3)。indexOf的复杂度为O(n)。更好的解决办法是使用双指针配合HashMap。虽然使用了额外的空间。但是可以将时间复杂度为O(n)。具体思路见下图。


// 暴力循环
if (s.length === 0) return 0
if (s.length === 1) return 1
let maxLen = 0
for1: for (let i = 0; i < s.length; i++) {
  let str = s[i]
  for2: for (let j = i + 1; j < s.length; j++) {
    maxLen = Math.max(maxLen, str.length)
    if (str.indexOf(s[j]) < 0) {
      str += s[j]
      maxLen = Math.max(maxLen, str.length)
    } else {
      continue for1
    }
  }
}
return maxLen

image

代码


/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  // 使用双指针解决 + hash
  const len = s.length
  let hashMap = new Map()
  let start = 0
  let end = 0
  let maxLen = 0

  while (end < len) {
    if (!hashMap.has(s[end])) {
      hashMap.set(s[end], 1)
      maxLen = Math.max(maxLen, [...hashMap.keys()].length)
      end += 1
    } else {
      hashMap.delete(s[start])
      start += 1
    }
  }

  return maxLen
};

6. Z 字形变换

原题

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时,排列如下:

L   C   I   R
E T O E S I I G
E   D   H   N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:“LCIRETOESIIGEDHN”。

思路

这道题目我的解决思路是将字符串转化为二维数组。输入时按照N字形输入。最后逐行读取二维数组,并将二维数组中空的填充去除。返回最后的结果。通过推导可知。当行数为 2 时, 斜线上的字母数量为0。当行数为 3 时, 斜线上的字母数量为1。当行数为 4 时, 斜线上的字母数量为2。


// 规律如下
L A C I R
E T O E S

L   C   I   R
E T O E S I I G
E   D   H   N

L     D     R
E   O E   I I
E C   I H   N
T     S     G

代码

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
  if (numRows === 1) return s
  let result = []
  let matrix = []
  let rowCounter = 0
  let prevRowCounter = 0
  let colCounter = 0
  let prevColCounter = 0
  const other = numRows - 2
  for (let i = 0; i < numRows; i++) {
    matrix.push([])
  }
  // 填充二维数组
  for (let i = 0; i < s.length; i++) {
    matrix[rowCounter][colCounter] = s[i]
    if (prevRowCounter <= rowCounter) {
      prevRowCounter = rowCounter
      if (rowCounter >= numRows - 1) {
        rowCounter -= 1
        colCounter += 1
      } else {
        rowCounter += 1
      }
    } else {
      prevRowCounter = rowCounter
      if (rowCounter <= 0) {
        rowCounter += 1
      } else {
        rowCounter -= 1
        colCounter += 1
      }
    }
  }
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] !== undefined) {
        result.push(matrix[i][j])
      }
    }
  }
  return result.join('')
};

11. 盛最多水的容器

原题

image

思路

本题的思路依然是使用对撞指针。我们在这里首先需要明确一个概念, 水的面积和高度和宽度有关。高度的取决于两条边框中最小的一边。具体思路见下图。

image

代码


// https://leetcode-cn.com/explore/orignial/card/all-about-array/232/two-pointers/969/

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  if (height.length === 1 || height.length === 0) {
    return 0
  }
  
  const len = height.length
  let start = 0
  let end = len - 1
  let max = 0
  while (start < end) {
    max = Math.max(max, (Math.min(height[start], height[end]) * (end - start)))
    if (height[start] <= height[end]) {
      start += 1
    } else {
      end -= 1
    }
  }
  return max
};

15. 三数之和

原题

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为:[ [-1, 0, 1], [-1, -1, 2] ]

思路

最简单最暴力的方法是使用三层for循环进行查找。但是时间复杂度为O(n^3)。我们的目标是将时间复杂度降为O(n^2)。我们只需要将原数组进行排序后, 结合167. 两数之和 II - 输入有序数组这道题目的思路(对撞指针)就可以将时间复杂度控制在O(n^2)。

代码


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  let result = []
  let hashMap = new Map()
  // 容错处理
  if (nums.length < 3) return []  
  // 容错处理
  if (nums.length === 3) {
      if (nums[0] + nums[1] + nums[2] === 0) return [nums]
      return []
  }
  nums = nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length - 3; i++) {
      let start = i + 1
      let end = nums.length - 1
      let target = 0 - nums[i]
      while (start < end) {
          if (nums[start] + nums[end] === target) {
              let arr = [nums[i], nums[start], nums[end]]
              let key = arr.join('')
              if (!hashMap.has(key)) {
                  hashMap.set(key, true)
                  result.push(arr)
              }
              end -= 1
              start += 1
          } else if (nums[start] + nums[end] > target) {
              end -= 1
          } else {
              start += 1
          }
      }
  }
  return result
};

16. 最接近的三数之和

原题

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1。 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2)。

思路

本题的思路与15. 三数之和基本类似。区别在于我们需要在循环中记录的是最小的差值(Math.abs(target - sum))。

代码


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
  let diff = Infinity
  let sums = undefined
  if (nums.length <= 3) return nums.reduce((a, b) => a + b, 0)
  nums = nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length; i++) {
    let start = i + 1
    let end = nums.length - 1
    while (start < end) {
      if (Math.abs(target - (nums[i] + nums[start] + nums[end])) < diff) {
         // 最接近的和
         sums = nums[i] + nums[start] + nums[end]
         // 当前最小的差值
         diff = Math.abs(target - (nums[i] + nums[start] + nums[end]))
      }
      if (nums[i] + nums[start] + nums[end] > target) {
          end -= 1
      } else if (nums[i] + nums[start] + nums[end] < target) {
          start += 1
      } else {
          return target
      }
    }
  }
  return sums
};

20. 有效的括号

原题

给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。

  1. 输入: “()[]{}”, 输出: true
  2. 输入: “(]”, 输出: false

思路

本题的解决办法需要使用这个数据结构(javascript中我们使用数组进行模拟栈), 具体思路见下图

image

代码


/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  if (s.length === 0) return true
  if (s.length === 1) return false
  let queue = []
  for (let i = 0; i < s.length; i++) {
    if (!queue.length) {
      queue.push(s[i])
    } else {
      let tail = queue[queue.length - 1]
      if (s[i] === '}' && tail === '{') {
        queue.pop()
        continue
      } else if (s[i] === ']' && tail === '[') {
        queue.pop()
        continue
      } else if (s[i] === ')' && tail === '(') {
        queue.pop()
        continue
      } else {
        queue.push(s[i])
      }
    }
  }
  if (!queue.length) {
    return true
  } else {
    return false
  }
};


46. 全排列

原题

给定一个没有重复数字的序列,返回其所有可能的全排列。输入: [1,2,3]。 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路

此题拥有两种思路字典法与递归法。递归法较为容易理解。我采用的也是递归法,代码如下。

代码


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    
  let result = []
  
  if (nums.length <= 1) result = [nums]

  function exchange (title, arr) {
    for (let i = 0; i < arr.length; i++) {
      let cloneArr = [...arr]
      let newFirst = [...title, ...cloneArr.splice(i, 1)]
      if (cloneArr && cloneArr.length) {
        exchange(newFirst, cloneArr)
      } else {
        result.push(newFirst)
      }
    }
  }

  for (let i = 0; i < nums.length; i++) {
    let cloneArr = [...nums]
    let first = cloneArr.splice(i, 1)
    exchange(first, cloneArr)
  }
  
  return result
};

53. 最大子序和

原题

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

思路

如果要在O(n)的时间复杂度的情况下解开本题, 需要使用动态规划的思想。但是本人能力有限, 动态规划不是很懂。这里只能说一个大概的思路,敬请谅解。

我们从数组中的第一位开始循环求和

如果sum(和) < 0。接下来的一位next无论大于0还是小于0, 都应当取代当前的负数sum。因为如果next < 0, sum + next 将会更小, 所以应当舍弃之前的sum。如果next大于0, sum更应当从next开始重新计算。

如果sum(和) > 0。如果接下来的一位next与当前的sum的和大于MAX, next与当前sum的和将成为新的MAX。否则继续向下迭代。

代码


/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  if (nums.length <= 1) return nums[0]
  let sum = nums[0]
  let MAX = sum
  for (let i = 1; i < nums.length; i++) {
    if (sum >= 0) {
      if (sum + nums[i] >= MAX) {
        MAX = sum + nums[i]
      }
      sum = sum + nums[i]
    } else {
      if (nums[i] >= MAX) {
        MAX = nums[i]
      }
      sum = nums[i]
    }
  }
  return MAX
};

62. 不同路径

原题

image

思路

所谓的不同路径, 其实就是求排列组合。比如 3 * 7 的网格中。机器人从起点到终点所需要的步骤可以抽象为一个数组。[bottom, bottom, right, right, right, right, right, right],所有的路径,即是这个数组的所有排列组合。

另外一种思路, 第一行所有网格的可能路径数均为1。第一列所有网格的数可能的路径均为1。通过推导可以得到如下的表格。终点可能的路径为28。

image

代码


/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  // 思路1
  let matrix = []
  for (let i = 0; i < n; i++) {
    let arr = new Array(m).fill(1)
    matrix.push(arr)
  }
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]
    }
  }
  return matrix[n-1][m-1]

  // 思路二, 可行, 但是会超出时间限制
  let arr = []
  let hashMap = new Map()
  for (let i = 0; i < m - 1; i++) {
    arr.push('m')
  }
  for (let i = 0; i < n - 1; i++) {
    arr.push('n')
  }

  if (arr.length <= 1) return 1

  function exchange (title, arr) {
    for (let i = 0; i < arr.length; i++) {
      let cloneArr = [...arr]
      let newFirst = [...title, ...cloneArr.splice(i, 1)]
      if (cloneArr && cloneArr.length) {
        exchange(newFirst, cloneArr)
      } else {
        let key = newFirst.join('')
        if (!hashMap.has(key)) {
          hashMap.set(key, true)
        }
      }
    }
  }

  for (let i = 0; i < arr.length; i++) {
    let cloneArr = [...arr]
    let first = cloneArr.splice(i, 1)
    exchange(first, cloneArr)
  }
  return hashMap.size
};

63. 不同路径 II

原题

image

思路

思路1使用递归法, 比较简单不在赘述

思路2与62. 不同路径类似。但不同的是出现了障碍物这个变量。所以我们在初始化表格的第一行与第一列的时候需要格外的注意。假设一个 3 * 7的网格。具体思路见下图。

假设地图如下

image

初始化第一行(如果第一行中的前一个为障碍物话, 那么后续可能路径的均为0),与第一列后(如果第一列中的前一个为障碍物话, 那么后续可能路径的均为0), 障碍物因为本身不能行走所以可能路径数直接设置为0。

image

接下来的方法同62. 不同路径一样。

代码


/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
  // 思路1, 使用动态规划和递归
  // 没有通过大数据量的测试用例
  let counter = 0
  const targetX = obstacleGrid[0].length - 1
  const targetY = obstacleGrid.length - 1
  /**
   * @param {number} x 当前矩阵的x坐标
   * @param {number} y 当前矩阵的y坐标
   * @param {string} direction 方向 right, bottom
   */
  const pathfinding = (x, y, direction) => {
    switch (direction) {
      case 'right':
        x = x + 1
        break
      case 'bottom':
        y = y + 1
        break
      default:
        break
    }
    // 遇到障碍物或者越界的情况下, 思路一条
    if (y >= targetY + 1) {
      return
    }
    if (x >= targetX + 1) {
      return
    }
    if (obstacleGrid[y][x] === 1) {
      return
    }
    if (x === targetX && y === targetY) {
      counter += 1
    } else if (x !== targetX && y === targetY) {
      // 只能向右走
      pathfinding(x, y, 'right')
    } else if (x === targetX && y !== targetY) {
      // 只能向下走
      pathfinding(x, y, 'bottom')
    } else {
      // 可能向右走
      // 可能向下走
      pathfinding(x, y, 'right')
      pathfinding(x, y, 'bottom')
    }
  }
  pathfinding(0, 0)
  return counter

  // 思路二
  // 带有条件的初始化第一行与第一列
  // 初始化x方向
  // 初始化y方向
  const xLen = obstacleGrid[0].length
  const yLen = obstacleGrid.length
  for (let i = 0; i < xLen; i++) {
    if (i - 1 >= 0) {
      if (obstacleGrid[0][i-1] === 0) {
        obstacleGrid[0][i] = 0
      } else if (obstacleGrid[0][i-1] === 1 && obstacleGrid[0][i] !== 1) {
        obstacleGrid[0][i] = 1
      } else if (obstacleGrid[0][i] == 1) {
        obstacleGrid[0][i] = 0
      }
    } else {
      if (obstacleGrid[0][i] === 0) {
        obstacleGrid[0][i] = 1
      } else {
        obstacleGrid[0][i] = 0
      }
    }
  }
  for (let i = 0; i < yLen; i++) {
    if (i - 1 >= 0) {
      if (obstacleGrid[i-1][0] === 0) {
        obstacleGrid[i][0] = 0
      } else if (obstacleGrid[i-1][0] !== 0 && obstacleGrid[i][0] !== 1) {
        obstacleGrid[i][0] = 1
      } else if (obstacleGrid[i-1][0] !== 0 && obstacleGrid[i][0] === 1) {
        obstacleGrid[i][0] = 0
      }
    }
  }
  for (let i = 1; i < yLen; i++) {
    for (let j = 1; j < xLen; j++) {
      if (obstacleGrid[i][j] === 1) {
        obstacleGrid[i][j] = 0
      } else {
        obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
      }
    }
  }

  return obstacleGrid[yLen - 1][xLen - 1]
};

121. 买卖股票的最佳时机

原题

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

思路

最大利润即(最高卖出价格 - 最小买入价格)。我们只需要找到最小买入价格后, 计算每一天的利润,取最大值即可

代码


/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {

  if (prices.length === 0) return 0  
  
  // 利润
  let result = 0
  
  let min = prices[0]
  // 找到最小的谷之后的最大的峰
  for (let i = 0; i < prices.length; i++) {
      if (prices[i] < min) {
          min = prices[i]   
      }
      result = Math.max(prices[i] - min, result)
  } 
  
  return result
};



回到顶部