白褶的博客

外观

两数之和 ​

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length;i++ ){
        for(let j = i + 1;j < nums.length ;j++){
            if(target === nums[i] + nums[j]){
                return [i,j]
            }
        }
    }
}

map方法

var twoSum = function(nums, target) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    let dif = target-nums[i]
    if (map.has(dif)) {
      return [map.get(dif), i]
    }
    map.set(nums[i], i);
  }
};

罗马字符数字转整数 ​

/**
 * @param {string} s
 * @return {number}
 */
let Num = {
        I:1,
        V:5,
        X:10,
        L:50,
        C:100,
        D:500,
        M:1000,
        IV:4,
        IX:9,
        XL:40,
        XC:90,
        CD:400,
        CM:900
    }
var romanToInt = function(s) {
    let sum = 0
    for(let i = 0;i < s.length ;i++){
        if(i < s.length && Num[s[i] + s[i+1]]){
            sum += Num [s[i] + s[i+1]]
            i += 1
        }else{
            sum += Num[s[i]]
        }
    }
    return sum
};

反转字符串 ​

必须原地修改输入数组、使用 O(1) 的额外空间

/**
 Do not return anything, modify s in-place instead.
 */
function reverseString(s: string[]): void {
    s = s.reverse()
};

整数反转 ​

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let newX = x.toString()
    let sum
    if(newX[0]==='-'){
        sum = newX[1]*1
        for(let i = 2;i<newX.length;i++){
            sum += newX[i]*Math.pow(10,i-1)
        }
        sum*=-1
    }else{
        sum = newX[0]*1
        for(let i = 1; i<newX.length;i++){
            sum += newX[i]*Math.pow(10,i)
        }
    }
    if ( sum < - Math.pow(2, 31) || sum > Math.pow(2, 31) - 1){
        return 0
    }
    return sum
};

加一 ​

给定一个由 整数组成的非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。

function plusOne(digits: number[]): number[] {
    for(let i = digits.length -1;i>=0;i--){
        digits[i]+=1
        digits[i]%=10
        if(digits[i]!==0){
            return digits
        }
    }
    digits.unshift(1)
    return digits
};

旋转数组 ​

给你一个数组，将数组中的元素向右轮转 k个位置，其中 k是非负数。

/**
 Do not return anything, modify nums in-place instead. Way One
 */
function rotate(nums: number[], k: number): void {
    for(let i:number =0;i<k;i++){
        nums.unshift(nums.pop())
    }
};
/**
 Do not return anything, modify nums in-place instead. Way Two 使用临时数组
 */
function rotate(nums: number[], k: number): void {
    let newNums:number []=[]
    let length = nums.length
    for(let i = 0;i<length;i++){
        newNums[i] = nums[i]
    }
    for(let i = 0;i<length;i++){
        nums[(i+k)%length] = newNums[i]
    }
};

存在重复元素 ​

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

//方法一
function containsDuplicate(nums: number[]): boolean {
    let arr:number [] = [...new Set(nums)]
    return arr.length !== nums.length
};
//方法二
function containsDuplicate(nums: number[]): boolean {
    nums.sort((a,b)=>a-b)
    for(let i = 0;i<nums.length;i++){
        if(nums[i]===nums[i+1]) return true
    }
    return false
};

只出现一次的数字 ​

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

function singleNumber(nums: number[]): number {
    nums.sort((a,b)=>a-b)
    for(let i = 0;i<nums.length;i++){
        if(nums[i]===nums[i+1]){
            i++
        }else {
            return nums[i]
        }
    }
};

二分法查找 ​

function search(nums: number[], target: number): number {
    let numsLength = nums.length
    if(!numsLength) return -1
    if(numsLength === 1){
        return nums[0] === target ? 0:-1
    }
    let start=0,end=numsLength - 1
    while(start<=end){
        let mid = Math.floor((start+end)/2) //取中位数d
        if(nums[mid] === target){
            return mid
        }else if (target > nums[mid]){ //目标数比中位数大,移动初始值start边界
            start = mid + 1
        }else {
            end = mid - 1 //目标数比中位数小,移动初始值end边界
        }
    }
    return -1
};

