基础编程题
二分搜索
-
经典二分搜索
需要注意的点
- 循环条件
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 - 循环条件
-
一个有重复元素的数组中查找 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 # 因为走到这里有两种情况 找到目标 或者没有目标
链表
-
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
-
翻转链表
定义两个指针
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 - 连接
-
判断链表是否有环
快慢指针 如何证明？
感想： 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
-
找到环形链表的入口
先判断有没有环 代码同上
之后将快指针移动到链表头 两个指针同时移动 如何证明？？
使用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
-
计算环的长度
快慢指针在环内相遇之后 让满指针继续移动 再次相遇经过多少步就可以计算环的长度
-
删除单链表倒数第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
求链表中间节点
判断两个链表是否相交
队列和栈
字符串
排序
-
插入排序
- 左侧已排序
- 右侧未排序
- 将未排序部分的第一个元素插入到已排序部分的合适的位置
- 插入排序稳定 相同值的元素的相对顺序不会改变
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
-
归并排序
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
-
快速排序
效率底 但是容易理解的版本 生成了新的数组
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.pngdef 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
