Aiden's blog
wushengxin
2021-09-30
目录

LeetCode算法

# 基本概念

# 时间复杂度

  • O(1)：定义变量，set，map

  • O(n)：一个循环(for、while)

  • O(logn)：二分搜索（设置一个mid，通过判断该数与target的值，小于则left=mid+1，否则right=mid-1）

  • O(nlogn)：sort排序

  • O(n^2)：嵌套循环(for、while）

# 空间复杂度

  • O(1)：定义变量

  • O(n)：定义一个长为n的数组、定义一个长度为n的set/map、for循环生成长度为n的链表

  • O(n^2)：二维数组、一维数组每个元素存放一个长度为n的set/map/链表

# 二叉树（Binary Tree）

二叉树：先序遍历、中序遍历、后序遍历（分别指的是根的位置在前中后）

  • root根节点
  • root.left左节点
  • root.right右节点
  • val，如root.val即可获取当前节点的值

# BST（Binary Search Tree）

也就是中序遍历，不管哪个位置(根节点与叶子节点也一样)，从大到小都是左中右

# 完全二叉树

height-1必须填满，height高度左边的节点必须排满

# 满二叉树

所有节点都必须排满，是完全二叉树的一种特例

# 链表(linked list)

  • head整个链表，相当于是一个值
  • head.next指向链表的下一个数，当不存在这个数则返回null，相当于是一个箭头
  • 一般遍历，判断curr!==null&&curr.next!==null
  • 逻辑写完，最后返回head即可

问题：链表和数组的区别

  • 链表删除和增加一个数所花费的时间短，只要改变指针的指向就好了，数组就要重新遍历一次
  • 数组获取元素比链表快，链表获取某个值需要一个一个遍历拿到即**.next**

# BFS（广度优先）

一个数一个数处理，从该数上下左右开始遍历，一圈一圈遍历

# DFS（深度优先）

一条路一条路的遍历，先处理一条路在回来处理另一条路，如岛屿问题

时间复杂度为nlogn

  • 定义变量left指向起始索引，right指向末尾索引
  • 循环left<=right
  • 设置mid = Math.floor(left + (right-left)/2) // 防止超过最大安全数
  • 通过判断nums[mid]与target值
    • 小于则砍半，将left设置为mid+1
    • 大于则砍半，将right设置为mid-1

# 动态规划

递归 + 记忆缓存memoize（斐波那契数列、不同路径、最长公共子序、最大正方形）

  • 创建memoize辅助函数，创建一个数组用于存储已经遍历过的数字
  • 创建dp数组（dummy）

# Palindrome（回文）

  • 创建一个isPalindrome辅助函数
  • 创建left和right，循环left<right，判断当前的s[left]和s[right]是否相等

# Anagram（字母异位词）

判断两个字符串出现的字符是否数量是一样的，通过map存储

  • A字符串字符存进去设置为+1
  • B字符串字符存进去设置为-1
  • 最后for of遍历map，判断每个map的值，letter[1] !== 0返回false，否则返回true

# 快速排序

var quickSort = function(arr){
	if(arr.length<=1) return arr
	const left = [],right = []
	let current = arr.splice(0,1)
	for(let i=0;i<arr.length;i++){
	  if(arr[i]<current){
	    left.push(arr[i])
	  }else{
	    right.push(arr[i])
	  }
	}
	return quickSort(left).concat(current,quickSort(right))
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 704、二分查找

又称二分搜索：通过取中间的数去比较left和right的值，砍半，时间复杂度为log(n)

var search = function(nums, target) {
    let left = 0,right = nums.length-1

    while(left<=right){
        let mid = Math.floor(left + (right-left)/2) // 防止超过最大安全数
        if(nums[mid] === target){
            return mid
        }else if(nums[mid] < target){
            left = mid+1
        }else{
            right = mid-1
        }
    }

    return -1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 70、爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

思路：dp[10] 是不是就是你爬到8阶，然后再走2步就到了，还有你走到9阶，再走1步就到了，

所以 dp[10] 是不是等于 dp[9]+dp[8]

延伸一下 dp[n] 是不是等于 dp[n - 1] + dp[n - 2]

var climbStairs = function(n) {
  const dp = [];
  dp[1] = 1;
  dp[2] = 2;
  for(let i=3;i<=n;i++){
  	dp[i] = dp[i-1]+dp[i-2];
  }
  return dp[n]
}
1
2
3
4
5
6
7
8
9

# 128、最长连续序列

var longestConsecutive = function(nums) {
	let current = 1;
	let maxlength = 0;
	if(nums.length===0){
	  return 0;
	}
	if(nums.length===1){
	  return 1;
	}
	nums = nums.sort((a,b)=> a-b);
	for(let i=1;i<nums.length;i++){
	  if(nums[i]-1 > nums[i-1]){
	    current = 1
	  }else if(nums[i]-1 == nums[i-1]){
	    current++
	  }
	  if(current>maxlength){
	    maxlength = current
	  }
	}
	return maxlength
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 53、最大子序和

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
1
2
3
var maxSubArray = function(nums) {
	let maxSum = nums[0]
    let dp = []
    dp[0] = nums[0]
    for(let i=1;i<nums.length;i++){
        dp[i] = Math.max(dp[i-1],0) + nums[i]
        maxSum = Math.max(dp[i],maxSum)
    }
    return maxSum
};
1
2
3
4
5
6
7
8
9
10

# 152、乘积最大连续序列

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
1
2
3
var maxProduct = function(nums) {
    const maxProduct = []
    const minProduct = []
    maxProduct[0] = nums[0]
    minProduct[0] = nums[0]
    let max = nums[0]
    for(let i=1;i<nums.length;i++){
        maxProduct[i] = Math.max(nums[i],maxProduct[i-1]*nums[i],minProduct[i-1]*nums[i])
        minProduct[i] = Math.min(nums[i],maxProduct[i-1]*nums[i],minProduct[i-1]*nums[i])
        max = Math.max(max,maxProduct[i])
    }
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# 326、3的幂

var isPowerOfThree = function(n) {
  while(n>=3){
    n /= 3	
  }
  return n===1
}
1
2
3
4
5
6

# 412、Fizz Buzz

  1. 如果 n 是3的倍数，输出“Fizz”；
  2. 如果 n 是5的倍数，输出“Buzz”；
  3. 如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
var fizzBuzz = function (n) { 
  const list = []
  for(let i=1;i<=n;i++){
    if(i%3==0 && i%5==0){
      list.push('FizzBuzz')
      continue
    }else if(i%3==0){
      list.push('Fizz')
      continue
    }else if(i%5==0){
      list.push('Buzz')
      continue
    }else{
      list.push(i+'')
    }
  }
  return list
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 7、整数反转

var reverse = function(x) {
    let ret = 0;
    while(x){
      ret = ret * 10 + x % 10;
      if(ret > Math.pow(2, 31) - 1 || ret < Math.pow(-2, 31)) return 0;
      x = parseInt(x / 10) 
    }
    return ret
}
1
2
3
4
5
6
7
8
9

# 172、阶乘中的零

给定一个整数 n，返回 n! 结果尾数中零的数量。

思路：有几个5就有几个0

var trailingZeroes = function(n){
	let sum = 0
	whilte(n>1){
	  n = Math.floor(n/5)
	  sum += n
	}
	return sum
}
1
2
3
4
5
6
7
8

# 343、整数拆分

# 题目描述

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

# 题目分析

题目中“n 至少可以拆分为两个正整数的和”，这个条件说明了 n 是大于 1 的整数。

对 7 来说，可以拆成 3+4，最大乘积是 12。

对 8 来说，可以拆成 3+3+2，最大乘积是 18。

# 贪心法

综上所述，算法的整体思路是：

  • n 除 3 的结果为 a，余数是 b
  • 当 b 为 0，直接将 a 个 3 相乘
  • 当 b 为 1，将（a-1）个 3 相乘，再乘以 4
  • 当 b 为 2，将 a 个 3 相乘，再乘以 2
var integerBreak = function(n) {
  if(n===2) return 1;
  if(n===3) return 2;
  const a = Math.floor(n/3);
  const b = n%3;
  if(b===0) return 3**a;
  if(b===1) return 3**(a-1)*4;
  return 3**a*2
}
1
2
3
4
5
6
7
8
9

# 674、最长连续递增序列

输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

var findLengthOfLCIS = function(nums) {
    if(nums.length === 0) return 0;
    if(nums.length===1) return  1;
    let nowLen = 1;
    let maxLen = 0;
    for(let i=1;i<nums.length;i++){
        if(nums[i]>nums[i-1]){
            nowLen++
        }else{
            if(maxLen<nowLen){
                maxLen = nowLen
            }
            nowLen = 1
        }
    }
    if(maxLen<nowLen){
        maxLen = nowLen
    }
    return maxLen
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 11、和为k的子数组

var subarraySum = function(nums, k) {
    let cnt = 0
    let sum_i = 0,sum_j = 0

    const map = new Map()
    map.set(0,1)
    for(let i=0;i<nums.length;i++){
        sum_i += nums[i]
        sum_j = sum_i - k
        if(map.has(sum_j)){
            cnt += map.get(sum_j)
        }
        let sum_cnt = map.get(sum_i) || 0
        map.set(sum_i,sum_cnt+1)
    }

    return cnt
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 11、盛最多水的容器

img

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
1
2
3

# 思路

我们现在有两个指针，分别指向第一根和最后一根。

假设 第一根高度是 H1，最后一根高度是Hn，H1大于Hn，所以他们围出来的面积是多少呢？

Hn*（n-1）。

现在我们要让其中一根指针向里移动，还要面积有可能上升。我们思考，面积取决于两根柱子的距离和两根柱子中最短的一根。现在，我们向里移动，两个指针指向的柱子的相对距离变短了，我们为了面积上升，只能选择让 两根柱子中较短的那一根长度较长，于是，我们要移动指向较短的柱子的那一个指针

var maxArea = function(height) {
    let frontPoint = 0;
    let endPoint = height.length - 1;
    let max = 0;
    while (frontPoint < endPoint) {
        max = Math.max(max, (endPoint - frontPoint) * (height[frontPoint] > height[endPoint] ? height[endPoint--]: height[frontPoint++]))
    }
    return max;
};
1
2
3
4
5
6
7
8
9

# 42、接雨水

var trap = function(height) {
    if(height.length===0){
        return 0
    }
    let left = 1
    let right = height.length-2
    let l_max = height[0]
    let r_max = height[height.length-1]
    let sum = 0
    while(left<=right){
        l_max = Math.max(l_max,height[left])
        r_max = Math.max(r_max,height[right])

        if(l_max<r_max){
            sum += l_max - height[left]
            left++
        }else{
            sum += r_max - height[right]
            right--
        }
    }
    return sum
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 4、寻找两个正序数组的中位数

var findMedianSortedArrays = function(nums1, nums2) {
  let nums3 = [...nums1,...nums2]
  nums3 = nums3.sort((a,b) => a-b)
  let center
  let nums3Len = Math.floor(nums3.length/2)
  if(nums3.length % 2 == 1){
      center = nums3[nums3Len]
  }else{
      center = parseFloat((nums3[nums3Len] + nums3[nums3Len-1]) / 2)
  }
  return center
};
1
2
3
4
5
6
7
8
9
10
11
12

# 26、删除有序数组中的重复项

# 覆盖法

var removeDuplicates = function(nums) {
  if(nums.length<2) return nums.length
   let i = 0
   for(let j = 1;j < nums.length;j++){
       if(nums[i] !== nums[j]){
           nums[++i] = nums[j]
       }
   }
    return ++i
};
1
2
3
4
5
6
7
8
9
10

# 1、两数之和

var twoSum = function(nums, target) {
    const map = new Map()
    for(let i=0.;i<nums.length;i++){
        const complete = target - nums[i]
        if(map.has(complete)){
            return [map.get(complete),i]
        }else{
            map.set(nums[i],i)
        }
    }
    return []
}
1
2
3
4
5
6
7
8
9
10
11
12

# 3、无重复字符的最长子串

var lengthOfLongestSubstring = function(s) {
    const set = new Set()
    let maxLenth = 0,i = 0,j = 0
    if(s.length===0) return 0
    for(i;i<s.length;i++){
        if(!set.has(s[i])){
            set.add(s[i])
            maxLenth = Math.max(maxLenth,set.size)
        }else{
            while(set.has(s[i])){
                set.delete(s[j])
                j++
            }
            set.add(s[i])
        }
    }
    return maxLenth
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 5、最长回文子串

var longestPalindrome = function(s) {
    if(s.length<2) return s
	let start = 0
    let maxLength = 1
    function expandAroundCenter(left,right){
        while(left>=0&&right<s.length&&s[left]===s[right]){
            if(right-left+1>maxLength){
                maxLength = right-left+1
                start = left
            }
            left--
            right++
        }
    }
    for(let i=0;i<s.length;i++){
        expandAroundCenter(i-1,i+1)
        expandAroundCenter(i,i+1)
    }
    return s.substring(start,start+maxLength)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 14、最长公共前缀

var longestCommonPrefix = function(strs) {
    if(strs.length===0) return ""
    let first = strs[0]
    if(first === '') return ""

    let minLen = Number.MAX_SAFE_INTEGER
    for(let i=1;i<strs.length;i++){
        const len = towStrCompare(first,strs[i])
        minLen = Math.min(len,minLen)
    }

    function towStrCompare(s,t){
        let i = 0,j = 0
        let cnt = 0
        while(i<s.length&&j<t.length){
            if(s[i]===t[j]){
                cnt++
            }else{
                return cnt
            }
            i++
            j++
        }
        return cnt
    }
    
    return first.slice(0,minLen)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 15、三数之和

var threeSum = function(nums) {
    let result = []
    nums = nums.sort((a,b)=>a-b)
    for(let i=0;i<nums.length-2;i++){
        if(i==0||nums[i]!==nums[i-1]){
            let start = i+1
            let end = nums.length-1
            while(start<end){
                if(nums[i]+nums[start]+nums[end]===0){
                    result.push([nums[i],nums[start],nums[end]])
                    start++
                    end--
                    while(start<end&&nums[start]===nums[start-1]){
                        start++
                    }
                    while(start<end&&nums[end]===nums[end+1]){
                        end--
                    }
                }else if(nums[i]+nums[start]+nums[end]<0){
                    start++
                }else{
                    end--
                }
            }
        } 
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 20、有效括号

var isValid = function(s) {
    const stack = []
	const map = new Map()
    map.set("(",")")
    map.set("{","}")
    map.set("[","]")
    for(let i=0;i<s.length;i++){
        if(map.has(s[i])){
            stack.push(map.get(s[i]))
        }else{
            if(stack.pop() !== s[i]) return false
        }
    }
    if(stack.length!==0) return false
    return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 54、螺旋矩阵

var spiralOrder = function(matrix){
    if(matrix.length === 0) return []
    let top = 0
    let bottom = matrix.length-1
    let left = 0
    let right = matrix[0].length-1
    
    let direction = "right"
    let result = []
    while(left<=right&&top<=bottom){
        if(direction === "right"){
            for(let i=left;i<=right;i++){
                result.push(matrix[top][i])
            }
            top++
            direction = "down"
        }else if(direction === "down"){
            for(let i=top;i<=bottom;i++){
                result.push(matrix[i][right])
            }
            right--
            direction = "left"
        }else if(direction === "left"){
            for(let i=right;i>=left;i--){
                result.push(matrix[bottom][i])
            }
            bottom--
            direction = "top"
        }else if(direction === "top"){
            for(let i=bottom;i>=top;i--){
                result.push(matir[i][left])
            }
            left++
            direction = "right
        }
    }
    return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 55、跳跃游戏

# 贪心算法

思路：索引加值是否大于等于maxJump，大于则成功，最后查看maxJump是否为索引0，从后往前遍历

var canJump = function(nums){
  let maxJump = nums.length-1
  for(let i=nums.length-2;i>=0;i--){
      if(i+num[i]>=maxJump){
          maxJump = i
      }
  }
    return maxJump === 0
}
1
2
3
4
5
6
7
8
9

# 56、合并区间

var merge = function(intervals){
    if(intervals.length<2){
        return intervals
    }
    intervals.sort((a,b)=> a[0]-b[0])
    let curr = intervals[0]
    let result = []
    for(let interval of intervals){
        if(curr[1]>=interval[0]){
            curr[1] = Math.max(curr[1],interval[1])
        }else{
            result.push(curr)
            curr = interval
        }
    }
    if(curr.length!==0){
        result.push(curr)
    }
    return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 62、不同路径

# 动态规划

思路：类似与扫雷

var uniquePaths = function(m, n) { //n为行，m为列
    let dp = []
    for(let i=0;i<n;i++){
        dp.push([])
    }
    for(let row=0;row<n;row++){
        dp[row][0] = 1
    }
    for(let col=0;col<m;col++){
        dp[0][col] = 1
    }
    for(let row=1;row<n;row++){
        for(let col=1;col<m;col++){
            dp[row][col] = dp[row-1][col] + dp[row][col-1]
        }
    }
    return dp[n-1][m-1] 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 66、加一

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
1
2
3
var plusOne = function(digits) {
    for(let i=digits.length-1;i>=0;i--){
        if(digits[i]!==9){
            digits[i]++
            return digits
        }else{
            digits[i] = 0
        }
    }
    const result = [1,...digits]
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12

# 26、验证回文

判断一个字符串是否有回文

var isPalindrome = function(s) {
    s = s.toLowerCase().replace(/[\W_]/g,"")
    if(s.length<2) return true
    let left = 0
    let right = s.length-1
    while(left<right){
        if(s[left]!==s[right]){
            return false
        }
        left++
        right--
    }
    return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 680、验证回文字符串II

删除一个字符后还是回文字符串

思路：设置一个help函数，当往中间字符不同时则分两种情况比较

  • left+1, right
  • left,right-1
var validPalindrome = function(s) {
    function isPalindrome(left,right){
        while(left<right){
            if(s[left] !== s[right]){
                return false
            }
            left++
            right--
        }
        return true
    }

    let left = 0,right = s.length-1
    while(left<right){
        if(s[left] !== s[right]){
            return isPalindrome(left+1,right) || isPalindrome(left,right-1)
        }
        left++
        right--
    }
    
    return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 200、岛屿数量

沉没法：当遇到1的岛屿把他变成0并向四周扩散（深度优先）

var numIslands = function(grid) {
    let count = 0
    function dfs(row,col){
        if(row<0||row>=grid.length||col<0||col>=grid[0].length||grid[row][col]==="0"){
            return
        }
        grid[row][col] = "0"
        dfs(row,col+1)
        dfs(row,col-1)
        dfs(row+1,col)
        dfs(row-1,col)
    }
    for(let row=0;row<grid.length;row++){
        for(let col=0;col<grid[0].length;col++){
            if(grid[row][col] === "1"){
                count++
            	dfs(row,col)
            }
        }
    }
    return count
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 695、岛屿面积

递归：往该点上下左右遍历，处理好边界问题

var maxAreaOfIsland = function(grid) {
    let result = 0
    for(let row=0;row<grid.length;row++){
        for(let col=0;col<grid[0].length;col++){
            if(grid[row][col] === 1){
                const count = dfs(row,col)
                result = Math.max(result,count)
            }
        }
    }
    function dfs(row,col){
        if(row<0||row>=grid.length||col<0||col>=grid[0].length||grid[row][col] === 0){
            return 0
        }
        
        grid[row][col] = 0
        let count = 1
        count += dfs(row,col-1)
        count += dfs(row,col+1)
        count += dfs(row-1,col)
        count += dfs(row+1,col)
        return count
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 83、删除排序链表中的重复元素

var deleteDuplicates = function(head) {
  let current = head
  while(current!==null&&current.next!==null){
      if(current.val === current.next.val){
          current.next = current.next.next
      }else{
          current = current.next
      }
  }
    return head
}
1
2
3
4
5
6
7
8
9
10
11

# 19、删除链表的倒数第N个结点

思路：n2为链表加n个节点的位置，通过判断是否指向最后一个结点来设置n1的结点，最后返回链表的头部

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode()
    dummy.next = head
    let n1 = dummy
    let n2 = dummy
    for(let i=0;i<=n;i++){
        n2 = n2.next
    }
    while(n2!==null){
        n1 = n1.next
        n2 = n2.next
    }
    n1.next = n1.next.next
    return dummy.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 21、合并两个有序链表

思路：一开始dummy指向空节点，所以要返回.next个节点值

var mergeTwoLists = function(l1, l2) {
	let curr = new ListNode()
    let dummy = curr
    while(l1!==null&&l2!==null){
        if(l1.val<l2.val){
            curr.next = l1
            l1 = l1.next
        }else{
            curr.next = l2
            l2 = l2.next
        }
        curr = curr.next
    }
    if(l1!==null){
        curr.next = l1
    }
    if(l2!==null){
        curr.next = l2
    }
    return dummy.next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 24、两两交换链表中的节点

思路:设置一个dummy节点指向链表前面，为了最后返回dummy.next节点

  • n1=current.next
  • n2=current.next.next
  • current.next = n2
  • n1.next = n2.next
  • n2.next = n1
  • current = n1
var swapPairs = function(head) {
    let dummy = new ListNode()
    dummy.next = head
    let curr = dummy

    while(curr.next!==null&&curr.next.next!==null){
        let n1 = curr.next
        let n2 = curr.next.next
        curr.next = n2
        n1.next = n2.next
        n2.next = n1
        curr = n1
    }
    return dummy.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 134、加油站

思路：检查当前油量是否大于等于0，如果小于0则直接从i+1处开始遍历

var canCompleteCircuit = function(gas, cost) {
    let totalGas = 0
    let totalCost = 0
    for(let i=0;i<gas.length;i++){
        totalGas += gas[i]
        totalCost += cost[i]
    }

    if(totalGas<totalCost){
        return -1
    }

    let currentGas = 0
    let start = 0
    for(let i=0;i<gas.length;i++){
        currentGas = currentGas - cost[i] + gas[i]
        if(currentGas<0){
            currentGas = 0
            start = i+1
        }
    }
    return start
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 153、寻找旋转排序数组中的最小值

思路：寻找旋转前的起始数组的最后一向是否大于旋转后数组的第一向，二分查找，找不到则切分，时间复杂度log(n)

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
1
2
3
var findMin = function(nums) {
    let left = 0,right = nums.length-1
    if(nums.length===1 || nums[right]>nums[0]) return nums[0]

    while(left<right){
        let mid = Math.floor(left+(right-left)/2)

        if(nums[mid]>nums[mid+1]){
            return nums[mid+1]
        }

        if(nums[mid-1]>nums[mid]){
            return nums[mid]
        }

        if(nums[left]<nums[mid]){
            left = mid+1
        }else{
            right = mid-1
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 160、相交链表

var getIntersectionNode = function(headA, headB) {
    let n1 = headA
    let n2 = headB
    while(n1!==n2){
        if(n1===null){
            n1 = headB
        }else{
            n1 = n1.next
        }
        if(n2===null){
            n2 = headA
        }else{
            n2 = n2.next
        }
    }
    return n1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 187、重复的DNA序列

思路：题目要求目标指定的10个字符串，通过slice遍历字符串，判断每个字符串出现的次数大于2就成立

var findRepeatedDnaSequences = function(s) {
    let result = []
    const map = new Map()
    for(let i=0;i+10<=s.length;i++){
        let dna = s.substring(i,i+10)
        if(!map.has(dna)){
            map.set(dna,1)
        }else if(map.get(dna)===1){
            result.push(dna)
            map.set(dna,2)
        }else{
            map.set(dna,map.get(dna)+1)
        }
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 198、打家劫舍

# 动态规划

思路：判断当前数加上i-2与i-1哪个大即可

var rob = function(nums) {
    if(nums.length === 0) return 0
    if(nums.length === 1) return nums[0]
    const dp = []
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0],nums[1])

    for(let i=2;i<nums.length;i++){
        dp[i] = Math.max(nums[i] + dp[i-2],dp[i-1])
    }
    return dp[nums.length-1]
};
1
2
3
4
5
6
7
8
9
10
11
12

# 206、反转链表

思路：定义三个指针，一个指向头结点的前面，通过来回赋值可得出pre是反向的链表

var reverseList = function(head) {
    let pre = null
    let curr = head
    let next = head
    while(curr!==null){
        next = curr.next
        curr.next = pre
        pre = curr
        curr = next
    }
    return pre
};
1
2
3
4
5
6
7
8
9
10
11
12

# 217、存在重复元素

var containsDuplicate = function(nums) {
    const set = new Set()
    for(let i=0;i<nums.length;i++){
        if(set.has(nums[i])){
            return true
        }else{
            set.add(nums[i])
        }
    }
    return false
};
1
2
3
4
5
6
7
8
9
10
11

# 219、存在重复元素II

思路：看map中是否有该数并且要在指定的k范围内查找

var containsNearbyDuplicate = function(nums, k) {
    const map = new Map()
    for(let i=0;i<nums.length;i++){
        if(map.has(nums[i]) && (i-map.get(nums[i]))<=k){
            return true
        }else{
            map.set(nums[i],i)
        }
    }
    return false
};
1
2
3
4
5
6
7
8
9
10
11

# 238、除自身以外数组的乘积

思路：通过一个变量product去更新每次的值，通过遍历前后循环即可

var productExceptSelf = function(nums) {
    const result = Array(nums.length).fill(1)

    let product = 1
    for(let i=0;i<nums.length;i++){
        result[i] = result[i] * product
        product = product * nums[i]
    }

    product = 1
    for(let i=nums.length-1;i>=0;i--){
        result[i] = result[i] * product
        product = product * nums[i]
    }

    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 49、字母异位词分组

思路：设置一个数组26位，每个数组都填充为0，但一个字符串的字符出现就在数组里面加1，并且放到map里面，key表示的是26位数组，value表示每次返回的数组

var groupAnagrams = function(strs) {
    if(strs.length === 0) return []
    const map = new Map()
    
    for(const str of strs){
        const characters = Array(26).fill(0)

        for(let i=0;i<str.length;i++){
            const ascii = str.charCodeAt(i) - 97
            characters[ascii]++
        }
        const key = characters.join()
        if(map.has(key)){
            map.set(key,[...map.get(key),str])
        }else{
            map.set(key,[str])
        }
    }

    const result = []
    for(const arr of map){
        result.push(arr[1])
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 242、有效字母异位词

思路：判断每个字符出现的次数即可，A出现的字符+1，B字符串出现的字符-1，用map遍历一次如果为0则为true

var isAnagram = function(s, t) {
    if(s.length !== t.length){
        return false
    }

    const map = new Map()
    for(let i=0;i<s.length;i++){
        if(map.has(s[i])){
            map.set(s[i],map.get(s[i])+1)
        }else{
            map.set(s[i],1)
        }

        if(map.has(t[i])){
            map.set(t[i],map.get(t[i])-1)
        }else{
            map.set(t[i],-1)
        }
    }

    for(const letter of map){
        if(letter[1] !== 0){
            return false
        }
    }

    return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 283、移动零

var moveZeroes = function(nums) {
    if(nums.length === 0) return []

    let j = 0
    for(let i=0;i<nums.length;i++){
        if(nums[i]!==0){
            nums[j] = nums[i]
            j++
        }
    }
    for(j;j<nums.length;j++){
        nums[j] = 0
    }

    return nums
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 328、奇偶链表

思路：通过改变奇偶链表下个next的指向，并存好偶数链表，最后指向该变量即可

var oddEvenList = function(head) {
    if(head === null){
        return null
    }

    if(head.next === null){
        return head
    }

    let odd = head
    let event = head.next
    let eventHead = head.next

    while(event !==null && event.next !==null){
        odd.next = odd.next.next
        odd = odd.next
        event.next = event.next.next
        event = event.next
    }

    odd.next = eventHead

    return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 349、两个数组的交集

思路：找两个数组同时出现的数，并且不重复，返回数组

var intersection = function(nums1, nums2) {
    const result = new Set()

    for(let num of nums1){
        if(nums2.includes(num)){
            result.add(num)
        }
    }

    return  [...result]
};
1
2
3
4
5
6
7
8
9
10
11

# 509、斐波那契数列

思路：动态规划=>递归 + 记忆缓存memoize

var fib = function(n) {
    if(n<=1) return n
    let dp = []
    dp[0] = 0
    dp[1] = 1
    function memoize(number){
        if(dp[number]!==undefined){
            return dp[number]
        }else{
            dp[number] = memoize(number-1) + memoize(number-2)
            return dp[number]
        }
    }

    let result = memoize(n)
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 733、图像渲染

沉没法：dfs遍历（深度优先）

var floodFill = function(image, sr, sc, newColor) {
    if(image[sr][sc] === newColor){
        return image
    }

    let oldColor = image[sr][sc]
    function dfs(sr,sc){
        if(sr<0||sr>=image.length||sc<0||sc>=image[0].length||image[sr][sc]!==oldColor){
            return
        }

        image[sr][sc] = newColor
        dfs(sr-1,sc)
        dfs(sr+1,sc)
        dfs(sr,sc-1)
        dfs(sr,sc+1)
    }
    dfs(sr,sc)
    return image
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 796、旋转字符串

思路：includes判断两个的A是否有B字符串

var rotateString = function(s, goal) {
    if(s.length !== goal.length) return false

    const str = s + s 
    return str.includes(goal)
};
1
2
3
4
5
6

# 836、矩阵重叠

思路：画图即可

var isRectangleOverlap = function(rec1, rec2) {
    if(rec1[2]<=rec2[0] || rec1[0]>=rec2[2] || rec1[1]>=rec2[3] || rec1[3]<=rec2[1]){
        return false
    }
    return true
};
1
2
3
4
5
6

# 2、两数相加

var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode()
    let curr = dummy
    let carry = 0
    while(l1!==null||l2!==null){
        let sum = 0
        if(l1!==null){
            sum += l1.val
            l1 = l1.next
        }
        if(l2!==null){
            sum += l2.val
            l2 = l2.next
        }
        sum += carry
        curr.next = new ListNode(sum%10)
        carry = Math.floor(sum/10)
        curr = curr.next
    }

    if(carry>0){
        curr.next = new ListNode(carry)
    }
    return dummy.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 905、按奇偶排序数组

var sortArrayByParity = function(nums) {
    let left = 0
    let right = nums.length-1
    while(left<right){
        //左指针对应奇数值，右指针对应偶数值，进行交换
        if(nums[left]%2===1&&nums[right]%2===0){
            [nums[left],nums[right]] = [nums[right],nums[left]]
        }
        //左指针对应的是偶数值，符合题意，继续向右移动
        if(nums[left]%2===0){
            left++
        }
        //右指针对应的是奇数值，符合题意，继续向左移动
        if(nums[right]%2===1){
            right--
        }
    }
    return nums
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 922、按奇偶排序数组II

var sortArrayByParityII = function(nums) {
    let j = 1
    for(let i=0;i<nums.length;i+=2){
        if(nums[i]%2===1){
            while(nums[j]%2===1){
                j += 2
            }
            [nums[i],nums[j]] = [nums[j],nums[i]]
        }
    }
    return nums
};
1
2
3
4
5
6
7
8
9
10
11
12

# 414、第三大的数

var thirdMax = function(nums) {
    nums.sort((a,b)=>b-a)
    const set = new Set()
    for(let i=0;i<nums.length;i++){
        if(!set.has(nums[i])){
            set.add(nums[i])
        }
    }
    let result = [...set]
    if(result.length<3){
        return result[0]
    }else{
        return result[2]
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 198、旋转数组

思路：我们可以用一个额外的数组来将每个元素放在正确的位置上，也就是原本数组里下标为i的我们把它放到（i+k）% 数组长度的位置。然后把新的数组拷贝到原数组中。

这个解法用到了一个技巧 a[(i+k) % nums.length] = nums[i]; 也是这道题目解题的关键。

var rotate = function(nums, k) {
    const result = []
    for(let i=0;i<nums.length;i++){
        result[(i+k)%nums.length] = nums[i]
    }
    for(let i=0;i<nums.length;i++){
        nums[i] = result[i]
    }
    return nums
};
1
2
3
4
5
6
7
8
9
10

# 577、反转字符串中的单词III

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
1
2
var reverseWords = function(s) {
    const arr = s.split(" ")
    const result = []
    let j = 0
    for(let str of arr){
        for(let i=str.length-1;i>=0;i--){
            result[j] = str[i]
            j++    
        }
        if(j<s.length){
            result[j] = " "
            j++
        } 
    }
    console.log(result)
    return result.join("")
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 反转字符串中的单词IV

输入：'abc hello1 good! race'
输出：'cba hello1 good! ecar'
1
2
let str = 'abc hello1 good! race'
function reverse(s){
    const arr = s.split(" ")
    const result = []
    let j = 0
    for(let str of arr){
        if(!/^[a-zA-Z]+$/.test(str)){
            for(let i=0;i<str.length;i++){
                result[j] = str[i]    
                j++
            }
        }else{
            for(let i=str.length-1;i>=0;i--){
                result[j] = str[i]
                j++
            }
        }
        if(j<s.length){
            result[j] = " "
            j++
        }
    }
    return result.join("")
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 统计一个字符串字符出现最多的次数及字母

function maxSort(sty){
    let obj = {}
    for(var i = 0; i< str.length; i++){
      let key = str[i];
      if(!obj[key]){
        obj[key] = 1;
      }else{
        obj[key] ++;
      }
    }
    let max = -1;
    let max_key = '';
    let key;
    for(key in obj){
      if(max<obj[key]){
        max=obj[key];
        max_key = key;
      }
    }
    console.log(max_key+"为最多出现字符，出现的次数为"+max);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 二叉树介绍

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

img

二叉树中的节点最多只能有两个子节点：左侧子节点和右侧子节点。我们接下来主要来实现一个二叉搜索树（BST）。它是二叉树的一种，但是只允许你在左侧节点存储比父节点小的值，在右侧节点存储比父节点大（或者等于）的值。如下图：

img

# 二叉搜索树(BST)

  • 若它的左子树不为空，则所有左子树上的值均小于其根节点的值
  • 若它的右子树不为空，则所有右子树上的值均大于其根节点得值
  • 它的左右子树也分别为二叉搜索树

1.jpg

# 172、二叉搜索树中的搜索

 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    if(root == null) return null
	if(root.val === val) return root
    if(root.val > val){
        return searchBST(root.left,val)
    }else if(root.val < val){
        return searchBST(root.right,val)
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 235、二叉搜索树的最近公共祖先


/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  if (
    (root.val > p.val && root.val < q.val) ||
    (root.val < p.val && root.val > q.val) ||
    root.val === p.val ||
    root.val === q.val
  ) {
    return root;
  } else if (root.val > q.val) {
    return lowestCommonAncestor(root.left, p, q);
  } else {
    return lowestCommonAncestor(root.right, p, q);
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 236、二叉树的最近公共祖先

var lowestCommonAncestor = function(root, p, q) {
    // 如果节点为空 返回null
    if (root===null ) return null;

    if (root.val === p.val || root.val === q.val) return root;


    let x = lowestCommonAncestor(root.left,p,q);
    let y = lowestCommonAncestor(root.right,p,q);

    if (x && y) {
        return root;
    } else {
        return x || y;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
编辑 (opens new window)
#算法
上次更新: 2021/12/06, 21:28:32
uni-app
Vue3实战难点

← Vue3实战难点→

最近更新
01
大文件分片上传
08-05
02
Vue3实现OSS存储
08-05
03
H5 TTS
08-05
更多文章>
Theme by Vdoing | Copyright © 2019-2024 Aiden Wu | MIT License
×