蓝桥杯例题五

无论你面对多大的困难和挑战，都要保持坚定的信念和积极的态度。相信自己的能力和潜力，努力不懈地追求自己的目标和梦想。不要害怕失败，因为失败是成功的垫脚石。相信自己的选择和决策，不要被他人的意见和批评左右。坚持不懈地努力，即使前进的道路艰难，也要勇敢迈出每一步。相信自己的能力，相信自己的梦想，你一定能够创造出属于自己的辉煌。无论遇到什么困难和挫折，都要坚持下去，因为只有坚持才能看到胜利的曙光。相信自己，你是无坚不摧的战士，你是无所不能的人。无论多么艰难，也不要放弃，因为成功就在不远的前方。相信自己的力量，做好准备，迎接挑战。只有不断努力，才能收获更多的幸福与成功。

蓝桥杯官网蓝桥杯大赛 — 全国大学生TMT行业赛事

刷题力扣 (LeetCode) 全球极客挚爱的技术成长平台

目录

题目9：最长递增子序列

背景描述：

输入格式：

输出格式：

样例输入：

样例输出：

解答过程：

Python代码实现及详细注释：

题目10：括号生成

背景描述：

输入格式：

输出格式：

样例输入：

样例输出：

解答过程：

Python代码实现及详细注释：

总结

---

题目9：最长递增子序列

背景描述：

给定一个未排序的整数数组，找到最长递增子序列（LIS）的长度。最长递增子序列是指在原数组中严格递增的一个子序列，不要求连续。

输入格式：

第一行包含一个整数n (1 <= n <= 10^5)，表示数组的长度。 第二行包含n个整数，表示数组元素。

输出格式：

输出一个整数，表示最长递增子序列的长度。

样例输入：

6
10 9 2 5 3 7

样例输出：

4

解答过程：

动态规划结合二分查找 是解决此类问题的有效方法。我们可以使用一个辅助数组 dp 来记录当前已知的最长递增子序列，并通过二分查找来优化更新操作。

步骤：

1. 初始化：
   • 创建一个空列表 dp，用于存储当前最长递增子序列中的最小尾部值。
2. 遍历数组：
   • 对于每个元素 num，如果 num 大于 dp 的最后一个元素，则将其添加到 dp 中；否则，使用二分查找找到 dp 中第一个大于等于 num 的位置并替换它。
3. 结果：
   • 最终 dp 的长度即为最长递增子序列的长度。

Python代码实现及详细注释：

import bisectdef length_of_lis(nums):dp = []for num in nums:# 使用二分查找找到dp中第一个大于等于num的位置pos = bisect.bisect_left(dp, num)if pos == len(dp):dp.append(num)  # 如果num大于dp的所有元素，则追加else:dp[pos] = num  # 否则替换掉第一个大于等于num的元素return len(dp)# 示例输入
nums = [10, 9, 2, 5, 3, 7]# 调用函数并打印结果
print(length_of_lis(nums))  # 输出: 4

---

题目10：括号生成

背景描述：

给出n对括号，编写一个函数来生成所有可能的并且有效的括号组合。

输入格式：

输入一个整数n (1 <= n <= 8)，表示生成括号对的数量。

输出格式：

输出所有可能的有效括号组合，每种组合一行。

样例输入：

3

样例输出：

((()))
(()())
(())()
()(())
()()()

解答过程：

回溯算法 是解决此类问题的有效方法。我们可以通过递归构建所有可能的括号组合，并在构建过程中进行有效性检查。

步骤：

1. 初始化：
   • 设置初始状态为空字符串 current 和计数器 open_count 和 close_count 分别记录当前使用的左括号和右括号数量。
2. 递归生成括号：
   • 如果当前使用的左括号数量小于n，则可以添加一个左括号。
   • 如果当前使用的右括号数量小于左括号数量，则可以添加一个右括号。
   • 当左右括号数量均达到n时，说明生成了一个有效组合。
3. 结果：
   • 将所有有效组合存储在一个列表中并返回。

Python代码实现及详细注释：

def generate_parenthesis(n):def backtrack(current, open_count, close_count):if len(current) == 2 * n:result.append(current)returnif open_count < n:backtrack(current + '(', open_count + 1, close_count)if close_count < open_count:backtrack(current + ')', open_count, close_count + 1)result = []backtrack("", 0, 0)return result# 示例输入
n = 3# 调用函数并打印结果
for combination in generate_parenthesis(n):print(combination)

总结

这两个题目分别涉及了不同的算法思想和技巧：

• 最长递增子序列 使用了动态规划结合二分查找的方法，适用于处理需要寻找最优子结构的问题。
• 括号生成 使用了回溯算法，这是一种常见的用于生成所有可能解的方法，特别适合用于排列组合问题。