![image](https://user-gold-cdn.xitu.io/2019/1/13/16846a94b71eab7d?w=1069&h=585&f=jpeg&s=45061) ### 前言 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), 详见下题**。 #### 代码 ```js /** * @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](https://user-gold-cdn.xitu.io/2019/1/13/16846a93659d91a7?w=1776&h=1114&f=png&s=161355) #### 代码 ```js /** * @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)。具体思路见下图。 ```js // 暴力循环 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](https://user-gold-cdn.xitu.io/2019/1/13/16846a93671690df?w=2262&h=1336&f=png&s=298442) #### 代码 ```js /** * @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 时，排列如下： ```js L C I R E T O E S I I G E D H N ``` 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。 #### 思路这道题目我的解决思路是将字符串转化为二维数组。输入时按照**N**字形输入。最后逐行读取二维数组，并将二维数组中空的填充去除。返回最后的结果。通过推导可知。当行数为 2 时, 斜线上的字母数量为0。当行数为 3 时, 斜线上的字母数量为1。当行数为 4 时, 斜线上的字母数量为2。 ```js // 规律如下 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 ``` #### 代码 ```js /** * @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](https://user-gold-cdn.xitu.io/2019/1/13/16846a9365a3ff2a?w=1056&h=1042&f=png&s=143295) #### 思路本题的思路依然是使用对撞指针。我们在这里首先需要明确一个概念, 水的面积和高度和宽度有关。高度的取决于两条边框中**最小**的一边。具体思路见下图。 ![image](https://user-gold-cdn.xitu.io/2019/1/13/16846a9365aa028f?w=2136&h=1280&f=png&s=161320) #### 代码 ```js // 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)。 #### 代码 ```js /** * @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)**)。 #### 代码 ```js /** * @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](https://user-gold-cdn.xitu.io/2019/1/13/16846a936704a448?w=1966&h=1186&f=png&s=160760) #### 代码 ```js /** * @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] ] #### 思路此题拥有两种思路[字典法](https://www.cnblogs.com/pmars/p/3458289.html)与递归法。递归法较为容易理解。我采用的也是递归法，代码如下。 #### 代码 ```js /** * @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。否则继续向下迭代。 #### 代码 ```js /** * @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](https://user-gold-cdn.xitu.io/2019/1/13/16846a93ec7bc3c8?w=1036&h=1238&f=png&s=150013) #### 思路所谓的不同路径, 其实就是求排列组合。比如 3 * 7 的网格中。机器人从起点到终点所需要的步骤可以抽象为一个数组。[bottom, bottom, right, right, right, right, right, right]，所有的路径，即是这个数组的所有排列组合。另外一种思路, 第一行所有网格的可能路径数均为1。第一列所有网格的数可能的路径均为1。通过推导可以得到如下的表格。终点可能的路径为28。 ![image](https://user-gold-cdn.xitu.io/2019/1/13/16846a93f3f62a72?w=1402&h=124&f=png&s=14539) #### 代码 ```js /** * @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](https://user-gold-cdn.xitu.io/2019/1/13/16846a9433b3eec5?w=1028&h=1240&f=png&s=155595) #### 思路思路1使用递归法, 比较简单不在赘述思路2与**62. 不同路径**类似。但不同的是出现了障碍物这个变量。所以我们在初始化表格的第一行与第一列的时候需要格外的注意。假设一个 3 * 7的网格。具体思路见下图。假设地图如下 ![image](https://user-gold-cdn.xitu.io/2019/1/13/16846a9437743734?w=1408&h=140&f=png&s=15606) 初始化第一行(**如果第一行中的前一个为障碍物话, 那么后续可能路径的均为0**)，与第一列后(**如果第一列中的前一个为障碍物话, 那么后续可能路径的均为0**), 障碍物因为本身不能行走所以可能路径数直接设置为0。 ![image](https://user-gold-cdn.xitu.io/2019/1/13/16846a93f528392b?w=1406&h=134&f=png&s=11765) 接下来的方法同**62. 不同路径**一样。 #### 代码 ```js /** * @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, 因为卖出价格需要大于买入价格。 #### 思路最大利润即(最高卖出价格 - 最小买入价格)。我们只需要找到最小买入价格后, 计算每一天的利润，取最大值即可 #### 代码 ```js /** * @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 }; ``` --- ****