面试算法题

发表于2024-09-10更新于2024-10-08

双指针系列

合并两个有序数组

图 0

解决思路

逆向双指针，从后往前比较两个数组的元素大小。大的填入应在的位置，然后指针前移，小的不作操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 逆向双指针的方法
var merge = function(nums1, m, nums2, n) {
  let p1 = m-1,p2 = n-1,p = m+n-1  //三个指针，第一个用来遍历数组1中的每个值。
  //第二个用来遍历数组2中的每一个值，第三个用来存数据，从数组1的最后一个位置开始。
  while(p1>=0 && p2>=0){ // 双指针，从两个数组的最后一个数开始，倒着比较值的大小。
    if (nums2[p2]>=nums1[p1]){
      nums1[p] = nums2[p2]
      p2--
    }
    else{
      nums1[p] = nums1[p1]
      p1--
    }
    p--
  }
  while(p2>=0){//如果数组2中还有剩余的元素，全部放在数组1的前面
    nums1[p] = nums2[p2]
    p2--
    p--
  }
};

最长无重复子串

图 5

解题思路

滑动窗口

  • 1、使用left和right两个指针，分别表示滑动窗口的左右边界，初始时都指向字符串的开头。
  • 2、使用一个哈希表（或者数组）来记录字符是否出现过以及字符出现的位置。
  • 3、不断移动右指针 right，每次移动时判断当前字符是否出现过：
    • 如果当前字符已经出现过，并且在当前窗口内（即其位置大于等于 left），则更新 left 指针的位置为该字符上次出现的位置的下一个位置。
    • 如果当前字符没有出现过，或者虽然出现过但不在当前窗口内，则更新最长子字符串的长度。
  • 不断更新最长子字符串的长度，并返回结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var lengthOfLongestSubstring = function(s) {
  let l=0,r=0,max=0
  let map = new Map()
  while(r<s.length){
    //判断map的记录中，这个字符的值是否在滑动窗口内
    if (map.has(s[r]) && map.get(s[r]) >= l) {
      //如果在窗口内l指针指向当前记录值的后一位
      l = map.get(s[r])+1
    }
    //如果map中没有当前字符得记录或者有记录但是不在滑动窗口范围内
    map.set(s[r], r)
    max = Math.max(max, r - l + 1)
    r++
  }
  return max
}

判断子序列

图 6

解题思路

  • 初始化指针i，j分别指向字符串是，和t的起始位置；其中s是子串，t是较长的字符串
  • 遍历比较s[i]和t[j]的情况
    • 如果s[i]==t[j]，那么指向子串的指针+1，即i++；且j++
    • 如果不想等j++
  • 判断子序列：如果 i 移动到了 s 的末尾，则说明 s 是 t 的子序列，返回 true；否则返回 false。

代码

1
2
3
4
5
6
7
8
9
10
11
var isSubsequence = function(s, t) {
  let i=0,j=0
  //处理两个字符串都是空字符串的情况
  if (s==t) return true
  while (j<t.length){
    if (s[i]===t[j]) i++
    j++
  }
  if (i==s.length) return true
  else return false
};

两数之和

图 1

解题思路

使用字典,判断目标值减去当前值的结果是否，存在于字典中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
var twoSum = function(nums, target) {
  let map = new Map()
  // 判断target-当前元素的结果是否存在于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)
    }
  }
}

三数之和

图 2

解决思路回溯算法：

1、回溯的三部曲，参数确定，确定终止条件，单层递归逻辑。提升效率要剪枝
2、双指针法：对数组进行排序，先确定第一个数字，然后使用双指针分别总数组的第一个和第最后一个开始，判断当前总和，综合大，右边指针前移，否者左边指针后移。

去重逻辑：第一个数字的去重，和后面两个数字的去重。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var threeSum = function (nums) {
  let res = []
  nums = nums.sort((a,b)=>a-b) //首先要进行排序
  for (let i = 0; i < nums.length-2; i++) {  //减2是因为求得是三个元素的和。
    if (i > 0 && nums[i] == nums[i - 1]) continue //a去重
    let left = i + 1,right = nums.length - 1 //指定双指针
    while (left < right) {
      let sum = nums[i]+nums[left]+nums[right]
      if (sum>0) right--
      if (sum<0) left++
      if(sum===0){
        res.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--
      }
    }
  }
  return res
}

反转链表

图 3

