算法导论

编写函数 insertion_sort(arr)，实现对列表的插入排序（升序），返回排序后的列表。 插入排序的基本思想：将数组分为已排序和未排序两部分，每次从...

编写函数 insertion_sort_desc(arr)，实现插入排序按降序排列，返回排序后的列表。

编写函数 merge(left, right)，将两个已排序的列表合并为一个有序列表。 例如：merge([1, 3, 5], [2, 4, 6]) 返回 [...

编写函数 merge_sort(arr)，实现归并排序算法，返回排序后的列表。 归并排序采用分治思想：将数组分成两半，分别排序后合并。

编写函数 max_subarray_brute(arr)，使用暴力法找出数组中连续子数组的最大和。 返回最大和的值。 例如：[-2, 1, -3, 4, -...

编写函数 max_subarray(arr)，使用分治法找出数组中连续子数组的最大和。 分治策略：最大子数组要么在左半部分，要么在右半部分，要么跨越中点。

编写函数 kadane(arr)，使用Kadane算法（动态规划思想）找出最大子数组和。 Kadane算法：遍历数组，记录当前位置结尾的最大子数组和。

编写函数 matrix_multiply(A, B)，计算两个矩阵的乘积。 矩阵A为m×n，矩阵B为n×p，结果为m×p矩阵。 例如：[[1,2],[3,4...

编写函数 heapify(arr, n, i)，对数组arr中下标为i的节点执行堆化操作（大顶堆）。 n是堆的大小，假设i的子树已经是堆。

编写函数 heap_sort(arr)，实现堆排序算法，返回排序后的列表。 堆排序步骤：1.构建大顶堆 2.反复将堆顶元素与末尾交换并调整堆。

编写类 MaxHeap，实现最大堆优先队列，包含以下方法： - __init__(): 初始化空堆 - insert(val): 插入元素 - extract_...

编写函数 partition(arr, low, high)，对数组arr[low:high+1]进行分区操作。 选择arr[high]作为基准(pivot)...

编写函数 quick_sort(arr)，实现快速排序算法，返回排序后的列表。 快速排序：选择基准元素，分区后递归排序左右两部分。

编写函数 randomized_quick_sort(arr)，实现随机化快速排序。 在选择基准时随机选择一个元素，避免最坏情况。

编写函数 counting_sort(arr)，实现计数排序算法。 计数排序适用于元素范围较小的整数排序。统计每个元素出现的次数，然后按顺序输出。

编写函数 radix_sort(arr)，实现基数排序算法。 基数排序按位数从低到高，对每一位进行计数排序。

编写函数 randomized_select(arr, k)，在无序数组中找出第k小的元素（k从0开始）。 使用类似快速排序的分区思想，期望时间复杂度O(n)...

编写类 DoublyListNode，表示双向链表的节点。 包含属性：val（值）、prev（前驱指针）、next（后继指针）。

编写函数 insert_after(node, new_node)，在双向链表节点node之后插入新节点new_node。

编写函数 delete_node(node)，从双向链表中删除指定节点。 假设node不是唯一的节点。

编写类 HashTableChaining，使用链地址法解决冲突的哈希表。 实现方法： - __init__(size): 初始化指定大小的哈希表 - ins...

编写类 BSTNode，表示二叉搜索树的节点。 包含属性：val（值）、left（左子树）、right（右子树）。

编写函数 bst_insert(root, val)，向二叉搜索树中插入值val。 返回插入后的根节点。

编写函数 bst_search(root, val)，在二叉搜索树中查找值val。 存在返回True，不存在返回False。

编写函数 bst_inorder(root)，返回二叉搜索树中序遍历的结果列表。 中序遍历BST应该得到升序序列。

编写函数 cut_rod_recursive(prices, n)，使用递归求解钢条切割问题。 prices[i]表示长度为i的钢条价格，n为钢条总长度，返回...

编写函数 cut_rod_dp(prices, n)，使用动态规划求解钢条切割问题。 自底向上计算，避免重复计算。

编写函数 matrix_chain_order(p)，计算矩阵链乘法的最少标量乘法次数。 p是维度数组，矩阵Ai的维度为p[i-1]×p[i]。 返回最少乘法...

编写函数 lcs(text1, text2)，求两个字符串的最长公共子序列长度。 子序列可以不连续。

编写函数 lcs_string(text1, text2)，返回最长公共子序列本身（任意一个即可）。

编写函数 activity_selection(start, end)，选择最多的互不重叠活动。 start和end分别是活动开始和结束时间列表，返回可选活动...

编写函数 build_huffman_tree(freq)，构建哈夫曼树。 freq是字符频率字典，返回哈夫曼树的根节点。 节点类包含属性：char（字符，...

编写函数 get_huffman_codes(root)，从哈夫曼树生成编码表。 返回字典，键为字符，值为编码字符串（左为'0'，右为'1'）。

编写函数 binary_search(arr, target)，在有序数组中查找目标值。 找到返回索引，找不到返回-1。

编写函数 search_insert(arr, target)，在有序数组中查找目标值的插入位置。 若目标值存在返回索引，不存在返回应该插入的位置索引。