寻找数组的中心索引 ​

/**
 * @param {number[]} nums
 * @return {number}
 */
var pivotIndex = function(nums) {
    const total = nums.reduce((pre,cur)=>pre+=cur,0)
    let number = -1
    let left = 0
    for(let i=0;i<nums.length;i++){
        left += nums[i]
        console.log(left,'left',total-nums[i]-left)
        if(left === total + nums[i] - left){
            number = i
            break;
        }
    }
    return number
};
function pivotIndex(nums: number[]): number {
  let number = -1,sum=0
  const total = nums.reduce((pre,cur)=>pre+=cur,0)
  nums.some((cur,index)=>{
    sum+=cur
    if(sum === total + cur - sum){
      number = index
      return true
    }
  })
  return number
};

搜索插入位置 ​

function searchInsert(nums: number[], target: number): number {
 let result:number
    nums.some((cur,index)=>{
        if(cur >=  target) {
            result = index
            return true
        }
    })
    return result ?? nums.length
};
function searchInsert(nums: number[], target: number): number {
    let result:number
    if(nums[nums.length-1] < target) {
        return nums.length
    }else {
        for(let i=0;i<nums.length;i++){
            if(nums[i] >= target){
                result = i
                break
            }
        }
    }
    return result
};

合并区间 ​

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  const sortNums = intervals.sort((a, b) => a[0] - b[0])
  return sortNums.reduce((pre, cur) => {
      const arr = pre[pre.length - 1]
      if (arr && arr[1] >= cur[0]) {
        let left = arr[0]
        let right = arr[1] <= cur[1] ? cur[1] : arr[1]
        pre[pre.length - 1] = [left,right]
      } else {
          pre.push(cur)
      }
    return pre
  }, [])
};

删列造序 ​

/**
 * @param {string[]} strs
 * @return {number}
 */
var minDeletionSize = function(strs) {
    let number = 0
    const arr = strs[0].split('').map((item,index)=> strs.map(_item=> _item[index]))
    for(let item of arr) {
        for(let i=0;i<item.length-1;i++){
            if(item[i] > item[i+1]){
                number ++
                break;
            }
        }
    }
    return number
};

旋转矩阵 ​

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const arr = matrix.reverse()
    for(let i = 0;i<arr.length ;i++){
        for(let j = i;j<arr[i].length;j++){
            let temp = arr[i][j]
            arr[i][j] = arr[j][i]
            arr[j][i] = temp
        }
    }
    return arr
};

零矩阵 ​

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    let rowArr = [],columnArr = []
   matrix.forEach((item,index)=>{
       item.forEach((_item,_index)=>{
           if(_item ===0) {
               if(rowArr.indexOf(index) === -1) rowArr.push(index)
               if(columnArr.indexOf(_index) === -1) columnArr.push(_index)
           }
       })
   })
   rowArr.forEach(item=>{
       matrix[item] = matrix[item].map(item=>item = 0)
   })
   columnArr.forEach(item=>{
       for(let i =0;i<matrix.length;i++){
           matrix[i][item] = 0
       }
   })
    return matrix
};

最大三角形面积 ​

/**
 * @param {number[][]} points
 * @return {number}
 */
var largestTriangleArea = function(points) {
    let maxArea = 0

    const getArea = ([x1,y1],[x2,y2],[x3,y3]) => {
        const area =  (x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2
        return area > 0 ? area : -1 * area
    }
    for(let i=0;i < points.length;i++){
        for(let j= i + 1;j < points.length;j++){
            for(let k = j + 1;k < points.length;k++){
                const areaInfo = getArea(points[i],points[j],points[k]);
                if(areaInfo >= maxArea) maxArea = areaInfo
            }
        }
    }
    return maxArea
};

最长公共前缀 ​

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    for(let i=0;i<strs[0].length;i++){
        let s = strs[0][i]
        for(let j=1;j<strs.length;j++){
            if(strs[j][i] !== s) {
                return strs[0].slice(0,i)
            }
        }
    }
    return strs[0]
};

