以下哪种情况使用链表比数组更合适？

下面的python代码实现给定单链表头结点 head 和一个整数 val ，删除链表中所有结点值等于 val 的节点，并返回新的头结点，则横线处填写（ ）。

class ListNode:
	def __init__(self, val=0, next=None):
		self.val = val
		self.next = next

def removeElements(head: ListNode, val: int) -> ListNode:
	dummy = ListNode(0, head)
	cur = dummy
	while cur.next:
		if cur.next.val == val:
			__________________________
			del del_node
		else:
			cur = cur.next
	return dummy.next

下列python代码用Floyd判断一个单链表中是否存在环，链表的头节点为 head ，即用两个指针在链表上前进： slow 每次走 1 步， fast 每次走 2 步，若存在环， fast 终会追上 slow （相遇）；若无环， fast 会先到达 nullptr。横线上应填写（ ）。

class ListNode:
	def __init__(self, x):
		self.val = x
		self.next = None
def hasCycle(head: ListNode) -> bool:
	if not head or not head.next:
		return False
	slow = head
	fast = head.next
	while fast and fast.next:
		if slow == fast:
			return True
		_________________
return False

下列代码用于判断一个数是否为完全数(即等于它的真因子之和的数，如6=1+2+3)，哪个选项是正确的实现？

def isPerfectNumber(n: int) -> bool:
	if n <= 1:
		return False
	sum = 1
	i = 2
	while i * i <= n:
		if n % i == 0:
			sum += i
			_______________
				sum += n // i
		i += 1
	return sum == n

以下代码计算两个数的最大公约数(GCD)，横线上应填写（ ）。

def gcd(a: int, b: int) -> int:
	if a < b:
		a, b = b, a # 交换a和b的值
	while b != 0:
		temp = a % b
		a = b
		b = temp
	return _________

下面的代码实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入（ ）。

def sieve(n: int):
	is_prime = [True] * (n + 1)
	is_prime[0] = is_prime[1] = False
	for i in range(2, n + 1):
		if is_prime[i]:
			for j in range(______, n + 1, i):
				is_prime[j] = False
	return is_prime

下面的代码实现线性筛法(欧拉筛)，横线处应填入（ ）。

def linearSieve(n: int):
	is_prime = [True] * (n + 1)
	primes = []
	for i in range(2, n + 1):
		if is_prime[i]:
			primes.append(i)
		for p in primes:
			if p * i > n:
				break
			is_prime[p * i] = False
			if _____________:
				break
return primes

线性筛算法中有语句 if p * i > n: break ，其目的是（ ）。

唯一分解定理描述的是( )。

给定一个 n x n 的矩阵 matrix ，矩阵的每一行和每一列都按升序排列。下面代码返回矩阵中第 k 小的元素，则两处横线上应分别填写（ ）。

def countLE(matrix, x):
	n = len(matrix)
	i, j = n - 1, 0
	cnt = 0
	while i >= 0 and j < n:
		if matrix[i][j] <= x:
			cnt += i + 1
			j += 1
		else:
			i -= 1
	return cnt

def kthSmallest(matrix, k):
	n = len(matrix)
	lo = matrix[0][0]
	hi = matrix[n-1][n-1]
	while lo < hi:
		mid = lo + (hi - lo) // 2
		if countLE(matrix, mid) >= k:
			________
		else:
			________
	return lo

下述python代码实现了快速排序算法，下面说法错误的是（ ）。

def partition(arr, low, high):
	i, j = low, high
	while i < j:
		while i < j and arr[j] >= arr[low]:
			j -= 1
		while i < j and arr[i] <= arr[low]:
			i += 1
		arr[i], arr[j] = arr[j], arr[i]
	arr[i], arr[low] = arr[low], arr[i]
	return i

def quickSort(arr, low, high):
	if low < high:
		pivot = partition(arr, low, high)
		quickSort(arr, low, pivot - 1)
		quickSort(arr, pivot + 1, high)

下述python代码实现了归并排序算法，则横线上应填写（ ）。

def merge(nums, left, mid, right):
	tmp = []
	i, j = left, mid + 1
	while i <= mid and j <= right:
		if nums[i] <= nums[j]:
			tmp.append(nums[i])
			i += 1
		else:
			tmp.append(nums[j])
			j += 1
	while i <= mid:
		tmp.append(nums[i])
		i += 1
	while ___________:
		tmp.append(nums[j])
		j += 1
	for k in range(len(tmp)):
		nums[left + k] = tmp[k]

