面试算法题

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

合并两个有序数组

图 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--
  }
};

两数之和

图 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]))

选择排序

冒泡排序

插入排序

堆排序

归并排序

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

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