翻转字符串中的单词 ​

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.split(' ').filter(item=>item!=='').reverse().join(' ')
};

数组拆分 I ​

/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayPairSum = function(nums) {
    const arr = nums.sort((a,b)=>a-b)
    let total = 0
    for(let i=0;i<arr.length;){
        total += arr[i]
        i+=2
    }
    return total
};

最长回文子串 ​

通过遍历查找每个字符的左右边界且相等的情况下，返回边界值，如果边界的长度大于原先的边界则覆盖。但考虑到字符串的长度可能是奇数或者偶数，考虑中心点可能是1个或者2个。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    const expandeAroundCenter = (s,left,right)=>{
        while(left >= 0 && right < s.length && s[left]===s[right]){
            left--
            right++
        }
        return [left+1,right-1]
    }
    let start=0,end=0
    for(let i=0;i<s.length;i++){
        const [left1,right1] = expandeAroundCenter(s,i,i)
        const [left2,right2] = expandeAroundCenter(s,i,i+1)
        if(right1-left1>end-start){
            end = right1
            start = left1
        }
        if(right2-left2>end-start){
            end = right2
            start = left2
        }
    }
    return s.slice(start,end+1)
}

杨辉三角 I ​

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
 let arr = [[1]]
    if(numRows===1){
        return arr
    } else if(numRows===2){
        arr.push([1,1])
        return arr
    } else {
        arr.push([1,1])
        for(let i=2;i<numRows;i++) {
            let x = [1]
            for(let j=0;j < arr[i-1].length - 1;j++){
                x.push(arr[i-1][j] + arr[i-1][j+1])
            }
            x.push(1)
            arr.push(x)
        }
        return arr
    }
}
/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    let total = []
    for(let i = 0;i < numRows;i++){
        let arr = new Array(i+1).fill(1)
        for(let j = 1;j < arr.length - 1;j++){
            arr[j] = total[i-1][j-1] + total[i-1][j]
        }
        total.push(arr)
    }
    return total
};
/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    let total = []
    const getRow = (index) =>{
        let row = new Array(index).fill(0)
        row[0] = 1
        for(let i=1;i<=index;i++){
            row[i] = row[i-1] * (index - i + 1) / i
        }
        return row
    }
    for(let i = 0;i < numRows;i++){
        const row = getRow(i)
        total.push(row)
    }
    return total
};

杨辉三角 II ​

返回第n行的数组

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    let total = []
    for(let i=0;i<rowIndex+1;i++){
        let arr = new Array(i+1).fill(1)
        for(let j = 1;j < arr.length - 1;j++){
            arr[j] = total[i-1][j-1] + total[i-1][j]
        }
        total.push(arr)
    }
    return total[rowIndex]
};
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    let rowArr = new Array(rowIndex + 1).fill(0)
    rowArr[0] = 1
    for(let i=1;i <= rowIndex; i++){
        rowArr[i] = rowArr[i - 1] * (rowIndex - i + 1) / i
    }
    return rowArr
};

反转字符串中的单词 III ​

  • **输入：**s = "Let's take LeetCode contest"
  • 输出："s'teL ekat edoCteeL tsetnoc"
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    const arr = s.split(' ')
    for(let i=0;i<arr.length;i++){
        arr[i] = arr[i].split('').reverse().join('')
    }
    return arr.join(' ')
};

最大连续1的个数 ​

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function(nums) {
    const arr = nums.join('').split(0)
    let max = 0
    for(let i=0;i<arr.length;i++){
        const length = arr[i].length
        max = length > max ? length : max
    }
    return max
};
const findMaxConsecutiveOnes = (nums) => {
  let maxCount=0,count=0
  for(let i = 0;i < nums.length;i++){
    if(nums[i] === 1){
       count++
    } else {
      maxCount = Math.max(maxCount,count)
      count = 0
    }
  }
  return Math.max(maxCount,count)
}

移除元素 ​

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

