数组基础#

1
class Solution:
2
    # 二分查找前需要明确区间定义：选择[left, right]还是[left, right)
3
    # 这里采用左闭右闭区间[left, right]
4
    def search(self, nums: List[int], target: int) -> int:
5
        # nums下标范围是[0, len(nums)-1]，采用[left, right]区间，所以right初始值为len(nums)-1
6
        left, right = 0, len(nums) - 1
7
        # 当left == right时，区间[left, right]仍然有效，所以条件是left <= right
8
        while left <= right:
9
            mid = left + (right - left) // 2
10
            if nums[mid] > target:
11
                # nums[mid]已经比较过，且大于target，所以新的right范围需要排除mid
12
                right = mid - 1
13
            elif nums[mid] < target:
14
                # nums[mid]已经比较过，且小于target，所以新的left范围需要排除mid
15
                left = mid + 1
16
            else:
17
                return mid
18
        return -1

1
class Solution:
2
    # 因为数组有序，我们希望插入后仍然有序
3
    # 插入的合法位置，一定是"从左往右数，第一个不小于 target 的位置"
4
    # 这就是"找第一个 >= target 的位置"
5
    def searchInsert(self, nums: List[int], target: int) -> int:
6
        left, right = 0, len(nums) - 1
7
        while left <= right:
8
            mid = left + (right - left) // 2
9
            if nums[mid] > target:
10
                right = mid - 1
11
            elif nums[mid] < target:
12
                left = mid + 1
13
            else:
14
                return mid
15
        # 二分查找过程中保持的循环不变量：
16
        # - nums[0..left-1] < target
17
        # - nums[right+1..end] > target
18
        # 也就是说，left左边所有元素都 < target，right右边所有元素都 > target
19
        # 当循环结束时，left 正好指向第一个 >= target 的位置（也是插入位置）
20
        return left

1
class Solution:
2
    def searchRange(self, nums: List[int], target: int) -> List[int]:
3
        left, right = self.leftBound(nums, target), self.rightBound(nums, target)
4
        return [left, right]
5

6
    # 寻找左边界就是找第一个 >= target 的位置
7
    def leftBound(self, nums, target):
8
        left, right = 0, len(nums) - 1
9
        while left <= right:
10
            mid = left + (right - left) // 2
11
            if nums[mid] < target:
12
                left = mid + 1
13
            else:
14
                # 寻找左边界：当nums[mid] == target时，继续向左收缩，寻找最左端的target
15
                right = mid - 1
16
        # 循环结束后，left 是最后一个 <= target 的位置
17
        # 检查边界条件：确保left在有效范围内，且nums[left]确实等于target
18
        return left if left >= 0 and left < len(nums) and nums[left] == target else -1
19

20
    # 寻找右边界就是找到第一个 <= target 的位置
21
    def rightBound(self, nums, target):
22
        left, right = 0, len(nums) - 1
23
        while left <= right:
24
            mid = left + (right - left) // 2
25
            if nums[mid] > target:
26
                right = mid - 1
27
            else:
28
                # 寻找右边界：当nums[mid] == target时，继续向右收缩，寻找最右端的target
29
                left = mid + 1
30
        # 循环结束后，right 是第一个 >= target 的位置
31
        # 检查边界条件：确保right在有效范围内，且nums[right]确实等于target
32
        return right if right >= 0 and right < len(nums) and nums[right] == target else -1

1
class Solution:
2
    # 本质是查找满足 mid * mid <= x 的最大整数 mid
3
    # 即找到最后一个使得平方不超过 x 的数
4
    def mySqrt(self, x: int) -> int:
5
        left, right = 0, x
6
        while left <= right:
7
            mid = left + (right - left) // 2
8
            if mid * mid > x:
9
                right = mid - 1
10
            elif mid * mid < x:
11
                left = mid + 1
12
            else:
13
                return mid
14
        # 循环结束时：
15
        # - 所有小于等于 x 的平方都在 [0, right]
16
        # - 所有大于 x 的平方都在 [left, x]
17
        # 此时 right 是满足 mid*mid <= x 的最大整数，即 x 的整数平方根
18
        return right

1
class Solution:
2
    def isPerfectSquare(self, num: int) -> bool:
3
        left, right = 0, num
4
        while left <= right:
5
            mid = left + (right - left) // 2
6
            temp = mid * mid
7
            if temp < num:
8
                left = mid + 1
9
            elif temp > num:
10
                right = mid - 1
11
            else:
12
                return True
13
        return False

1
class Solution:
2
    # 双指针思路：slow指针指向新数组的下一个待填充位置，fast指针遍历原数组
3
    # 当fast指向的值等于val时，fast继续向前移动（跳过该元素）
4
    # 当fast指向的值不等于val时，将该值复制到slow位置，然后slow和fast都向前移动
5
    def removeElement(self, nums: List[int], val: int) -> int:
6
        slow = 0
7
        for fast in range(len(nums)):
8
            if nums[fast] != val:
9
                nums[slow] = nums[fast]
10
                slow += 1
11
        return slow

1
class Solution:
2
    # 思路与上题相同：将val改为0，额外步骤是将数组后面的位置全部填充为0
3
    def moveZeroes(self, nums: List[int]) -> None:
4
        slow = 0
5
        for fast in range(len(nums)):
6
            if nums[fast] != 0:
7
                nums[slow] = nums[fast]
8
                slow += 1
9
        # 将slow之后的所有位置填充为0
10
        for i in range(slow, len(nums)):
11
            nums[i] = 0

1
class Solution:
2
    def backspaceCompare(self, s: str, t: str) -> bool:
3
        s = self.traverse(s)
4
        t = self.traverse(t)
5
        return s == t
6

7
    def traverse(self, s):
8
        s = list(s)
9
        slow = 0
10
        for fast in range(len(s)):
11
            if s[fast] != '#':
12
                s[slow] = s[fast]
13
                slow += 1
14
            else:
15
                # 关键处理：当fast指向'#'时，需要模拟退格操作
16
                # slow向后退一格（如果可能），表示删除前一个字符
17
                if slow > 0:
18
                    slow -= 1
19
        return ''.join(s[:slow])

1
class Solution:
2
    # 左右双指针策略：由于存在负数，平方后最大值只能出现在数组两端
3
    # 比较左右指针位置元素的平方大小，将较大值放入结果数组的末尾
4
    # 然后移动对应指针，继续比较，直到处理完所有元素
5
    def sortedSquares(self, nums: List[int]) -> List[int]:
6
        left, right = 0, len(nums) - 1
7
        res = [0] * len(nums)
8
        cur = len(nums) - 1  # 结果数组的填充位置，从后往前填充
9
        while left <= right:
10
            multi_left = nums[left] * nums[left]
11
            multi_right = nums[right] * nums[right]
12
            if multi_left >= multi_right:
13
                res[cur] = multi_left
14
                left += 1
15
            else:
16
                res[cur] = multi_right
17
                right -= 1
18
            cur -= 1
19
        return res