記錄下自己的思路與能理解的解法,可能并不是最優(yōu)解法,不定期持續(xù)更新~

1.盛最多水的容器

給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，第 i 條線的兩個(gè)端點(diǎn)是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
返回容器可以儲(chǔ)存的最大水量。
個(gè)人想法: 就是找出x軸與y軸相乘哪個(gè)最大, 水往下流, 所以兩個(gè)y軸取最小的數(shù)

        // /**
        //  * 暴力解,這解法數(shù)據(jù)多的時(shí)候會(huì)很慢
        //  * @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.兩數(shù)之和

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個(gè) 整數(shù)，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案。

/**
 * @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.電話號(hào)碼的字母組合

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。
個(gè)人想法:每一個(gè)按鍵逐層遞加,

    /**
         * @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; // 當(dāng)前層的節(jié)點(diǎn)個(gè)數(shù)
                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.兩數(shù)相除

會(huì)溢出,這是我能解的程度了,正確的看不懂

        /**
         * @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
            // 處理邊界，防止轉(zhuǎn)正數(shù)溢出
            // 除數(shù)絕對(duì)值最大，結(jié)果必為 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.三數(shù)之和

個(gè)人題目理解:
1.三個(gè)數(shù)加起來(lái)為0
2.下標(biāo)不能一樣
3.數(shù)組不能一樣

• 用三個(gè)循環(huán)的方式也可以,就是會(huì)溢出

	注意測(cè)試用例太多的時(shí)候別在里面打log...
        var threeSum = function (nums) {
            nums.sort((a, b) => a - b) //排序
            const arr = [] //記錄符合條件的數(shù)組
            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] 為"定數(shù)",與左右三個(gè)數(shù)相加,符合條件(為0)的添加進(jìn)數(shù)組
                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) {
                        // 數(shù)字太小,向右移
                        left++
                    } else if (sum > 0) {
                        // 數(shù)字太大,向左移
                        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('');
        };




就是先準(zhǔn)備numRows.length個(gè)數(shù)組，假設(shè)是3,依次從左到右，從上到下將字符串推進(jìn)數(shù)組，再轉(zhuǎn)為字符串輸出
/**
 * @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.旋轉(zhuǎn)圖像

個(gè)人理解:第一排對(duì)應(yīng)右邊第一排,第二排對(duì)應(yīng)右邊第二排…以此類推,那么拿到長(zhǎng)度后,從右邊開始遞減賦值.例如第一排123對(duì)應(yīng)每排數(shù)組的第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) => {
                // 到數(shù)組盡頭了停止遞歸
                if (pointer === candidates.length) return;
                // target已經(jīng)被整減,可以添加數(shù)組,并且已經(jīng)沒(méi)有值了,無(wú)需往下執(zhí)行
                if (diff === 0) {
                    result.push(consistute)
                    return
                }
                // 先跳過(guò)一部分,例如該例子target是7,7>3會(huì)進(jìn)入if分支,7-3=4再次進(jìn)入遞歸來(lái)到if分支,diff變成4的時(shí)候
                // 4依然>3,4-3=1,1<3,這就進(jìn)行不下去了.
                // 所以需要在第一步7-3時(shí),進(jìn)入遞歸,遞歸中再次進(jìn)入遞歸(第一個(gè)遞歸,指針需要+1),那么就變成diff 4 - 2
                // 然后diff變成2,進(jìn)入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. 外觀數(shù)列

個(gè)人想法:就是數(shù)數(shù),數(shù)幾個(gè)一樣的,比如"1",就是一個(gè)一,那就寫作"11",下一次就是兩個(gè)一,就寫作"21",再下次就是一個(gè)二一個(gè)一,寫作’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. 有效的數(shù)獨(dú)

• 個(gè)人想法:每一行、每一列、每個(gè)3x3去除’.'后,判斷去重后數(shù)組長(zhǎng)度是否與原數(shù)組長(zhǎng)度一致,不一致就是出現(xiàn)多次,就無(wú)效

   /**
         * @param {character[][]} board
         * @return {boolean}
         */
        var isValidSudoku = function (board) {
            // 用來(lái)驗(yàn)證結(jié)果
            let result = true
            // 其實(shí)這兩個(gè)都是9,只是這么寫靈活點(diǎn)
            const length = board.length
            const rowLength = board[0].length
            // 用于"數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。"時(shí)盛放的容器
            // 到時(shí)會(huì)將例子編寫為變量的[
            //     [5,3,6,9,8],
            //     [7,1,9,5,]
            //     .....
            // ]
            let resetBoard = Array.from({
                length: length
            }).fill([])
            for (let index = 0; index < length; index++) {
                // 裝每一行去除'.'的數(shù)據(jù)
                let row = []
                // 裝每一列去除'.'的數(shù)據(jù)
                let column = []
                for (let index2 = 0; index2 < rowLength; index2++) {
                    if (board[index][index2] !== '.') {
                        // 裝進(jìn)行
                        row.push(board[index][index2])
                        // 這部分是裝進(jìn)'resetBoard'那個(gè)步驟的,
                        // 邏輯是:Math.floor(行 / 3) * 3 + Math.floor(列 / 3)
                        // 舉例子:第三行那個(gè)6,就是 (3 / 3) * 3 + (7 / 3) = 0 * 3 + 2.333 = 0 + 2 ,放在下標(biāo)為2的位置
                        // 舉例子:第四行那個(gè)6,就是 (4 / 3) * 3 + (4 / 3) = 1 * 3 + 1 = 3 + 1 ,放在下標(biāo)為4的位置
                        const index3 = Math.floor(index / 3) * 3 + Math.floor(index2 / 3)
                        resetBoard[index3] = [...resetBoard[index3], board[index][index2]]
                    }
                    // 裝進(jìn)列
                    if (board[index2][index] !== '.') column.push(board[index2][index])
                }
                // 如果是去重后數(shù)組長(zhǎng)度與原數(shù)組長(zhǎng)度不一致,那就是有重復(fù)的,返回false
                result = [...new Set(row)].length === row.length
                if (!result) return result
                result = [...new Set(column)].length === column.length
                if (!result) return result
            }
            // 判斷3x3的數(shù)組有沒(méi)有重復(fù)
            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.最接近的三數(shù)之和

個(gè)人理解: 不斷相加, 減target最小的就替換

      /**
         * @param {number[]} nums
         * @param {number} target
         * @return {number}
         */
        var threeSumClosest = function (nums, target) {
            // 計(jì)算總數(shù)
            let sum = 0
            // 用來(lái)判斷是否更接近target,如果是就替換
            let diff = null
            // 排序
            nums = nums.sort((a, b) => a - b)
            const length = nums.length
            for (let index = 0; index < length; index++) {
                // 排序后是從小到大的,這里有三個(gè)指針,一個(gè)是遍歷數(shù)組的下標(biāo),一個(gè)是遍歷數(shù)組下標(biāo)的前一位,一個(gè)是數(shù)組的末尾
                // 如果大于目標(biāo)值了,right就向左一步(就是讓數(shù)字變小),如果小于目標(biāo)值了,就讓lef右一步(就是讓數(shù)字變大)
                let left = index + 1
                let right = length - 1
                while (left < right) {
                    // 當(dāng)前總和數(shù)
                    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.最長(zhǎng)回文子串

思路: 就是一個(gè)字符串,某一截翻轉(zhuǎn)前跟反轉(zhuǎn)后要一致,如例子’babad’所示,遍歷到第二位時(shí),left 與 right指針都是1,于是符合條件,左右指針?lè)謩e向兩邊挪一位,判斷是否一致,如果一致就繼續(xù)執(zhí)行上面動(dòng)作直至到達(dá)邊界.
然后判斷哪個(gè)回文子串最長(zhǎng),就返回

        var longestPalindrome = function (s) {
            let longest = '';
            let length = s.length
            for (let i = 0; i < length; i++) {
                // 奇數(shù)
                const add = expandAroundCenter(s, i, i)
                // 偶數(shù)
                const even = expandAroundCenter(s, i, i + 1)

                const diff = even.length > add.length ? even : add
                longest = longest.length > diff.length ? longest : diff
            }


            // 中心擴(kuò)展法
            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.羅馬數(shù)字轉(zhuǎn)整數(shù)

/**
 * @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++) {
      // 先找出對(duì)應(yīng)的數(shù)字
        const value = romeList[s[index]]
        //如果含有特殊符號(hào)就減,否則就加
        if (value < romeList[s[index + 1]]) {
          result -= value
        } else {
          result += value
        }
      }
      return result
};

14.整數(shù)轉(zhuǎn)羅馬數(shù)字

       /**
         * @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'
            }
            // 數(shù)字?jǐn)?shù)組
            const numKey = Object.keys(remoList)
            // 簡(jiǎn)單判斷下數(shù)字大小決定從哪里開始
            let right = num > 40 ? numKey.length - 1 : 7
            const deep = (num) => {
                // 如果能減的動(dòng)就添加羅馬數(shù)字,并且使num變?yōu)槭Ｓ鄶?shù)字
                let diff = num - numKey[right]
                if (diff >= 0) {
                    result += remoList[numKey[right]]
                    num = diff
                }
                // 如果指針大于0 才減,以免尾數(shù)減不盡,如果num<0表示尾數(shù)減完了,就停止
                // diff < numKey[right] 用來(lái)判斷整數(shù)的情況,例如20-10 還有10,還要減當(dāng)前數(shù),所以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.可以攻擊國(guó)王的皇后

在一個(gè) 8x8 的棋盤上，放置著若干「黑皇后」和一個(gè)「白國(guó)王」。
給定一個(gè)由整數(shù)坐標(biāo)組成的數(shù)組 queens ，表示黑皇后的位置；以及一對(duì)坐標(biāo) king ，表示白國(guó)王的位置，返回所有可以攻擊國(guó)王的皇后的坐標(biāo)(任意順序)。

//思路:從國(guó)王開始八個(gè)方向出發(fā),記錄第一個(gè)遇到的皇后
/**
 * @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.字符串相乘

個(gè)人理解:可以拿張紙用乘法算一下,其實(shí)就是把我們平時(shí)的乘法運(yùn)算邏輯變成代碼

        /**
         * @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)
            // 從個(gè)位數(shù)開始乘
            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
                    // 相乘再加進(jìn)位,這里的p2就是上一循環(huán)的進(jìn)位p1
                    let sum = num1[reverseIndex] * num2[reverseIndex2] + result[p2]
                    // 進(jìn)位
                    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.找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo)

• 個(gè)人思路:比較簡(jiǎn)單,就一個(gè)個(gè)截取出來(lái)匹配正不正確

        /**
         * @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'))

18.搜索旋轉(zhuǎn)排序數(shù)組

• 說(shuō)是中級(jí)難度,但是簡(jiǎn)單到有點(diǎn)不可置信,可能因?yàn)槲覜](méi)有極致優(yōu)化速度跟內(nèi)存…

    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    var search = function (nums, target) {
      return nums.findIndex(v => v === target)
    };
    console.log(search([4, 5, 6, 7, 0, 1, 2], 0))


    var search = function (nums, target) {
      let result = -1
      let length = nums.length
      if (target < nums[0]) {
        for (let index = length - 1; index >= 0; index--) {
          const item = nums[index];
          if (item === target) return index
        }
      } else {
        for (let index = 0; index < length; index++) {
          const item = nums[index];
          if (item === target) return index
        }
      }

      return result
    };
    console.log(search([4, 5, 6, 7, 0, 1, 2], 0))

19. 刪除有序數(shù)組中的重復(fù)項(xiàng) II

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
			//用來(lái)判斷是否超過(guò)2
           let count = 0
           //下標(biāo)
            let left = 0
            while (left < nums.length) {
            //如果當(dāng)前的數(shù)跟上一位一樣count就+1,否則就重置進(jìn)入下一循環(huán)
                if (nums[left] === nums[left - 1]) {
                    count++
                    //超過(guò)2就刪除一位 ,否則進(jìn)入下一循環(huán), splice會(huì)改變?cè)瓟?shù)組,所以不++
                    count > 1 ? nums.splice(left, 1) : left++
                } else {
                    count = 0
                    left++
                }
            }
            return nums.length
};

20.在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

    var searchRange = function (nums, target) {
      // 先找到第一個(gè)元素,如果沒(méi)有找到說(shuō)明整個(gè)數(shù)組都沒(méi)有,直接返回[-1,-1]
      let point = nums.findIndex(item => item === target)
      if (point === -1) return [-1, -1]
      const length = nums.length
      let left = point
      let right = length - 1
      let first = point
      let end = false
      // 現(xiàn)在就直接從后面開始找最后面的,找到立馬返回
      while (left <= right) {
        if (nums[right] === target) {
          return [first, right]
        } else {
          right--
        }
      };
    };



    // 這種方式vscode是可以運(yùn)行的,不知道為什么力扣報(bào)沒(méi)有findLastIndex這個(gè)方法
    var searchRange = function (nums, target) {
      let left = nums.findIndex(item => item === target)
      if (left === -1) return [-1, -1]
      let right = nums.findLastIndex(item2 => item2 === target)
      return [left, right]
    }
    console.log(searchRange([5, 7, 7, 8, 8, 10], 8))

21.跳躍游戲

        var canJump = function (nums) {
            // 必須到達(dá)end下標(biāo)的數(shù)字
            let end = nums.length - 1;

            for (let i = nums.length - 2; i >= 0; i--) {
                if (end - i <= nums[i]) {
                    end = i;
                }
            }

            return end == 0;
        };
        // console.log(canJump([2, 0, 0]))
        // console.log(canJump([3,2,1,0,4]))
        // console.log(canJump([2, 0, 2]))
        // console.log(canJump([1,0,2]))
        // console.log(canJump([0, 2, 3]))
        console.log(canJump([2,3,1,1,4]))

22.全排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
            const result = [];
            const length = nums.length
            const deep = (arr) => {
                if (arr.length === length) {
                    result.push([...arr])
                    return
                }
                for (const item of nums) {
                    if(!arr.includes(item)){
                        arr.push(item)
                        deep(arr)
                        arr.pop()
                    }
                }
            }
            deep([])
            return result

};

23.多數(shù)元素

/**
 * @param {number[]} nums
 * @return {number}
 */
 //大佬做法
var majorityElement = function(nums) {
    const n = nums.length;
    nums = nums.sort((a,b) => a-b);
    if (nums[0] === nums[Math.floor(n / 2)]) {
        return nums[0]
    } else if (nums[n - 1] === nums[Math.floor(n / 2)]) {
        return nums[n - 1];
    }
    return nums[Math.floor(n / 2)]
};

//我的做法
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
            const target = Math.floor(nums.length / 2)
            const count = {}
            nums.forEach(item => {
                count[item] ? count[item]++ : count[item] = 1
            })
            for (const key in count) {
                if (count[key] > target) return key
            }
};

24.輪轉(zhuǎn)數(shù)組

        /**
         * @param {number[]} nums
         * @param {number} k
         * @return {void} Do not return anything, modify nums in-place instead.
         */
        var rotate = function (nums, k) {
            if (k > nums.length) {
                // 這種寫法需要的時(shí)間比較長(zhǎng),就是一遍遍地將最后一個(gè)往第一個(gè)加
                for (let index = 0; index < k; index++) {
                    nums.unshift(nums.pop())
                }
            } else {
                // 這個(gè)就快一點(diǎn),直接裁剪最后的部分往前加,但是當(dāng)k大于nums長(zhǎng)度的時(shí)候就不行
                nums.unshift(...nums.splice(nums.length - k, nums.length))
            }
            return nums
        };
        console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3))

25.買賣股票的最佳時(shí)機(jī)

        /**
         * @param {number[]} prices
         * @return {number}
         */
        let maxProfit = function (prices) {
            let diff = 0
            let minValue = prices[0]
            for (const item of prices) {
                diff = Math.max(diff, item - minValue)
                minValue = Math.min(item, minValue)
            }
            return diff
        };
        console.log(maxProfit([7, 5, 1, 3, 6, 4]))

26.買賣股票的最佳時(shí)機(jī) II

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
           //今天比昨天錢多就累計(jì)起來(lái)
            let totle = 0
            const length = prices.length
            for (let index = 1; index < length; index++) {
                const item = prices[index];
                const diff = item - prices[index - 1]
                if (diff > 0) totle += diff
            }
            return totle
};

