代码随想录刷题

数组

二分法

LeetCode No.704

先确定区间定义，左闭右开/左闭右闭，再确定循环条件，最后确定区间更新方式

def search(nums, target):
  left, right = 0, len(nums) - 1
  # 左闭右闭
  while left <= right:  # eg. [1,1]
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    elif nums[mid] < target:
      left = mid + 1
    else:
      right = mid - 1

  return -1


# def search(nums, target):
#     left, right = 0, len(nums)
#     # 左闭右开
#     while left < right: # eg. [1,1) 不合理
#       mid = (left + right) // 2
#       if nums[mid] == target:
#         return mid
#       elif nums[mid] < target:
#         left = mid + 1
#       else:
#         right = mid
#
#     return -1


# 单元测试
def test_search():
  nums = [1, 3, 5, 7, 9]
  assert search(nums, 1) == 0
  assert search(nums, 3) == 1
  assert search(nums, 5) == 2
  assert search(nums, 7) == 3
  assert search(nums, 9) == 4
  assert search(nums, 2) == -1
  assert search(nums, 10) == -1

  nums = []
  assert search(nums, 1) == -1

  nums = [1]
  assert search(nums, 1) == 0
  assert search(nums, 2) == -1


if __name__ == '__main__':
  test_search()

移除元素

leetcode No.27

双指针（快慢指针）

from typing import List


class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast, slow = 0, 0
        length = len(nums)
        while fast < length:
            if nums[fast] != val:
                try:
                    nums[slow] = nums[fast]
                    slow += 1

                except Exception as err:
                    print(nums, val)
                    print(slow, fast)
            fast += 1
        return slow + 1


def test_removeElement():
    s = Solution()

    # Test case where all elements in the list are equal to val
    nums1 = [3,2,2,3]
    val1 = 3
    assert s.removeElement(nums1, val1) == 2


if __name__ == '__main__':
    test_removeElement()

有序数组的平方

LeetCode No.977

直观想法： 先平方，再排序
实际： 双指针

from typing import List


class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        i = 0
        j = len(nums) - 1
        new_nums = [-1]* len(nums)
        new_index = -1
        while i<=j:
            if nums[i]**2 <= nums[j]**2:
                new_nums[new_index] = nums[j]**2
                j -= 1
            else :
                new_nums[new_index] = nums[i]**2
                i += 1
            new_index -= 1
        
        return new_nums

长度最小的子数组

LeetCode No.209

滑动窗口 ```python