刷一下算法

记录下自己的思路与能理解的解法,可能并不是最优解法,不定期持续更新~

1.盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 个人想法: 就是找出x轴与y轴相乘哪个最大, 水往下流, 所以两个y轴取最小的数

// /** // * 暴力解,这解法数据多的时候会很慢 // * @param {number[]} height // * @return {number} // */ // var maxArea = function (height) { // if (height.length <= 0) return height[0] // let maxNumber = 0 // for (let index = 0; index < height.length; index++) { // const item = height[index] // for (let i = index; i < height.length; i++) { // const diff = i - index // const num = diff * Math.min(height[i], item) // maxNumber = Math.max(maxNumber,num) // } // } // return maxNumber // }; /** * 双指针解法 */ var maxArea = function (height) { if (height.length <= 0) return height[0] let maxNumber = 0 let left = 0 let right = height.length - 1 while (left < right) { const num = (right - left) * Math.min(height[left], height[right]) maxNumber = Math.max(maxNumber, num) if (height[left] < height[right]) { left++ } else { right-- } } return maxNumber }; console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])) 2.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。

/** * @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) } } return [] }; 3.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 个人想法:每一个按键逐层递加,

/** * @param {string} digits * @return {string[]} */ var letterCombinations = function (digits) { if (digits.length == 0) return []; const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' }; const length = digits.length const queue = [] queue.push('') for (let i = 0; i < length; i++) { const levelSize = queue.length; // 当前层的节点个数 for (let u = 0; u < levelSize; u++) { const current = queue.shift() const letters = map[digits[i]] for (const l of letters) { queue.push(current + l); // 生成新的字母串入列 } } } return queue }; console.log(letterCombinations("232"))

4.两数相除

会溢出,这是我能解的程度了,正确的看不懂 /** * @param {number} dividend * @param {number} divisor * @return {number} */ var divide = function (dividend, divisor) { const INT_MIN = -Math.pow(2, 31) const INT_MAX = Math.pow(2, 31) - 1 if (dividend == INT_MIN && divisor == -1) return INT_MAX // 处理边界，防止转正数溢出 // 除数绝对值最大，结果必为 0 或 1 if (divisor == INT_MIN) { return dividend == divisor ? 1 : 0; } let isMinus = false if (divisor < 0) isMinus = !isMinus if (dividend < 0) isMinus = !isMinus let result = 0 dividend = Math.abs(dividend) divisor = Math.abs(divisor) if (dividend === divisor) { result = 1 } else { while (dividend > divisor) { dividend = dividend - Math.abs(divisor) console.log(dividend, divisor) result++ } } return isMinus ? -result : result }; console.log(divide(-10, 3)) 5.三数之和

个人题目理解: 1.三个数加起来为0 2.下标不能一样 3.数组不能一样

用三个循环的方式也可以,就是会溢出 注意测试用例太多的时候别在里面打log... var threeSum = function (nums) { nums.sort((a, b) => a - b) //排序 const arr = [] //记录符合条件的数组 const length = nums.length for (let i = 0; i < length; i++) { if (nums[i] > 0) break; if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重 // nums[i] 为"定数",与左右三个数相加,符合条件(为0)的添加进数组 let left = i + 1 let right = length - 1 while (left < right) { const sum = nums[i] + nums[left] + nums[right] if (sum === 0) { arr.push([nums[i], nums[left], nums[right]]) while (left < right && nums[left] == nums[left + 1]) left++ // 去重 while (left < right && nums[right] == nums[right - 1]) right-- // 去重 left++ right-- } else if (sum < 0) { // 数字太小,向右移 left++ } else if (sum > 0) { // 数字太大,向左移 right-- } } } return arr }; console.log(threeSum([-1,0,1,2,-1,-4])) 6.N 字形变换

var convert = function (s, numRows) { if (numRows === 1 || s.length <= numRows) { return s; } const result = Array(numRows).fill(''); let row = 0; let direction = -1; for (let i = 0; i < s.length; i++) { result[row] += s[i]; if (row === 0 || row === numRows - 1) { direction *= -1; } row += direction; } return result.join(''); }; 就是先准备numRows.length个数组，假设是3,依次从左到右，从上到下将字符串推进数组，再转为字符串输出 /** * @param {string} s * @param {number} numRows * @return {string} */ var convert = function(s, numRows) { let result = [] let resultStr = '' let state = 'add' let pointer = 0 const length = s.length - 1 s = [...s] s.forEach((item, index) => { if (state === 'add') { result[pointer] = result[pointer] === undefined ? [item] : [...result[pointer], item] pointer++ if (pointer === numRows - 1) state = 'minus' } else { result[pointer] = result[pointer] === undefined ? [item] : [...result[pointer], item] pointer-- if (pointer === 0) state = 'add' } }) result.flat(Infinity).forEach(item => resultStr += item) return resultStr }; pointer-- if (pointer === 0) state = 'add' } }) return result.flat(Infinity).join('') }; 7.旋转图像