27.H 指數(shù)

用人話解釋這道題是這樣的:因?yàn)閔是文章數(shù)量， 有3個(gè)超過(guò)引用3次的文章，所以是3， 如果5或6，就需要是有5篇超過(guò)被引用5次的文章，6同理。

        /**
         * @param {number[]} citations
         * @return {number}
         */
        var hIndex = function (citations) {
            citations = citations.sort((a, b) => a - b)
            let result = 0;
            let index = citations.length - 1
            while (index >= 0 && citations[index] > result) {
                result++
                index--
            }
            return result
        };
        console.log(hIndex([0, 1]))

28.加油站

        /**
         * @param {number[]} gas
         * @param {number[]} cost
         * @return {number}
         */
        var canCompleteCircuit = function (gas, cost) {
            let totalGas = 0; // 總剩余油量
            let currentGas = 0; // 當(dāng)前起點(diǎn)的剩余油量
            let start = 0; // 起點(diǎn)
            let length = gas.length
            for (let index = 0; index < length; index++) {
                totalGas += gas[index] - cost[index]
                currentGas += gas[index] - cost[index]
                if (currentGas < 0) {
                    start = index + 1
                    currentGas = 0
                }
            }
            if (totalGas >= 0) {
                return start;
            } else {
                return -1;
            }
        };
        console.log(canCompleteCircuit([1,2,3,4,5],[3,4,5,1,2]))

