跟着卡哥学算法Day 1：数组整体学习 & 常见题目

数组在内存空间中连续存储的，这样会使得通过下标获取数组元素很方便，但删除或新增元素时，就需要移动其他元素的位置。

接下来都通过 🌟 来代表题目难度：

简单：🌟
中等：🌟🌟
困难：🌟🌟🌟

经典题目#

704. 二分查找 🌟#

力扣链接

前提#

有序排列

无重复值

题目描述#

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
输入: nums = [-1,0,3,5,9,12], target = 9
2
输出: 4
3
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
输入: nums = [-1,0,3,5,9,12], target = 2
2
输出: -1
3
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

解题思路#

重点：定好区间

开闭：包含这个元素

左闭右闭：[left, right]

左闭右开：[left, right)

需要定义三个值：

left：0 左侧初始下标
right：nums.length - 1 右侧初始下标
middle

判断条件：

确保 left <= right

left + ((right - left) >> 1)：计算 middle
nums[middle] < target]：中间值小于目标值，目标值在右侧，更新 left 为middle + 1
nums[middle] > target]：中间值大于目标值，目标值在左侧，更新 right 为middle - 1
nums[middle] === target：等于目标值，返回 middle

代码#

1
function search(nums: number[], target: number): number {
2
  let left = 1
3
  let right = nums.length - 1
4
  while (left <= right) {
5
    const middle = left + ((right - left) >> 1)
6
    if (nums[middle] === target) return middle
7
    if (nums[middle] > target) {
8
      right = middle - 1
9
    } else {
10
      left = middle + 1
11
    }
12
  }
13
  return -1
14
}

相似题目#

35. 搜索插入位置 🌟

思路：

按照二分法找到的返回下标
未找到则返回 right + 1（left 一直增加，当一直未找到 targe 时，left 会不满足条件，即 left > right，此时 right + 1 就是插入的位置）

1
function searchInsert(nums: number[], target: number): number {
2
  let left = 0
3
  let right = nums.length - 1
4
  while (left <= right) {
5
    let middle = left + ((right - left) >> 1)
6
    if (nums[middle] > target) {
7
      right = middle - 1
8
    } else if (nums[middle] < target) {
9
      left = middle + 1
10
    } else {
11
      return middle
12
    }
13
  }
14
  return right + 1
15
}

34. 在排序数组中查找元素的第一个和最后一个位置 🌟🌟

解题思路：

两次二分查找
- 查找目标值第一次出现位置 nums[middle] >= target，一直移动 right
- 查找目标值最后一次出现位置 nums[middle] <= target，一直移动 left
target 在数组左或右，返回 [-1, -1]
target 在数组范围内，但不存在 right - left < 0，返回 [-1, -1]
target 在数组范围内，存在，返回 [left, right]

1
function searchRange(nums, target) {
2
  if (nums[0] > target || nums[nums.length - 1] < target) return [-1, -1]
3
  const left = searchLeft(nums, target)
4
  const right = searchRight(nums, target)
5
  if (right - left < 0) return [-1, -1]
6
  return [left, right]
7
}
8
function searchLeft(nums, target) {
9
  let left = 0
10
  let right = nums.length - 1
11
  while (left <= right) {
12
    let middle = left + ((right - left) >> 1)
13
    if (nums[middle] < target) {
14
      left = middle + 1
15
    } else {
16
      right = middle - 1
17
    }
18
  }
19
  return left
20
}
21
function searchRight(nums, target) {
22
  let left = 0
23
  let right = nums.length - 1
24
  while (left <= right) {
25
    let middle = left + ((right - left) >> 1)
26
    if (nums[middle] <= target) {
27
      left = middle + 1
28
    } else {
29
      right = middle - 1
30
    }
31
  }
32
  return right
33
}

69. x 的平方根 🌟

1
function mySqrt(x: number): number {
2
  if (x < 2) return x
3
  let left = 0
4
  let right = x
5
  while (left <= right) {
6
    let mid = left + ((right - left) >> 1)
7
    if (mid * mid < x) {
8
      left = mid + 1
9
    } else if (mid * mid > x) {
10
      right = mid - 1
11
    } else {
12
      return mid
13
    }
14
  }
15
  return right
16
}

367. 有效的完全平方数 🌟

1
function isPerfectSquare(num: number): boolean {
2
  let left = 0
3
  let right = num
4
  while (left <= right) {
5
    let mid = left + ((right - left) >> 1)
6
    if (mid * mid === num) {
7
      return true
8
    } else if (mid * mid < num) {
9
      left = mid + 1
10
    } else {
11
      right = mid - 1
12
    }
13
  }
14
  return false
15
}

27. 移除元素 🌟#

力扣链接 🌟

题目描述#

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。

解题思路#

双指针
- slow：填充进新数组的 value（只有 nums[fast] !== val 才填充进新数组）
- fast：代表新数组的 index

“一个萝卜一个坑”

代码#

1
function removeElement(nums: number[], val: number): number {
2
  let k = 0
3
  for (let i = 0; i < nums.length; i++) {
4
    if (nums[i] !== val) {
5
      nums[k] = nums[i]
6
      k++
7
    }
8
  }
9
  return k
10
}

相似题目#

26. 删除有序数组中的重复项 🌟

思路：

双指针
慢指针填充条件：当 nums[fast + 1] !== nums[fast] 时，填充进新数组

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

283. 移动零 🌟

思路：

双指针
填充条件：当 nums[fast] !== 0 时，填充进新数组
最后使用 fill 填充数组

1
function moveZeroes(nums: number[]): void {
2
  let slow = 0
3
  for (let fast = 0; fast < nums.length; fast++) {
4
    if (nums[fast] !== 0) {
5
      nums[slow] = nums[fast]
6
      slow++
7
    }
8
  }
9
  nums.fill(0, slow)
10
}

844. 比较含退格的字符串 🌟

思路：

1
function backspaceCompare(s, t) {
2
  const s1 = getResult(s)
3
  const t1 = getResult(t)
4
  return s1 === t1
5
}
6

7
function getResult(s) {
8
  let slow = 0
9
  let count = 0
10
  s = s.split('')
11
  for (let fast = 0; fast < s.length; fast++) {
12
    if (s[fast] !== '#') {
13
      s[slow] = s[fast]
14
      slow++
15
    } else {
16
      if (slow !== 0) {
17
        slow--
18
        s[slow] = ''
19
        count++
20
      }
21
    }
22
  }
23
  s.fill('', s.length - 1 - count)
24
  return s.join('')
25
}

977. 有序数组的平方 🌟#

力扣链接 🌟

思路：

双指针

1
function sortedSquares(nums: number[]): number[] {
2
  let i = 0
3
  const length = nums.length
4
  let j = length - 1
5
  let res = new Array(length).fill(0)
6
  let k = length - 1
7

8
  while (i <= j) {
9
    let left = nums[i] * nums[i]
10
    let right = nums[j] * nums[j]
11
    if (left < right) {
12
      res[k] = right
13
      j--
14
    } else {
15
      res[k] = left
16
      i++
17
    }
18
    k--
19
  }
20
  return res
21
}

音乐

音乐

经典题目#

704. 二分查找 🌟#

前提#

题目描述#

解题思路#

代码#

相似题目#

27. 移除元素 🌟#

题目描述#

解题思路#

代码#

相似题目#

977. 有序数组的平方 🌟#

音乐

文章目录