2026年百度AI面试算法工程师编程题

2026年百度AI面试算法工程师编程题一、字符串处理（3题，每题10分，共30分）1.题目：给定一个字符串`s`，其中包含字母、数字和特殊字符，请编写一个函数，统计其中字母的数量（区分大小写）、数字的数量以及特殊字符的数量。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：-输入：`"aB3!cD4#"`-输出：`字母数量：5，数字数量：2，特殊字符数量：3`2.题目：给定两个字符串`s1`和`s2`，请编写一个函数，判断`s1`是否是`s2`的子串。如果`s1`是`s2`的子串，返回`True`；否则返回`False`。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：-输入：`s1="abc"`,`s2="aabbccabc"`-输出：`True`3.题目：给定一个字符串`s`，请编写一个函数，将字符串中的所有单词按字典序升序排列，并返回排序后的字符串。假设字符串中的单词由空格分隔，且单词之间只有一个空格。示例：-输入：`"bananaappleorange"`-输出：`"applebananaorange"`二、数组处理（3题，每题10分，共30分）1.题目：给定一个整数数组`nums`，请编写一个函数，找出数组中第三大的数，并返回该数。如果数组中不存在第三大的数，返回最大的数。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：-输入：`nums=[3,2,1,5,6,4]`-输出：`2`-输入：`nums=[1,2]`-输出：`2`2.题目：给定一个整数数组`nums`，请编写一个函数，将数组中的元素按奇偶性分开，使得所有奇数位于数组的前面，所有偶数位于数组的后面，并返回重新排列后的数组。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：-输入：`nums=[3,1,2,4]`-输出：`[3,1,4,2]`3.题目：给定一个整数数组`nums`，请编写一个函数，找出数组中和最大的连续子数组，并返回其和。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：-输入：`nums=[-2,1,-3,4,-1,2,1,-5,4]`-输出：`6`（子数组为`[4,-1,2,1]`）三、动态规划（3题，每题10分，共30分）1.题目：给定一个整数数组`nums`，其中包含正数和负数，请编写一个函数，找出数组中和最大的连续子数组，并返回其和。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：-输入：`nums=[-2,1,-3,4,-1,2,1,-5,4]`-输出：`6`（子数组为`[4,-1,2,1]`）2.题目：给定一个字符串`s`，请编写一个函数，判断`s`是否是一个有效的括号字符串，其中括号包括`()`、`[]`和`{}`。有效括号字符串满足所有括号均正确匹配且嵌套合理。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：-输入：`"()"`-输出：`True`-输入：`"()[]{}"`-输出：`True`-输入：`"(]"`-输出：`False`3.题目：给定一个整数`n`，请编写一个函数，计算`n`的阶乘。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：-输入：`n=5`-输出：`120`四、数据结构（3题，每题10分，共30分）1.题目：给定一个链表，请编写一个函数，反转该链表，并返回反转后的链表头节点。要求时间复杂度为O(n)，空间复杂度为O(1)。示例：-输入：`1->2->3->4->5`-输出：`5->4->3->2->1`2.题目：给定一个二叉树，请编写一个函数，判断该二叉树是否是平衡二叉树。平衡二叉树的定义是：对于任意节点，其左右子树的高度差不超过1。要求时间复杂度为O(n)，空间复杂度为O(h)（h为树的高度）。示例：-输入：3/\920\/\157-输出：`True`3.题目：给定一个无重复元素的整数数组`nums`，请编写一个函数，生成该数组的所有可能的组合，并返回所有组合的列表。组合中元素的顺序不重要，且每个组合中的元素不重复。要求时间复杂度为O(2^n)，空间复杂度为O(n)。示例：-输入：`nums=[1,2,3]`-输出：`[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]`答案与解析一、字符串处理1.答案：pythondefcount_characters(s):letters=0digits=0special=0forcharins:ifchar.isalpha():letters+=1elifchar.isdigit():digits+=1else:special+=1returnf"字母数量：{letters}，数字数量：{digits}，特殊字符数量：{special}"示例print(count_characters("aB3!cD4#"))#输出：字母数量：5，数字数量：2，特殊字符数量：3解析：-遍历字符串中的每个字符，使用`isalpha()`判断是否为字母，`isdigit()`判断是否为数字，其余为特殊字符。-时间复杂度为O(n)，空间复杂度为O(1)。2.答案：pythondefis_substring(s1,s2):ifnots1:returnTruelen1,len2=len(s1),len(s2)iflen1>len2:returnFalseforiinrange(len2-len1+1):ifs2[i:i+len1]==s1:returnTruereturnFalse示例print(is_substring("abc","aabbccabc"))#输出：True解析：-使用滑动窗口法，遍历`s2`，检查每个长度为`s1`的子串是否与`s1`相等。-时间复杂度为O(n)，空间复杂度为O(1)。3.答案：pythondefsort_words(s):words=s.split()words.sort()return''.join(words)示例print(sort_words("bananaappleorange"))#输出："applebananaorange"解析：-使用`split()`将字符串按空格分割成单词列表，然后使用`sort()`排序，最后使用`join()`连接成字符串。-时间复杂度为O(nlogn)，空间复杂度为O(n)。二、数组处理1.答案：pythondefthird_largest(nums):first=second=third=float('-inf')fornuminnums:ifnum>first:third=secondsecond=firstfirst=numeliffirst>num>second:third=secondsecond=numelifsecond>num>third:third=numreturnfirstifthird==float('-inf')elsethird示例print(third_largest([3,2,1,5,6,4]))#输出：2print(third_largest([1,2]))#输出：2解析：-使用三个变量`first`、`second`、`third`分别记录最大、第二大、第三大的数。-遍历数组，更新这三个变量。-时间复杂度为O(n)，空间复杂度为O(1)。2.答案：pythondefseparate_odd_even(nums):left,right=0,len(nums)-1whileleft<right:whileleft<rightandnums[left]%2!=0:left+=1whileleft<rightandnums[right]%2==0:right-=1ifleft<right:nums[left],nums[right]=nums[right],nums[left]returnnums示例print(separate_odd_even([3,1,2,4]))#输出：[3,1,4,2]解析：-使用双指针法，`left`从左向右移动，`right`从右向左移动。-当`left`指向偶数时，`right`向左移动，当`right`指向奇数时，`left`向右移动。-交换`left`和`right`指向的元素。-时间复杂度为O(n)，空间复杂度为O(1)。3.答案：pythondefmax_subarray_sum(nums):max_sum=current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum示例print(max_subarray_sum([-2,1,-3,4,-1,2,1,-5,4]))#输出：6解析：-使用Kadane算法，`current_sum`记录当前子数组的和，`max_sum`记录最大子数组的和。-遍历数组，更新`current_sum`和`max_sum`。-时间复杂度为O(n)，空间复杂度为O(1)。三、动态规划1.答案：pythondefmax_subarray_sum(nums):max_sum=current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum示例print(max_subarray_sum([-2,1,-3,4,-1,2,1,-5,4]))#输出：6解析：-使用Kadane算法，`current_sum`记录当前子数组的和，`max_sum`记录最大子数组的和。-遍历数组，更新`current_sum`和`max_sum`。-时间复杂度为O(n)，空间复杂度为O(1)。2.答案：pythondefis_valid_parentheses(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack示例print(is_valid_parentheses("()"))#输出：Trueprint(is_valid_parentheses("()[]{}"))#输出：Trueprint(is_valid_parentheses("(]"))#输出：False解析：-使用栈，遍历字符串，遇到右括号时，检查栈顶元素是否与当前右括号匹配。-时间复杂度为O(n)，空间复杂度为O(n)。3.答案：pythondeffactorial(n):ifn==0:return1result=1foriinrange(1,n+1):result=ireturnresult示例print(factorial(5))#输出：120解析：-使用循环计算阶乘，从1乘到n。-时间复杂度为O(n)，空间复杂度为O(1)。四、数据结构1.答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev示例defprint_list(head):current=headresult=[]whilecurrent:result.append(str(current.val))current=current.nextprint('->'.join(result))node1=ListNode(1)node2=ListNode(2)node3=ListNode(3)node4=ListNode(4)node5=ListNode(5)node1.next=node2node2.next=node3node3.next=node4node4.next=node5print_list(reverse_list(node1))#输出：5->4->3->2->1解析：-使用迭代法反转链表，遍历链表，每次将当前节点的`next`指向前一个节点。-时间复杂度为O(n)，空间复杂度为O(1)。2.答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)returnmax(left_height,right_height)+1,left_balancedandright_balancedandabs(left_height-right_height)<=1_,balanced=check(root)returnbalan