29.最后一個(gè)單詞的長(zhǎng)度

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
            const arr = s.split(' ').filter(item => item != '')
            return arr[arr.length - 1].length
};

30.翻轉(zhuǎn)字符串中的單詞

        /**
         * @param {string} s
         * @return {string}
         */
        var reverseWords = function (s) {
            const arr = s.split(' ')
            const length = arr.length
            let result = ''
            for (let index = length; index >= 0; index--) {
                const item = arr[index];
                if (item) result += `${item} `
            }
            return result.substring(0, result.length - 1)
        };
        console.log(reverseWords("the sky is blue"))

/**
 * @param {string} s
 * @return {string}
 */
let reverseWords = function(s) {
   return  s.split(/[\s]+/).filter(e=>e!="").reverse().join(" ")
    
};

31.驗(yàn)證回文串

先統(tǒng)一去除非數(shù)字與字母的字符,轉(zhuǎn)小寫,再左右兩方對(duì)比

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {

            s = s.replace(/[\W_]/g, '').toLowerCase();
            let left = 0
            let right =  s.length - 1
            while (left < right) {
                if (s[left] != s[right]) return false
                left++
                right--
            }
            return true
};

32.判斷子序列

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
            let target = 0
            const length = t.length
            for (let index = 0; index < length; index++) {
                const element = t[index];
                if (s[target] === element) target++
            }
            return target === s.length
};