个人理解:第一排对应右边第一排,第二排对应右边第二排…以此类推,那么拿到长度后,从右边开始递减赋值.例如第一排123对应每排数组的第length - 第一排的位置,

/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */ var rotate = function (matrix) { const length = matrix[0].length - 1 const copyMatrix = JSON.parse(JSON.stringify(matrix)) copyMatrix.forEach((item, index) => { item.forEach((i, key) => { matrix[key][length - index] = i }) return item }) return matrix }; console.log(rotate([ [5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16] ]), '------------') 8.组合总和

/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum = function (candidates, target) { const result = [] const deep = (consistute, diff, pointer) => { // 到数组尽头了停止递归 if (pointer === candidates.length) return; // target已经被整减,可以添加数组,并且已经没有值了,无需往下执行 if (diff === 0) { result.push(consistute) return } // 先跳过一部分,例如该例子target是7,7>3会进入if分支,7-3=4再次进入递归来到if分支,diff变成4的时候 // 4依然>3,4-3=1,1<3,这就进行不下去了. // 所以需要在第一步7-3时,进入递归,递归中再次进入递归(第一个递归,指针需要+1),那么就变成diff 4 - 2 // 然后diff变成2,进入if分支的deep ,2-2==0,return出去 deep(consistute, diff, pointer + 1) if (diff - candidates[pointer] >= 0) { deep([...consistute, candidates[pointer]], diff - candidates[pointer], pointer) } } deep([], target, 0) return result }; console.log(combinationSum([7, 6, 3, 2], 7), '------------') 9. 外观数列

个人想法:就是数数,数几个一样的,比如"1",就是一个一,那就写作"11",下一次就是两个一,就写作"21",再下次就是一个二一个一,写作’1211’…以此类推

/** * @param {number} n * @return {string} */ var countAndSay = function(n) { const deep = (remainRow, num) => { if (remainRow === 0) return num const numArr = Array.from(num) let tempNum = '' let contrast = numArr[0] let count = 0 const length = numArr.length - 1 numArr.forEach((item, index) => { if (item === contrast) { count++ } else { tempNum += count + numArr[index - 1] contrast = item count = 1 } if (index === length) tempNum += count + item }) return deep(remainRow - 1, tempNum) } return deep(n - 1, '1') }; console.log(countAndSay(4)) 10. 有效的数独 个人想法:每一行、每一列、每个3x3去除’.'后,判断去重后数组长度是否与原数组长度一致,不一致就是出现多次,就无效

/** * @param {character[][]} board * @return {boolean} */ var isValidSudoku = function (board) { // 用来验证结果 let result = true // 其实这两个都是9,只是这么写灵活点 const length = board.length const rowLength = board[0].length // 用于"数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。"时盛放的容器 // 到时会将例子编写为变量的[ // [5,3,6,9,8], // [7,1,9,5,] // ..... // ] let resetBoard = Array.from({ length: length }).fill([]) for (let index = 0; index < length; index++) { // 装每一行去除'.'的数据 let row = [] // 装每一列去除'.'的数据 let column = [] for (let index2 = 0; index2 < rowLength; index2++) { if (board[index][index2] !== '.') { // 装进行 row.push(board[index][index2]) // 这部分是装进'resetBoard'那个步骤的, // 逻辑是:Math.floor(行 / 3) * 3 + Math.floor(列 / 3) // 举例子:第三行那个6,就是 (3 / 3) * 3 + (7 / 3) = 0 * 3 + 2.333 = 0 + 2 ,放在下标为2的位置 // 举例子:第四行那个6,就是 (4 / 3) * 3 + (4 / 3) = 1 * 3 + 1 = 3 + 1 ,放在下标为4的位置 const index3 = Math.floor(index / 3) * 3 + Math.floor(index2 / 3) resetBoard[index3] = [...resetBoard[index3], board[index][index2]] } // 装进列 if (board[index2][index] !== '.') column.push(board[index2][index]) } // 如果是去重后数组长度与原数组长度不一致,那就是有重复的,返回false result = [...new Set(row)].length === row.length if (!result) return result result = [...new Set(column)].length === column.length if (!result) return result } // 判断3x3的数组有没有重复 for (let index = 0; index < rowLength; index++) { result = [...new Set(resetBoard[index])].length === resetBoard[index].length if (!result) return result } return result }; console.log(isValidSudoku( [ ["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."], [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"], ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"], [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"], [".", ".", ".", ".", "8", ".", ".", "7", "9"] ])) 11.最接近的三数之和

个人理解: 不断相加, 减target最小的就替换

/** * @param {number[]} nums * @param {number} target * @return {number} */ var threeSumClosest = function (nums, target) { // 计算总数 let sum = 0 // 用来判断是否更接近target,如果是就替换 let diff = null // 排序 nums = nums.sort((a, b) => a - b) const length = nums.length for (let index = 0; index < length; index++) { // 排序后是从小到大的,这里有三个指针,一个是遍历数组的下标,一个是遍历数组下标的前一位,一个是数组的末尾 // 如果大于目标值了,right就向左一步(就是让数字变小),如果小于目标值了,就让lef右一步(就是让数字变大) let left = index + 1 let right = length - 1 while (left < right) { // 当前总和数 const tempSum = nums[index] + nums[left] + nums[right] const tempDiff = target - tempSum if (diff === null || Math.abs(tempDiff) < Math.abs(diff)) { diff = tempDiff sum = tempSum } if (tempSum < target) left++ else if (tempSum > target) right-- else if (tempSum == target) { sum = tempSum break } } } return sum }; console.log(threeSumClosest([-1, 2, 1, -4, 5, 0], -7)) /** * @param {number[]} nums * @param {number} target * @return {number} */ var threeSumClosest = function(nums, target) { if(nums.length==3) return nums[0]+nums[1]+nums[2] const len = nums.length let result = nums[0]+nums[1]+nums[2]; for (let i = 0; i < len-2; i++) { for (let j = i + 1; j < len-1; j++) { for (let k = j+1; k < len; k++) { // console.log(target - sum,nums[k]); if(Math.abs(nums[i] + nums[j] + nums[k] - target) < Math.abs(result - target)) { result = nums[i] + nums[j] + nums[k] } } } } return result }; 12.最长回文子串

思路: 就是一个字符串,某一截翻转前跟反转后要一致,如例子’babad’所示,遍历到第二位时,left 与 right指针都是1,于是符合条件,左右指针分别向两边挪一位,判断是否一致,如果一致就继续执行上面动作直至到达边界. 然后判断哪个回文子串最长,就返回

var longestPalindrome = function (s) { let longest = ''; let length = s.length for (let i = 0; i < length; i++) { // 奇数 const add = expandAroundCenter(s, i, i) // 偶数 const even = expandAroundCenter(s, i, i + 1) const diff = even.length > add.length ? even : add longest = longest.length > diff.length ? longest : diff } // 中心扩展法 function expandAroundCenter(s, left, right) { while (left >= 0 && right <= length && s[left] === s[right]) { left-- right++ } return s.slice(left + 1, right) } return longest; }; console.log(longestPalindrome("babad")) 13.罗马数字转整数

/** * @param {string} s * @return {number} */ var romanToInt = function(s) { const romeList = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 } let result = 0 const length = s.length for (let index = 0; index < length; index++) { // 先找出对应的数字 const value = romeList[s[index]] //如果含有特殊符号就减,否则就加 if (value < romeList[s[index + 1]]) { result -= value } else { result += value } } return result }; 14.整数转罗马数字

/** * @param {number} num * @return {string} */ var intToRoman = function (num) { let result = '' const remoList = { 1: 'I', 4: 'IV', 5: 'V', 9: 'IX', 10: 'X', 40: 'XL', 50: 'L', 90: 'XC', 100: 'C', 400: 'CD', 500: 'D', 900: 'CM', 1000: 'M' } // 数字数组 const numKey = Object.keys(remoList) // 简单判断下数字大小决定从哪里开始 let right = num > 40 ? numKey.length - 1 : 7 const deep = (num) => { // 如果能减的动就添加罗马数字,并且使num变为剩余数字 let diff = num - numKey[right] if (diff >= 0) { result += remoList[numKey[right]] num = diff } // 如果指针大于0 才减,以免尾数减不尽,如果num<0表示尾数减完了,就停止 // diff < numKey[right] 用来判断整数的情况,例如20-10 还有10,还要减当前数,所以right不用-- if (right > 0 && num > 0 && diff < numKey[right]) { right-- } else if (num <= 0) { return } deep(num) } deep(num) return result }; console.log(intToRoman(20)) /** * @param {number} num * @return {string} */ var intToRoman = function (num) { const arr = ['I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M']; const numArr = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000]; let str = ''; for (let i = numArr.length - 1; i >= 0; i--) { if (num >= numArr[i]) { str += arr[i]; num -= numArr[i]; i++ } } return str }; 15.可以攻击国王的皇后

在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。 给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。

//思路:从国王开始八个方向出发,记录第一个遇到的皇后 /** * @param {number[][]} queens * @param {number[]} king * @return {number[][]} */ var queensAttacktheKing = function(queens, king) { let y = king[0] let x = king[1] let top = y let left = x let right = x let bottom = y let count = 0 let queensMap = new Map(); queens.forEach(item => { let key = item.join(""); queensMap.set(key, item); }); let max = 7 let result = { 'left': undefined, 'right': undefined, 'top': undefined, 'bottom': undefined, 'upperLeft': undefined, 'upperRight': undefined, 'leftLower': undefined, 'rightLower': undefined, } while (max >= 0) { top-- left-- right++ bottom++ count++ max-- if (!result.top && queensMap.has(`${top}${x}`)) { result.top = queensMap.get(`${top}${x}`) } if (!result.left && queensMap.has(`${y}${left}`)) { result.left = queensMap.get(`${y}${left}`) } if (!result.right && queensMap.has(`${y}${right}`)) { result.right = queensMap.get(`${y}${right}`) } if (!result.bottom && queensMap.has(`${bottom}${x}`)) { result.bottom = queensMap.get(`${bottom}${x}`) } if (!result.upperLeft && queensMap.has(`${y - count}${x - count}`)) { result.upperLeft = queensMap.get(`${y - count}${x - count}`) } if (!result.upperRight && queensMap.has(`${y - count}${x + count}`)) { result.upperRight = queensMap.get(`${y - count}${x + count}`) } if (!result.leftLower && queensMap.has(`${y + count}${x - count}`)) { result.leftLower = queensMap.get(`${y + count}${x - count}`) } if (!result.rightLower && queensMap.has(`${y + count}${x + count}`)) { result.rightLower = queensMap.get(`${y + count}${x + count}`) } } return Object.values(result).filter(item => item) }; //大佬的脑子: var queensAttacktheKing = function(queens, king) { queen_pos = new Set(); for (const queen of queens) { let x = queen[0], y = queen[1]; queen_pos.add(x * 8 + y); } const ans = []; for (let dx = -1; dx <= 1; ++dx) { for (let dy = -1; dy <= 1; ++dy) { if (dx == 0 && dy == 0) { continue; } let kx = king[0] + dx, ky = king[1] + dy; while (kx >= 0 && kx < 8 && ky >= 0 && ky < 8) { let pos = kx * 8 + ky; if (queen_pos.has(pos)) { ans.push([kx, ky]); break; } kx += dx; ky += dy; } } } return ans; }; 16.字符串相乘

个人理解:可以拿张纸用乘法算一下,其实就是把我们平时的乘法运算逻辑变成代码

/** * @param {string} num1 * @param {string} num2 * @return {string} */ var multiply = function (num1, num2) { if (num1 === '0' || num2 === '0') return '0' let multiplication = [] let num1Length = num1.length let num2Length = num2.length let result = new Array(num1Length + num2Length).fill(0) // 从个位数开始乘 for (let reverseIndex = num1Length - 1; reverseIndex >= 0; reverseIndex--) { for (let reverseIndex2 = num2Length - 1; reverseIndex2 >= 0; reverseIndex2--) { const p1 = reverseIndex + reverseIndex2 const p2 = reverseIndex + reverseIndex2 + 1 // 相乘再加进位,这里的p2就是上一循环的进位p1 let sum = num1[reverseIndex] * num2[reverseIndex2] + result[p2] // 进位 result[p1] += Math.floor(sum / 10) result[p2] = sum % 10 } } if (result[0] === 0) result.shift() return result.join('') }; console.log(multiply('123', '456')) 17.找出字符串中第一个匹配项的下标 个人思路:比较简单,就一个个截取出来匹配正不正确

/** * @param {string} haystack * @param {string} needle * @return {number} */ var strStr = function (haystack, needle) { const length = haystack.length const needleLen = needle.length for (let index = 0; index < length; index++) { const temp = haystack.slice(index, index + needleLen) if (temp === needle) return index if (index === length - 1) return -1 } }; console.log(strStr('leetcode', 'leeto'))