leetcode

一、数组

1. 二分查找

704、二分查找	35、搜索插入位置	34、在排序数组中查找元素的第一个和最后一个位置
仅需查值，存在则返回middle	最后左指针索引即应插入的位置	有重复元素寻找边界，两次二分查找

704.二分查找

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

提示：数组中无重复元素（不然下标不唯一）

二分查找的前提条件：数组为有序数组

算法思路： 1. 确定区间 2. 确定循环条件 3. 确定左右边界

二分查找中最关键的点在于区间的定义。在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作。区间的定义一般为两种，左闭右闭即 left=0, right=len(nums)-1 或者左闭右开 left=0, right=len(nums) 。

[left, right]

• 因为定义target在[left, right]区间，因此while循环中条件为left <= right

• if (nums[middle] > target) right 要赋值为middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的右区间结束下标位置就是 middle - 1

• if (nums[middle] < target) left 要赋值为middle + 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle + 1

  class Solution(object):
      def search(self, nums, target):
          """
          :type nums: List[int]
          :type target: int
          :rtype: int
          """
          left = 0
          right = len(nums)-1
  
          while (left<=right):
              # middle = left + ((right - left) / 2)这种写法是为了防止int类型数据溢出
              middle = (left+right)//2
  
              if (nums[middle]>target):
                  right = middle-1
              elif (nums[middle]<target):
                  left= middle+1
              else: 
                  return middle
          return -1

[left, right)

• 因为定义target在[left, right)区间,因此while循环中条件为left < right

• if (nums[middle] > target) right 要赋值为middle ，因为当前这个nums[middle]一定不是 target ，右指针更新后while循环右侧开区间没有考虑middle 。

• if (nums[middle] < target) left 要赋值为middle + 1 ，因为左边界是能取到的。

  class Solution(object):
      def search(self, nums, target):
          """
          :type nums: List[int]
          :type target: int
          :rtype: int
          """
          left = 0
          right = len(nums)
  
          while (left < right):
              middle = (left+right)//2
  
              if (nums[middle]>target):
                  right = middle
              elif (nums[middle]<target):
                  left= middle+1
              else: 
                  return middle
          return -1

  35.搜索插入位置

  给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

  提示：请必须使用时间复杂度为 O(log n) 的算法，nums 为 无重复元素 的升序排列数组。

  **算法思路：**1. 目标值等于数组中某元素，return middle

  ​ 2. 当目标值需要插入数组中，最后返回的下标left = right + 1，跳出循环。

  class Solution(object):
      def searchInsert(self, nums, target):
          """
          :type nums: List[int]
          :type target: int
          :rtype: int
          """
  
          left, right=0, len(nums)-1
          while (left<=right):
              middle=(left+right)//2
  
              if target==nums[middle]:
                  return middle
              elif nums[middle]<target:
                  left = middle+1
              else: 
                  right = middle-1
          # 此处可以是left或者right + 1
          return left

  

  

上图两个例子反映左指针即是要插入的下标位置。

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

给你一个按照非递减顺序排列的整数数组nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target ，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

**算法思路：**1. 暴力求解：利用数组有序的特点从头到尾遍历一次数组。遍历到的元素刚好等于target记录为第一个位置，遍历到刚好不等于target的元素记录为最后一个位置。

​ 2. 二分查找：目标元素在有序数组中可能存在多个，当nums[middle]恰好等于target时，还要继续查找。用两个二分查找，一个二分查找查找左边界，另一个查找右边界。

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = self.searchleft(nums, target)
        right = self.searchright(nums, target)
        return [left, right]

    def searchleft(self, nums, target):
        left, right = 0, len(nums) - 1

        while (left <= right):
            mid = left + ((right-left)/2)

            if (target <= nums[mid]):
                right = mid - 1
            else: 
                left = mid + 1

        if left >= len(nums) or nums[left]!=target:
            return -1

        return left

    def searchright(self,nums,target):
        left, right = 0,len(nums)-1

        while (left <= right):
            mid = left + ((right-left)/2)

            if (target>=nums[mid]):
                left = mid + 1
            else: 
                right = mid - 1

        if right < 0 or nums[right]!=target:
            return -1

        return right

2. 移除元素

27. 移除元素

给你一个数组 nums 和一个值 val ，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

**算法思路：**双指针法（快慢指针法）

**快指针：**遍历数组元素

**慢指针：**指向更新新数组下标的位置

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        # 此处slow、fast指向同一位置，最终返回的slow即数组长度。若slow与fast差一位，则slow +1为数组长度，对应26题
        fast = 0
        slow = 0
        while fast < len(nums):
            if (nums[fast]!= val):
                nums[slow]=nums[fast]
                slow+=1
            fast+=1
        return slow

977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums ，返回 每个数字的平方 组成的新数组，要求也按非递减顺序排序。

算法思路：数组平方的最大值就在数组的两端，不是最左边就是最右边。可以考虑双指针法了， i 指向起始位置， j 指向终止位置。定义一个新数组 ans ，和原数组一样的大小，让 k 指向 ans 数组终止位置。

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = [0] * len(nums)-1
        i, j, k = 0, len(nums)-1, len(nums)-1
        while i <= j:
            if nums[i] * nums[i] > nums[j] * nums[j]:
                ans[k] = nums[i] * nums[i]
                i += 1
            else:
                ans[k] = nums[j] * nums[j]
                j -= 1
            k -= 1
       return ans
            

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0 。

算法思路： 双指针法