33.兩數(shù)之和 II - 輸入有序數(shù)組

        /**
         * @param {number[]} numbers
         * @param {number} target
         * @return {number[]}
         */
        var twoSum = function (numbers, target) {
            let left = 0,
                right = numbers.length - 1;
            while (left < right) {
                const total = numbers[left] + numbers[right]
                if (total === target) {
                    return [left + 1, right + 1]
                } else if (total > target) {
                    right--
                } else if(total < target) {
                    left++
                }
            }
        };
        console.log(twoSum( [5,25,75],  100))

34.長(zhǎng)度最小的子數(shù)組

我們使用兩個(gè)指針，一個(gè)左指針 left 和一個(gè)右指針 right 來(lái)定義一個(gè)滑動(dòng)窗口。

初始時(shí)，左指針和右指針都指向數(shù)組的第一個(gè)元素，窗口大小為1。

我們計(jì)算窗口內(nèi)所有元素的總和（從左指針到右指針），并將其與目標(biāo)值進(jìn)行比較。

如果窗口內(nèi)元素的總和小于目標(biāo)值，我們將右指針向右移動(dòng)，擴(kuò)大窗口，以便窗口內(nèi)的總和變大。

如果窗口內(nèi)元素的總和大于或等于目標(biāo)值，我們記錄當(dāng)前窗口的長(zhǎng)度（right - left + 1），然后將左指針向右移動(dòng)，縮小窗口，以尋找更小的長(zhǎng)度。