自定义链表

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
var reverseList = function(head) {
  let prev = null
  let cur = head
  while(cur){
    // 这一步我忘记了，没有把next的值保存下来，直接给cur.next赋值了
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev //最后一个cur是null，他前面一个才是第一个有值的节点
};

排序算法

快速排序

其核心思想是分治，选择一个基准元素，将比基准小的元素放在左边，比基准大的元素放在右边。然后地柜对左右两个部分，分别进行快速排序。

快速排序复杂度
平均时间复杂度（Onlogn）、最坏情况O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quickSort(arr) {
  //终止条件
  if (arr.length <= 1) return arr
  //找基准,选择最后一个元素作为基准
  let std = arr.length - 1
  //用来存储左右两个数组
  let leftArr = [],
    rightArr = []
  for (let i = 0; i < std && i != std; i++) {
    if (arr[i] <= arr[std]) leftArr.push(arr[i])
    else rightArr.push(arr[i])
  }
  //分别处理左右两个子数组
  return [...quickSort(leftArr), arr[std], ...quickSort(rightArr)]
}
console.log(quickSort([5, 2, 9, 1, 7, 6,3,80,34]))

选择排序

选择最大的数，放在数组的最右边，然后再选择第二大的数，放在数组的右边第二的位置，以此类推。

选择排序复杂度
平均时间复杂度（Onlogn）、最坏情况O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function selectSort(arr){
  const n = arr.length-1
  // 从后往前排好arr的顺序，所以遍历从后往前
  for (let i=n;i>0;i--){
    let maxIndex = i
    // 将没排好序的过一遍
    for (let j=0;j<=i;j++){
      if (arr[j]>arr[maxIndex]) maxIndex = j
    }
    if (maxIndex != i){
      [arr[maxIndex],arr[i]] = [arr[i],arr[maxIndex]]
    }
  }
  return arr
}

冒泡排序

冒泡排序通过重复遍历要排序的列表，每次比较相邻的两个元素。如果顺序不正确，就交换它们的位置。这个过程会重复直到整个列表有序。

每一轮遍历会将一个最大的元素“冒泡”到末尾。

复杂度：时间复杂度：O(n²)

1
2
3
4
5
6
7
8
9
10
function populeSort(arr){
  let len = arr.length-1
  for(let i=0;i<len;i++){
    // 每一轮遍历都会将一个最大的元素“冒泡”到末尾，所以下一轮遍历就不用再遍历最后一个元素
    for(let j=0;j<len-1;j++){
      if(arr[j]>arr[j+1]) [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
    }
  }
  return arr
}

插入排序

插入排序将数组划分为已排序和未排序部分，从未排序部分取出元素，并将其插入到已排序部分的适当位置。这个过程会反复执行，直到所有元素都被插入到正确的位置。

复杂度：时间复杂度：O(n²) 最好情况（数组本身有序）：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function insertSort(arr){
  //有序无序两部分，从无序的数据中一次拿数据，插入到有序部分
  let len = arr.length
  // 第一个元素是有序部分，从第二个数据开始拿数据
  for(let i=1;i<len;i++){
    let curr = arr[i]
    let j=i-1
    //从有序数据的后面开始往前遍历，直到找到合适插入的位置
    while(j>=0 && curr<arr[j]){
      // 给将来要插入元素的地方腾位置
      arr[j+1] = arr[j]
      j--
    }
    arr[j+1] = curr
  }
  return arr
}

归并排序

归并排序是另一种分治算法，它将数组递归地拆分为两个子数组，直到每个子数组只有一个元素。然后将这些子数组有序地合并，直到所有元素合并成一个有序数组。

归并排序是一种稳定排序，而且它的最坏情况复杂度和平均复杂度都是 O(n log n)。

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
function mergeSort(arr){
  //终止条件，就是arr长度
  if (arr.length<=1) return arr
  //首先将数组分为二部分
  let mid = Math.floor(arr.length/2)
  let leftArr = arr.slice(0,mid)
  let rightArr = arr.slice(mid)
  return merge(mergeSort(leftArr),mergeSort(rightArr))
}

function merge(left,right){
  let result =[]
  let i=0,j=0
  while(i<left.length && j<right.length){
    if (left[i]<right[j]){
      result.push(left[i])
      i++
    }
    else{
      result.push(right[j])
      j++
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j))
}

堆排序

堆排序利用了堆这种数据结构。堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。堆排序的核心思想是：首先将数组构造成一个最大堆，然后依次将堆顶元素（最大值）与最后一个元素交换，再将剩下的元素重新调整为堆，直到排序完成。

复杂度：时间复杂度：O(n log n)

二叉树系列

层序遍历

前序遍历

递归法

1
2
3
4
5
6
7
8
9
10
11
var preorderTraversal = function (root) {
  const res = []
  const preorder = (rt)=>{
    if (!rt) return
    res.push(rt.val)
    preorder(rt.left)
    preorder(rt.right)
  }
  preorder(root)
  return res
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
var preorderTraversal = function (root) {
  let res = []
  if (!root) return res   // 应对空二叉树
  let queue = [root]
  while(queue.length){
    //每次从队列里去一个节点，把该节点的值添加到result，
    let cur = queue.pop()
    res.push(cur.val) //该节点的右孩子和左孩子依次加入节点，
    if (cur.right) queue.push(cur.right) //等到下一轮，就会分别依次遍历左孩子和有孩子了
    if (cur.left) queue.push(cur.left)
  }
return res
}

后序遍历

递归法

1
2
3
4
5
6
7
8
9
10
11
var postorderTraversal = function (root) {
  let res = []
  const postorder = (rt) => {
    if (!rt) return    //不要忘了这个条件
    postorder(rt.left)
    postorder(rt.right)
    res.push(rt.val)
  }
  postorder(root)
  return res
}

迭代法

1

中序遍历

递归法

1
2
3
4
5
6
7
8
9
10
11
var inorderTraversal = function (root) {
  let res =[]
  const inorder = (rt)=>{
    if (!rt) return
    rt.left && inorder(rt.left)
    res.push(rt.val)
    rt.right && inorder(rt.right)
  }
  inorder(root)
  return res
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var inorderTraversal = function (root) {
  // 入栈:左->右
  // 出栈:左 中 右
  let res = []
  const stack = []
  if (root) stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    if (!node) {
      res.push(stack.pop().val)
      continue
    }
    if (node.right) stack.push(node.right) // 右
    stack.push(node) // 中
    stack.push(null)
    if (node.left) stack.push(node.left) // 左
  }
  return res
}