• 使用左右指针，left 和 right 之间的长度即为滑动窗口的大小（即连续数组的大小）。
• 如果滑动窗口内的值 sum >= target，维护连续数组最短长度，left 向右移动，缩小滑动窗口。
• 如果滑动窗口内的值 sum < target，则 right 向有移动，扩大滑动窗口。

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        # 首先初始化left和right指针以及当前和sum、最小长度 min_len
        sum = 0
        left, right = 0, 0
        min_len = int("inf")
        n = len(nums)
        
        #滑动窗口left<=right一直满足，最外层while条件是右指针小于n
        while right < n:
            sum += nums[right]
            while sum >= target:
                length = right - left + 1
                min_len = min(length, min_len)
                sum -= nums[left]
                left += 1
            right += 1
		if min_len == float('inf'):
            return 0
        else:
            return min_len

59. 螺旋数组II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

**算法思路：**模拟法，设定边界。

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        """
        初始需要四条边界的初值，初值以及一个0矩阵
        """
        l, r, t, b = 0, n-1, 0, n-1
        nums, target = 1, n*n
        mat = [[0 for _ in range (n)] for _ in range (n)]
        while nums <= target:
            for i in range (l, r+1):
                mat[t][i] = nums
                nums += 1
            t += 1
            # 上图为例：(1, 3) i先取1，再取2
            for i in range (t, b+1):
                mat[i][r] = nums
                nums += 1
            r -= 1
            # 上图为例：(1， -1) i先取1，再取0
            for i in range (r, l-1 , -1):
                mat[b][i] = nums
                nums += 1
            b -= 1
            # 上图为例：(1,0) i只取1
            for i in range (b, t-1, -1):
                mat[i][l] = nums
                nums += 1
            l += 1
        return mat

二、链表

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

**算法思路：**设置虚拟头结点，统一所有节点的移除操作。

• 新建虚拟头结点，并与原链表相连。 dummy_head = ListNode(next=head)
• 新增指针 cur 指向 dummy_head 头结点来遍历链表，进行循环判断是否移除元素。
• 最后返回 dummy_head.next ，原始 head 可能被删除。

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_head = ListNode(next = head)
        cur = dummy_head
        while(cur.next != None):
            if (cur.next.val == val):
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next

707. 设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next 。 val 是当前节点的值， next 是指向下一个节点的指针。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

**算法思路：**设置虚拟头结点，统一所有节点的操作。

• 一个链节点类（新增节点），一个链表类（操作链表，需设置虚拟头结点）。
• 需要遍历链表的操作都要新增cur指针，指向虚拟头结点，用于遍历。

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

算法思路： 双指针法依次操作每个结点，循环终止条件为cur为None。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        pre = None

        while (cur):
            temp = cur.next 
            cur.next = pre
            pre = cur
            cur = temp
        return pre

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即只能进行节点交换）。

算法思路：

• 使用虚拟头节点，新增遍历指针 cur 指向虚拟头节点。
• 确定循环终止条件，分奇偶情况。
• 交换节点过程中注意保存中间节点 。
• 确定 cur 的下次位置。

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        new_node = ListNode(next=head)
        cur = new_node

        while (cur.next and cur.next.next):
            temp1 = cur.next
            temp2 = cur.next.next.next

            cur.next = cur.next.next
            cur.next.next = temp1
            temp1.next = temp2

            cur = cur.next.next
        return new_node.next

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

算法思路： 虚拟头结点+双指针法。要删除倒数第n个结点，让fast移动n+1步，然后让fast和slow同时移动，直到fast指向链表末尾，最后改变slow的指向即可。此处，只有fast移动n+1步后，slow才能指向待删结点的前一个位置。让fast指针先走的目的是为了找到slow。

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        new_node = ListNode(next=head)
        fast = new_node
        slow = new_node

        while (n>=0):
            fast = fast.next
            n -= 1

        while (fast):
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next

        return new_node.next

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

算法思路： 双指针法。

• 快慢指针均指向头结点

• 确定快指针的循环条件（快指针一次走两步，要保证fast和fast->next不为空）

• 当快慢指针相遇，新增一个指针指向头结点，一个指针指向快或慢指针

• 确定内部循环条件，新增指针指向若不相等则不断后移，当两者相等时，即是入环的第一个节点。

  class Solution:
      def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
          slow, fast = head, head
          while (fast and fast.next):
              fast = fast.next.next
              slow = slow.next
              if (slow==fast):
                  index1 = slow
                  index2 = head
                  while (index1 != index2):
                      index1 = index1.next
                      index2 = index2.next
                  return index2
          return None
      

三、哈希表

要快速判断一个元素是否出现或是否在集合里的时候，就要考虑哈希法。但是哈希法是牺牲了空间换取了时间，要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

算法思路： 定义一个数组，来记录字符串s里字符出现的次数。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26
        for i in s:
            record[ord(i) - ord("a")] += 1
        for i in t:
            record[ord(i) - ord("a")] -= 1
        for i in range(26):
            if record[i] != 0:
                return False
        return True

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

算法思路： 如果数值过大，哈希值跨度大，一般使用set结构来存放数据。
ps：std::set 和 std::multiset 底层实现都是红黑树， std::unordered_set 的底层实现是哈希表， 使用 unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择 unordered_set 。直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        hash = {}
        ans = []
        for num in nums1:
            hash[num] = 1

        for num in nums2:
            if num in hash.keys() and hash[num] == 1:
                ans.append(num)
                hash[num] = 0	#去重
        return ans

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target ，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

算法思路： 利用哈希表map来缩短寻找 target - x 的时间。是否存在元素，所以元素是key，返回下标，下标即value

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash = {}
        for i, num in enumerate(nums):
            if target-num in hash:
                return [hash[target-num], i]
            hash[nums[i]]= i
        return []