重復(fù)步驟4和步驟5，直到遍歷完整個(gè)數(shù)組。在此過(guò)程中，我們不斷調(diào)整窗口大小，以找到滿足條件的最小子數(shù)組。

最終，我們得到了滿足條件的最小子數(shù)組的長(zhǎng)度。

        /**
         * @param {number} target
         * @param {number[]} nums
         * @return {number}
         */
        var minSubArrayLen = function (target, nums) {
            let result = Infinity
            let left = 0
            let sum = 0
            const length = nums.length
            for (let index = 0; index < length; index++) {
                sum += nums[index];
                
                while (sum >= target) {
                    result = Math.min(result, index - left + 1)
                    sum -= nums[left];
                    left++
                }
            }
            return result === Infinity ? 0 : result
        };
        console.log(minSubArrayLen(7, [2,3,1,2,4,3]))

35.無(wú)重復(fù)字符的最長(zhǎng)子串

        /**
         * @param {string} s
         * @return {number}
         */
        var lengthOfLongestSubstring = function (s) {
            let newMap = new Map()
            const length = s.length
            let result = 0
            let start = 0
            for (let index = 0; index < length; index++) {
                const item = s[index];
                if (newMap.has(item)) {
                    start = Math.max(newMap.get(item) + 1, start)
                }
                newMap.set(item, index)
                result = Math.max(result, index - start + 1)
            }
            return result
        };
        console.log(lengthOfLongestSubstring("pwwkew"))