const removeElement = (nums,val) => {
  let i = 0
  nums.forEach((item,index)=>{if(item !==val) nums[i++] = nums[index]})
  return i
}
const removeElement = (nums,val) => {
    let left=0,right= nums.length
    while(left < right){
      if(nums[left] === val){
        nums[left] = nums[right-1]
        right--
      } else {
        left++
      }
    }
   return left
}

移动零 ​

快指针遇到非零数，则和慢指针指向的零交换位置。

const moveZeros = (nums) =>{
  let slow = 0
  for(let fast = 0;fast < nums.length;fast++){
    if(nums[fast]){
      let temp = nums[slow]
      nums[slow] = nums[fast]
      nums[fast] = temp
      slow++
    }
  }
  return nums
}

实现strStr() ​

给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回  -1 。

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    for (let i=0;i<haystack.length;i++) {
        const needleLength = needle.length
        const haystackLength = haystack.length
        if (haystackLength >= needleLength + i) {
            const copy = haystack.slice(i,needleLength + i)
            if(copy === needle) {
                return i
            }
        }
    }
    return -1
};

寻找旋转排序数组中的最小值 ​

必须使用O(log n)的时间复杂度

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    if(nums.length === 1) return nums[0]
    let l=0,r = nums.length - 1
    while(l<r) {
        let mid = Math.floor((l+r)/2)
        if(nums[mid]>nums[r]) {
            l = mid + 1;
        } else {
         r = mid
        }
    }
    return nums[l]
};

树结构树节点查找本层深度 ​

/**
 * 查看树中Object的嵌套深度
 * @param {number} id
 * @return {number}
 */
function  getTreeMaxFloor(findId) {
  let toggle = false
  let max = 1
  let result = 1
  const callBack = (findId, data) => {
    for (let i = 0; i < data.length; i++) {
      const { id, type, children } = data[i]
      if (type === 'Object') {
        if (findId !== id && children.length > 0) {
          max += 1
          callBack(findId, children)
        } else if (findId === id) {
          toggle = true
          result = max
        }
      }
    }
    max = toggle ? result : 1
  }
  callBack(findId, this.treeData)
  return result
}

K 件物品的最大和 ​

/**
 * @param {number} numOnes
 * @param {number} numZeros
 * @param {number} numNegOnes
 * @param {number} k
 * @return {number}
 */
var kItemsWithMaximumSum = function(numOnes, numZeros, numNegOnes, k) {
    return numOnes > k
    ? k
    : numOnes + numZeros < k ? 2 * numOnes + numZeros - k : numOnes
};

矩阵中的和 ​

/**
 * @param {number[][]} nums
 * @return {number}
 */
var matrixSum = function(nums, x = 0) {
    let total = x
    let curMax = 0
    for (let i = 0; i < nums.length; i++){
        const numsList = nums[i]
        const { max, maxIndex } = getMaxNumber(numsList)
        numsList.splice(maxIndex, 1)
        if (max > curMax) curMax = max
    }
    total += curMax
    return nums[0].length === 0 ? total : matrixSum(nums, total)
};

var getMaxNumber = (arr) => {
    let max = 0
    let maxIndex = -1
    for (let i = 0; i < arr.length; i++) {
        const cur = arr[i]
        if (max < cur) {
            max = cur
            maxIndex = i
        }
    }
    return { max, maxIndex }
}

拆分成最多数目的正偶数之和 ​

function maximumEvenSplit(finalSum: number): number[] {
  if (finalSum % 2 !== 0) return []
  let arr: number[] = []
  for (let i = 2; i <= finalSum; i+=2) {
    arr.push(i)
    finalSum -= i
  }
  arr[arr.length - 1] += finalSum
  return arr
}

两数之和 II - 输入有序数组 ​

原理：通过双向双指针，因为原数组是经过排序的，时间复杂度O(n)

function twoSum(numbers: number[], target: number): number[] {
    let l = 0, r = numbers.length - 1
    while (numbers[l] + numbers[r] !== target) {
        numbers[l] + numbers[r] < target ? l++ : r--
    }
    return [l+1, r+1]
};

​