刷一下算法

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

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 = 0let left = 0let right = height.length - 1while (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.lengthconst 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) - 1if (dividend == INT_MIN && divisor == -1) return INT_MAX// 处理边界，防止转正数溢出// 除数绝对值最大，结果必为 0 或 1if (divisor == INT_MIN) {return dividend == divisor ? 1 : 0;}let isMinus = falseif (divisor < 0) isMinus = !isMinusif (dividend < 0) isMinus = !isMinuslet result = 0dividend = 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.lengthfor (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 + 1let right = length - 1while (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 = 0const length = s.length - 1s = [...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 - 1const 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 numconst numArr = Array.from(num)let tempNum = ''let contrast = numArr[0]let count = 0const length = numArr.length - 1numArr.forEach((item, index) => {if (item === contrast) {count++} else {tempNum += count + numArr[index - 1]contrast = itemcount = 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.lengthconst 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])}// 如果是去重后数组长度与原数组长度不一致,那就是有重复的,返回falseresult = [...new Set(row)].length === row.lengthif (!result) return resultresult = [...new Set(column)].length === column.lengthif (!result) return result}// 判断3x3的数组有没有重复for (let index = 0; index < rowLength; index++) {result = [...new Set(resetBoard[index])].length === resetBoard[index].lengthif (!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.lengthfor (let index = 0; index < length; index++) {// 排序后是从小到大的,这里有三个指针,一个是遍历数组的下标,一个是遍历数组下标的前一位,一个是数组的末尾// 如果大于目标值了,right就向左一步(就是让数字变小),如果小于目标值了,就让lef右一步(就是让数字变大)let left = index + 1let right = length - 1while (left < right) {// 当前总和数const tempSum = nums[index] + nums[left] + nums[right]const tempDiff = target - tempSumif (diff === null || Math.abs(tempDiff) < Math.abs(diff)) {diff = tempDiffsum = tempSum}if (tempSum < target) left++else if (tempSum > target) right--else if (tempSum == target) {sum = tempSumbreak}}}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.lengthlet 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.lengthfor (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 : addlongest = 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 = 0const length = s.lengthfor (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 : 7const 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 = ylet left = xlet right = xlet bottom = ylet count = 0let queensMap = new Map();queens.forEach(item => {let key = item.join("");queensMap.set(key, item);});let max = 7let 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.lengthlet num2Length = num2.lengthlet 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 + reverseIndex2const p2 = reverseIndex + reverseIndex2 + 1// 相乘再加进位,这里的p2就是上一循环的进位p1let 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.lengthconst needleLen = needle.lengthfor (let index = 0; index < length; index++) {const temp = haystack.slice(index, index + needleLen)if (temp === needle) return indexif (index === length - 1) return -1}};console.log(strStr('leetcode', 'leeto'))