基础编程题

二分搜索

1. 经典二分搜索

   需要注意的点

   • 循环条件 left <= right 还是 left < right
     • 需要看 left == right 是不是可以进入循环 可能是target吗
     • 需要防止程序死循环 如果left == right == mid 在循环体内不能出去 就会构成死循环
   • 左右边界更新 right = mid - 1 还是 right = mid

   class Solution:
       def bs(self, nums, target):
           left, right = 0, len(nums) - 1
           while left <= right:
               mid = (left + right) // 2
               if nums[mid] == target:
                   return mid + 1
               elif nums[mid] < target:
                   left = mid + 1  # 为什么可以+1 因为mid不可能是target 
               else:
                   right = mid - 1  # 同理 这样也保证了算法可以收敛 不会死循环
           return -1
   

2. 一个有重复元素的数组中查找 key 的最左位置

   跟第一题的区别：

   • 循环条件
   • 边界更新
   • 循环体内不判断是否找到目标 循环体外才判断 需要考虑出循环的两种情况

   class Solution:
       def bs(self, nums, target):
           left, right = 0, len(nums) - 1
           while left < right:
               mid = (left + right) // 2
               if nums[mid] < target: # 左半部分可以丢掉 并且mid不可能是target
                   left = mid + 1
               else: # nums[mid] >= target
                   right = mid # 因为mid可能是target
           return right if nums[right] == target else -1 # 因为走到这里有两种情况 找到目标 或者没有目标
   

链表

1. O(1)时间复杂度删除链表节点

   题目描述：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。
   解题思路：常规的做法是从链表的头结点开始遍历，找到需要删除的节点的前驱节点，把它的 next 指向要删除节点的下一个节点，平均时间复杂度为O(n)，不满足题目要求。
   那是不是一定要得到被删除的节点的前一个节点呢？其实不用的。我们可以很方面地得到要删除节点的下一个节点，如果我们把下一个节点的内容复制到要删除的节点上覆盖原有的内容，再把下一个节点删除，那就相当于把当前要删除的节点删除了。

   单向链表不能回头 只能往后面走

   class Solution:
       def deleteNode(self, pHead, Node):
           if pHead == None or Node == None:
               return
           if Node.next:
               Node.val = Node.next.val
               Node.next = Node.next.next
           # 此时确定 Node 位于链表尾
           elif pHead == Node: # 链表只有一个元素
               pHead = None
           else:
               while pHead.next.next:
                   pHead = pHead.next
               pHead.next = None
           return pHead
   

2. 翻转链表

   定义两个指针pre和cur，每反转一个节点涉及到三个操作：

   • 连接cur指针的next
   • 分别移动指针pre和cur

   关于Python 等号左右多个变量同时赋值
   两个原则：

   • 等号右边的变量存放的都是旧的值 等号左边的变量存放的都是新的值
   • 等号左边的变量会被刷新 注意先后顺序 先取值后赋值

   class Solution:
       def ReverseList(self, pHead):
           prev = None # 辅助节点
           while pHead:
               pHead.next, prev, pHead = prev, pHead, pHead.next
           return prev
   

   正常的代码

   class Solution:
       def reverse(self, pHead):
           prev = None
           while pHead:
               tp = pHead.next # 存下下一个节点
               pHead.next = prev
               prev = pHead
               pHead = tp
           return prev
   

   递归版本：

   class Solution:
       def ReverseList(self, pHead):
           if not pHead or not pHead.next: # 停止向下递归 往回返
               return pHead
           res = self.ReverseList(pHead.next)
           pHead.next.next = pHead # 连接
           pHead.next = None # 尾节点
           return res
   

3. 判断链表是否有环

   快慢指针 如何证明？

   感想： while循环内部作为函数return出口很常见 while循环体外往往代表着另外一种情况

   class Solution(object):
       def hasCycle(self, head):
           """
           :type head: ListNode
           :rtype: bool
           """
           fast, slow = head, head
           while fast and fast.next:
               fast = fast.next.next
               slow = slow.next
               if fast == slow: 
                   return True
           return False
   