def mergeSort(nums, left, right):
	if left >= right:
		return
	mid = (left + right) // 2
	mergeSort(nums, left, mid)
	mergeSort(nums, mid + 1, right)
	merge(nums, left, mid, right)

# 使用示例
if __name__ == "__main__":
	nums = [3, 1, 4, 1, 5, 9, 2, 6]
	mergeSort(nums, 0, len(nums) - 1)
	print(nums) # 输出排序后的数组

假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 movies ，其中 movies[i] =[start_i, end_i] 表示第 i 部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影，则横线上应分别填写的代码为（ ）。

def maxMovies(movies):
	if not movies:
		return 0
	# 按照结束时间排序
	movies.sort(key=lambda x: x[1])
	count = 1
	_____________ = movies[0][1]
	for i in range(1, len(movies)):
		if movies[i][0] >= lastEnd:
			count += 1
			lastEnd = movies[i][1]
	return count

给定一个整数数组 nums ，下面代码找到一个具有最大和的连续子数组，并返回其最大和。则下面说法错误的是（ ）。

import math
def crossSum(nums, left, mid, right):
	leftSum = -math.inf
	sum_val = 0
	for i in range(mid, left - 1, -1):
		sum_val += nums[i]
		leftSum = max(leftSum, sum_val)
	rightSum = -math.inf
	sum_val = 0
	for i in range(mid + 1, right + 1):
		sum_val += nums[i]
		rightSum = max(rightSum, sum_val)
	return leftSum + rightSum

def helper(nums, left, right):
	if left == right:
		return nums[left]
	mid = left + (right - left) // 2
	leftMax = helper(nums, left, mid)
	rightMax = helper(nums, mid + 1, right)
	crossMax = crossSum(nums, left, mid, right)
	return max(leftMax, rightMax, crossMax)

def maxSubArray(nums):
	return helper(nums, 0, len(nums) - 1)

给定一个由非负整数组成的数组 digits ，表示一个非负整数的各位数字（最高位在数组首位）。下面代码对该整数执行 +1 操作，并返回结果数组，则横线上应填写（ ）。

def plusOne(digits):
	for i in range(len(digits)-1, -1, -1):
		if digits[i] < 9:
			digits[i] += 1
			return digits
		digits[i] = 0
	_______________

基于下面定义的函数，通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果一个数能被9整除，则它的各位数字之和能被9整除。

def isDivisibleBy9(n):
	return n % 9 == 0
def isDigitSumDivisibleBy9(n):
	num_str = str(n)
	digit_sum = 0
	for c in num_str:
		digit_sum += int(c)
	return digit_sum % 9 == 0

假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 findMusicalPattern(4，6) 函数返回2。

import math
def findMusicalPattern(rhythm1, rhythm2):
	commonDivisor = math.gcd(rhythm1, rhythm2)
	patternLength = (rhythm1 * rhythm2) // commonDivisor

下面递归实现的斐波那契数列的时间复杂度为 O(2ⁿ)。

def fib_memo(n, memo):
	if n <= 1:
		return n
	if memo[n] != -1:
		return memo[n]
	memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
	return memo[n]
if __name__ == "__main__":
	n = 40
	memo = [-1] * 100
	result = fib_memo(n, memo)
	print(result)

链表通过更改指针实现高效的节点插入与删除，但节点访问效率低、占用内存较多，且对缓存利用不友好。

二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。

线性筛关键是“每个合数只会被最小质因子筛到一次”，因此为 O(n)。

快速排序和归并排序都是稳定的排序算法。

下面代码采用分治算法求解汉诺塔问题，时间复杂度为 O(n log n)。

def move(src, tar):
	pan = src.pop()
	tar.append(pan)
def dfs(n, src, buf, tar):
	if n == 1:
		move(src, tar)
		return
	dfs(n - 1, src, tar, buf)
	move(src, tar)
	dfs(n - 1, buf, src, tar)
def solveHanota(A, B, C):
	n = len(A)
	dfs(n, A, B, C)

所有递归算法都可以转换为迭代算法。

贪心算法总能得到全局最优解。