2026年程序设计进阶Python语言算法题库

2026年程序设计进阶Python语言算法题库一、字符串处理题（共3题，每题10分）1.1检索特定字符序列的最长重复子串题目描述：给定一个非空字符串`s`，请编写函数返回其最长重复子串的长度。例如，输入`s="ababcabababc"`，输出应为`5`（对应子串`"ababc"`）。要求：时间复杂度不超过O(n²)，空间复杂度不超过O(n)。1.2词典序排列的字符串分组题目描述：给定一个字符串列表`words`，请按词典序对字符串进行分组，使得同一组内的字符串可以通过删除零个或多个字符得到另一个组内字符串。例如，输入`words=["abc","ab","ac","bd"]`，输出应为`[["abc","ab","ac"],["bd"]]`。要求：实现时间复杂度为O(nlogn)，空间复杂度不超过O(n)。1.3字符串加密与解密题目描述：设计一个加密函数`encrypt(s)`，将字符串`s`按以下规则加密：将每个字符按ASCII码值右移3位（超过127的按模128处理），然后反转字符串。解密函数`decrypt(s)`需实现逆向操作。例如，`encrypt("hello")`输出`"khoor"`。要求：编写完整的加密和解密函数，并测试其正确性。二、数组与矩阵运算题（共4题，每题10分）2.1矩阵螺旋遍历题目描述：给定一个`mxn`的矩阵，请按螺旋顺序返回其元素。例如，输入`matrix=[[1,2,3],[4,5,6],[7,8,9]]`，输出应为`[1,2,3,6,9,8,7,4,5]`。要求：不使用额外空间，原地修改矩阵。2.2最长递增子序列（LIS）题目描述：给定一个整数数组`nums`，请返回其最长递增子序列的长度。例如，输入`nums=[10,9,2,5,3,7,101,18]`，输出`4`（对应子序列`[2,5,7,101]`）。要求：时间复杂度为O(nlogn)，空间复杂度不超过O(n)。2.3矩阵中的“蛇形”路径求和题目描述：给定一个`mxn`矩阵，蛇形路径从左上角开始，第一行从左到右，第二行从右到左，以此类推。请返回蛇形路径的路径和。例如，输入`matrix=[[1,2,3],[4,5,6],[7,8,9]]`，输出`25`（路径为`1+2+3+6+5+4+7+8+9`）。要求：实现时间复杂度为O(mn)，空间复杂度不超过O(1)。2.4移除数组中的重复项题目描述：给定一个整数数组`nums`，请原地移除所有重复项，并返回新数组的长度。例如，输入`nums=[0,0,1,1,1,2,2,3,3,4]`，输出`5`（新数组前5个元素为`[0,1,2,3,4]`）。要求：不使用额外空间，时间复杂度为O(n)。三、动态规划题（共3题，每题10分）3.1最长公共子序列（LCS）题目描述：给定两个字符串`s1`和`s2`，请返回它们的最长公共子序列的长度。例如，输入`s1="abcde"`,`s2="ace"`，输出`3`（子序列`"ace"`）。要求：使用动态规划实现，时间复杂度为O(mn)，空间复杂度不超过O(mn)。3.2零钱兑换题目描述：给定一个整数数组`coins`（表示面值）和一个总金额`amount`，请返回凑出总金额的最少硬币数量。例如，输入`coins=[1,2,5]`,`amount=11`，输出`3`（组合为`5+5+1`）。要求：使用动态规划实现，时间复杂度为O(amountcoins.length)，空间复杂度不超过O(amount)。3.3斐波那契数列的非递归实现题目描述：请编写函数`fib(n)`，返回斐波那契数列的第`n`项（从0开始）。例如，`fib(4)`输出`3`（序列为`0,1,1,2,3`）。要求：使用动态规划或迭代实现，时间复杂度为O(n)，空间复杂度不超过O(1)。四、树与图算法题（共3题，每题10分）4.1二叉树的层序遍历题目描述：给定一个二叉树，请返回其层序遍历的结果。例如，输入`[3,9,20,null,null,15,7]`（对应二叉树），输出`[[3],[9,20],[15,7]]`。要求：使用队列实现，时间复杂度为O(n)，空间复杂度不超过O(n)。4.2二叉树的最大深度题目描述：给定一个二叉树，请返回其最大深度。例如，输入`[3,9,20,null,null,15,7]`，输出`3`。要求：使用递归或迭代实现，时间复杂度为O(n)，空间复杂度不超过O(n)。4.3图的连通分量计数题目描述：给定一个无向图（邻接矩阵表示），请返回其连通分量的数量。例如，输入`graph=[[1,1,0],[1,1,0],[0,0,1]]`，输出`2`。要求：使用深度优先搜索（DFS）或广度优先搜索（BFS）实现，时间复杂度为O(V+E)，空间复杂度不超过O(V)。五、高级算法题（共3题，每题10分）5.1K个最近点题目描述：给定一个二维点列表`points`和一个整数`K`，请返回距离原点（0,0）最近的`K`个点。例如，输入`points=[[1,3],[-2,2]]`,`K=1`，输出`[[-2,2]]`。要求：使用快速选择算法（Quickselect）实现，平均时间复杂度为O(n)。5.2字符串的子集生成题目描述：给定一个不含重复字符的字符串`s`，请返回其所有可能的不重复子集。例如，输入`s="abc"`，输出`["","a","b","c","ab","ac","bc","abc"]`。要求：使用回溯算法实现，时间复杂度为O(2^n)，空间复杂度不超过O(n)。5.3爬楼梯的最少步数题目描述：给定一个楼梯，每次可以爬1或2步，请返回爬到`n`阶的最少步数。例如，`n=4`，输出`2`（步数组合为`1+1`或`2+2`）。要求：使用动态规划或数学公式实现，时间复杂度为O(n)，空间复杂度不超过O(1)。答案与解析1.1检索特定字符序列的最长重复子串答案：pythondeflongest_repeating_substring(s):n=len(s)dp=[[0]nfor_inrange(n)]max_len=0foriinrange(n):forjinrange(i+1,n):ifs[i]==s[j]:dp[i][j]=dp[i+1][j-1]+1ifi+1<j-1else1max_len=max(max_len,dp[i][j])returnmax_len示例print(longest_repeating_substring("ababcabababc"))#输出:5解析：使用动态规划，`dp[i][j]`表示以`s[i]`和`s[j]`结尾的最长重复子串长度。若`s[i]==s[j]`，则`dp[i][j]=dp[i+1][j-1]+1`，否则为`1`。最终最大值即为答案。1.2词典序排列的字符串分组答案：pythonfromcollectionsimportdefaultdictdefgroup_anagrams(words):groups=defaultdict(list)forwordinwords:sorted_word=''.join(sorted(word))groups[sorted_word].append(word)returnlist(groups.values())示例print(group_anagrams(["abc","ab","ac","bd"]))#输出:[["abc","ab","ac"],["bd"]]解析：对每个字符串排序，相同排序的字符串属于同一组。使用哈希表记录分组，时间复杂度为O(nlogn)。1.3字符串加密与解密答案：pythondefencrypt(s):return''.join(chr((ord(c)-128+3)%128)forcins[::-1])defdecrypt(s):return''.join(chr((ord(c)-3+128)%128)forcins[::-1])示例print(encrypt("hello"))#输出:"khoor"print(decrypt("khoor"))#输出:"hello"解析：右移3位相当于`ord(c)-128+3`，反转后解密时逆向操作。模128处理避免ASCII码溢出。2.1矩阵螺旋遍历答案：pythondefspiral_order(matrix):ifnotmatrix:return[]m,n=len(matrix),len(matrix[0])left,right,top,bottom=0,n-1,0,m-1res=[]whileleft<=rightandtop<=bottom:forjinrange(left,right+1):res.append(matrix[top][j])foriinrange(top+1,bottom+1):res.append(matrix[i][right])iftop<bottomandleft<right:forjinrange(right-1,left-1,-1):res.append(matrix[bottom][j])foriinrange(bottom-1,top,-1):res.append(matrix[i][left])left,right,top,bottom=left+1,right-1,top+1,bottom-1returnres示例print(spiral_order([[1,2,3],[4,5,6],[7,8,9]]))#输出:[1,2,3,6,9,8,7,4,5]解析：使用四个指针控制遍历边界，按左-右-下-上的顺序遍历，逐步缩小边界。2.2最长递增子序列（LIS）答案：pythondeflength_of_LIS(nums):ifnotnums:return0tails=[]fornuminnums:left,right=0,len(tails)whileleft<right:mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midifleft==len(tails):tails.append(num)else:tails[left]=numreturnlen(tails)示例print(length_of_LIS([10,9,2,5,3,7,101,18]))#输出:4解析：使用二分查找维护tails数组，`tails[i]`表示长度为`i+1`的最小末尾值。时间复杂度为O(nlogn)。2.3矩阵中的“蛇形”路径求和答案：pythondefsnake_matrix_sum(matrix):ifnotmatrix:return0m,n=len(matrix),len(matrix[0])res=0foriinrange(m):ifi%2==0:forjinrange(n):res+=matrix[i][j]else:forjinrange(n-1,-1,-1):res+=matrix[i][j]returnres示例print(snake_matrix_sum([[1,2,3],[4,5,6],[7,8,9]]))#输出:25解析：按行交替遍历方向，偶数行从左到右，奇数行从右到左。2.4移除数组中的重复项答案：pythondefremove_duplicates(nums):ifnotnums:return0i=0forjinrange(1,len(nums)):ifnums[j]!=nums[i]:i+=1nums[i]=nums[j]returni+1示例nums=[0,0,1,1,1,2,2,3,3,4]print(remove_duplicates(nums))#输出:5print(nums[:5])#输出:[0,1,2,3,4]解析：双指针法，`i`指向当前不重复元素的末尾，`j`遍历数组。3.1最长公共子序列（LCS）答案：pythondeflongest_common_subsequence(s1,s2):m,n=len(s1),len(s2)dp=[[0](n+1)for_inrange(m+1)]foriinrange(m):forjinrange(n):ifs1[i]==s2[j]:dp[i+1][j+1]=dp[i][j]+1else:dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])returndp[m][n]示例print(longest_common_subsequence("abcde","ace"))#输出:3解析：动态规划，`dp[i][j]`表示`s1[:i]`和`s2[:j]`的LCS长度。3.2零钱兑换答案：pythondefcoin_change(coins,amount):dp=[float('inf')](amount+1)dp[0]=0forcoinincoins:forxinrange(coin,amount+1):dp[x]=min(dp[x],dp[x-coin]+1)returndp[amount]ifdp[amount]!=float('inf')else-1示例print(coin_change([1,2,5],11))#输出:3解析：动态规划，`dp[x]`表示凑出`x`的最少硬币数。遍历所有硬币更新`dp`数组。3.3斐波那契数列的非递归实现答案：pythondeffib(n):ifn==0:return0a,b=0,1for_inrange(2,n+1):a,b=b,a+breturnb示例print(fib(4))#输出:3解析：迭代计算，使用两个变量存储前两个值，避免递归栈溢出。4.1二叉树的层序遍历答案：pythonfromcollectionsimportdequedeflevel_order(root):ifnotroot:return[]res,queue=[],deque([root])whilequeue:level=[]for_inrange(len(queue)):node=queue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnres示例输入为[3,9,20,null,null,15,7]，手动构建树classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightroot=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20)root.right.left=TreeNode(15)root.right.right=TreeNode(7)print(level_order(root))#输出:[[3],[9,20],[15,7]]解析：使用队列实现BFS，按层遍历二叉树。4.2二叉树的最大深度答案：pythondefmax_depth(root):ifnotroot:return0return1+max(max_depth(root.left),max_depth(root.right))示例同4.1print(max_depth(root))#输出:3解析：递归计算左右子树的最大深度，加1为当前节点深度。4.3图的连通分量计数答案：pythondefcount_components(n,graph):visited=[False]ndefdfs(node):stack=[node]whilestack:u=stack.pop()forvingraph[u]:ifnotvisited[v]:visited[v]=Truestack.append(v)res=0foriinrange(n):ifnotvisited[i]:visited[i]=Truedfs(i)res+=1returnres示例graph=[[1,1,0],[1,1,0],[0,0,1]]print(count_components(3