4. 找到环形链表的入口

   先判断有没有环 代码同上

   之后将快指针移动到链表头 两个指针同时移动 如何证明？？

   使用while - else语法区分出循环的两种情况

   class Solution(object):
       def detectCycle(self, head):
           """
           :type head: ListNode
           :rtype: bool
           """
           slow = fast = head
           while fast and fast.next:
               slow = slow.next
               fast = fast.next.next
               if slow == fast:
                   break
           else: # 因为出循环存在两种情况 所以需要区分 这里使用while else语法作区分
               return None
           while head != slow: # 直接移动头指针
               slow = slow.next
               head = head.next
           return head
   

5. 计算环的长度

   快慢指针在环内相遇之后 让满指针继续移动 再次相遇经过多少步就可以计算环的长度

6. 删除单链表倒数第n个节点

   class Solution:
       def FindKthToTail(self, head, k):
           # write code here
           if head == None or k <= 0:
               return None
   
           # 设定两个指针 第一个指针指向头节点 第二个指向k-1节点
           p1, p2 = head, head
           i = 0
           while p2.next and i < k - 1:
               p2 = p2.next
               i += 1
           # while 循环结束 一定要对各种不同的情况进行判断
           if i != k - 1:  # 链表没有K个元素
               return None
   
           while p2.next:
               p1, p2 = p1.next, p2.next
           return p1
   

for循环版本

  class Solution:
    def FindKthToTail(self, head, k):
        if not head or k <= 0:
            return
        fast = slow = head
        for i in range(k - 1):
            if not (fast and fast.next): # 为了保证fast指针最后停下的位置也是非空的  所以加上fast.next
                return
            fast = fast.next

        while fast and fast.next:
            fast = fast.next
            slow = slow.next
        return slow

7. 求链表中间节点

8. 判断两个链表是否相交

队列和栈

字符串

排序

1. 插入排序

   • 左侧已排序
   • 右侧未排序
   • 将未排序部分的第一个元素插入到已排序部分的合适的位置
   • 插入排序稳定 相同值的元素的相对顺序不会改变

image.png

def insertionSort(nums):
    for i in range(1, len(nums)):
        cur, p = nums[i], i  # 取出当值位置的数值 因此当前位置可以被填充
        while p - 1 >= 0 and nums[p - 1] > cur:
            nums[p] = nums[p - 1]
            p -= 1
        nums[p] = cur
    return nums

2. 归并排序

   image.png

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)  # 合并左右两个已经排序的部分

def merge(left, right):
    l, r = 0, 0
    result = [] # 需要开辟新空间存放排完序的结果
    while l < len(left) and r < len(right):
        if left[l] < right[r]:  # 将left与right较小元素按序加入新序列
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

3. 快速排序

   效率底 但是容易理解的版本 生成了新的数组

   def quicksort(nums):
       size = len(nums)
       if not nums or size < 2:  # 递归出口，空数组或者只有一个元素的数组都是有序的
           return nums
       idx = 0 # 标定点
       pivot = nums[idx] # 标定值
       less_part = [nums[i] for i in range(size) if nums[i] <= pivot and idx != i]
       great_part = [nums[i] for i in range(size) if nums[i] > pivot and idx != i]
       return quicksort(less_part) + [pivot] + quicksort(great_part)
   

   正常 版本 直接在原始数组上修改

   image.png

   def quickSort(nums, first, last):
       splitpoint = partition(nums, first, last)
       quickSort(nums, first, splitpoint - 1)
       quickSort(nums, splitpoint + 1, last)
   
   
   def partition(nums, first, last):
       rand = randint(first, last)  # 优化，随机取标定点，以解决近乎有序的列表
       nums[first], nums[rand] = nums[rand], nums[first]
   
       pivot = nums[first]
       left = first + 1
       right = last
       while True:  # 这里使用了双路快排，以解决有大量相同值的列表
           while left <= right and nums[left] < pivot:
               left += 1
           while right >= left and nums[right] > pivot:
               right -= 1
   
           if left > right:
               break
           else:
               nums[left], nums[right] = nums[right], nums[left]
               left += 1
               right -= 1 # 这两行代码必须有 否则程序可能死循环 测试样例 [3,2,2,2,3]
       nums[first], nums[right] = nums[right], nums[first] # right处于<=v部分最后一个元素 
       return right
   
   

动态规划