36.火柴拼正方形

/**
 * @param {number[]} matchsticks
 * @return {boolean}
 */
var makesquare = function(matchsticks) {
  if(matchsticks.length<4)return false

  let total = matchsticks.reduce((i,x)=>x+=i)

  if(total%4) return false

  matchsticks.sort((a,b)=>b-a)

  const SIDE = total/4

  if(matchsticks[0]>SIDE)return false
  
  let edges = [0,0,0,0]

  const dfs = (i) => {
    if(i === matchsticks.length)return true
    for(let k = 0;k<4;k++){
      if(edges[k] + matchsticks[i] > SIDE || (k&&edges[k]===edges[k-1]))continue
      edges[k] += matchsticks[i] 
      if(dfs(i+1))return true
      edges[k] -= matchsticks[i]
    }
    return false
  }
  return dfs(0);
};

37.單詞搜索

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-723329.html

        /**
         * @param {character[][]} board
         * @param {string} word
         * @return {boolean}
         */
        var exist = function (board = [
            ["C", "A", "A"],
            ["A", "A", "A"],
            ["B", "C", "D"]
        ], word = "AAB") {
            const rows = board.length;
            const cols = board[0].length;


            const dfs = (i, j, count) => {
                // 超出范圍與不符合字母的去除
                if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] !== word[count]) {
                    return false
                }
                // 符合所有條件直接返回true
                if (count === word.length - 1) return true
                // 臨時(shí)刪除已經(jīng)使用的字母
                const temp = board[i][j]
                board[i][j] = '/'

                // 往四面散開排查
                const found =
                    dfs(i - 1, j, count + 1) ||
                    dfs(i + 1, j, count + 1) ||
                    dfs(i, j - 1, count + 1) ||
                    dfs(i, j + 1, count + 1)
                // 回顯之前的字母到數(shù)組
                board[i][j] = temp
                return found
            }

            for (let i = 0; i < rows; i++) {
                for (let j = 0; j < cols; j++) {
                    if (dfs(i, j, 0)) {
                        return true;
                    }
                }
            }
            return false

        };

        console.log(exist())

到了這里，關(guān)于刷一下算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！