网络安全黑客技术练习题大全(35)
- 2026-11-03 03:09:13
题目41：最大子数组和
问题描述：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解题思路：动态规划（Kadane 算法）。维护当前子数组和 cur_sum 与全局最大和 max_sum。若 cur_sum < 0，则从当前元素重新开始累加。遍历过程中更新 max_sum。
Python代码示例：
1 2 3 4 5 6 def maxSubArray(nums): max_sum = cur_sum = nums[0] for num in nums[1:]: cur_sum = max(num, cur_sum + num) max_sum = max(max_sum, cur_sum) return max_sum
题目42：爬楼梯
问题描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？
解题思路：动态规划。第 n 阶的方法数等于第 n-1 阶和第 n-2 阶方法数之和。可以用两个变量滚动更新，优化空间。
Python代码示例：
1 2 3 4 5 6 7 def climbStairs(n): if n <= 2: return n first, second = 1, 2 for _ in range(3, n + 1): first, second = second, first + second return second
题目43：买卖股票的最佳时机
问题描述：给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出。设计一个算法来计算你所能获取的最大利润。
解题思路：一次遍历，维护当前最小价格和最大利润。每天计算如果今天卖出能获得的利润，并更新最大利润。
Python代码示例：
1 2 3 4 5 6 7 def maxProfit(prices): min_price = float('inf') max_profit = 0 for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit
题目44：有效的括号
问题描述：给定一个只包括 '('、')'、'{'、'}'、'['、']' 的字符串 s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。
解题思路：使用栈。遇到左括号就入栈，遇到右括号则检查栈顶是否为对应的左括号。最后栈为空则有效。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 def isValid(s): stack = [] mapping = {')': '(', '}': '{', ']': '['} for char in s: if char in mapping: top = stack.pop() if stack else '#' if mapping[char] != top: return False else: stack.append(char) return not stack
题目45：环形链表
问题描述：给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
解题思路：使用快慢指针。慢指针每次走一步，快指针每次走两步。如果存在环，快慢指针最终会相遇。
Python代码示例（假设 ListNode 类已定义）：
1 2 3 4 5 6 7 8 def hasCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False
题目46：两数相加
问题描述：给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
解题思路：模拟竖式加法。同时遍历两个链表，逐位相加并处理进位。若某个链表遍历完则视为 0，最后若还有进位则补一个新节点。
Python代码示例（假设 ListNode 类已定义）：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def addTwoNumbers(l1, l2): dummy = ListNode(0) cur = dummy carry = 0 while l1 or l2 or carry: x = l1.val if l1 else 0 y = l2.val if l2 else 0 total = x + y + carry carry = total // 10 cur.next = ListNode(total % 10) cur = cur.next if l1: l1 = l1.next if l2: l2 = l2.next return dummy.next
题目47：字符串中的第一个唯一字符
问题描述：给定一个字符串 s，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
解题思路：使用哈希表统计每个字符出现的次数，再遍历一次字符串，找到第一个计数为 1 的字符并返回其索引。
Python代码示例：
1 2 3 4 5 6 7 8 def firstUniqChar(s): count = {} for ch in s: count[ch] = count.get(ch, 0) + 1 for i, ch in enumerate(s): if count[ch] == 1: return i return -1
题目48：有效的字母异位词
问题描述：给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。字母异位词指由相同字母重排列形成的字符串，每个字符出现次数相同。
解题思路：使用哈希表统计 s 中每个字符的出现次数，再遍历 t 递减计数。若所有计数归零则返回 True。也可直接比较两个字符串排序后的结果。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 def isAnagram(s, t): if len(s) != len(t): return False count = {} for ch in s: count[ch] = count.get(ch, 0) + 1 for ch in t: if ch not in count or count[ch] == 0: return False count[ch] -= 1 return True
题目49：合并两个有序链表
问题描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：使用哑节点和双指针。比较两个链表当前节点的值，将较小者接到结果链表末尾，并移动对应指针。最后将未遍历完的链表直接接到末尾。
Python代码示例（假设 ListNode 类已定义）：
1 2 3 4 5 6 7 8 9 10 11 12 13 def mergeTwoLists(list1, list2): dummy = ListNode(0) cur = dummy while list1 and list2: if list1.val <= list2.val: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next cur = cur.next cur.next = list1 if list1 else list2 return dummy.next
题目50：二叉树的最大深度
问题描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
解题思路：递归。当前节点的最大深度等于左右子树最大深度的较大值加 1。也可以使用层序遍历（BFS）逐层计数。
Python代码示例（假设 TreeNode 类已定义）：
1 2 3 4 5 6 def maxDepth(root): if not root: return 0 left_depth = maxDepth(root.left) right_depth = maxDepth(root.right) return max(left_depth, right_depth) + 1
