蓝桥杯例题五

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

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

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

题目9：最长递增子序列

背景描述：

输入格式：

输出格式：

样例输入：

样例输出：

解答过程：

Python代码实现及详细注释：

题目10：括号生成

背景描述：

输入格式：

输出格式：

样例输入：

样例输出：

解答过程：

Python代码实现及详细注释：

总结

题目9：最长递增子序列

背景描述：

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

输入格式：

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

输出格式：

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

样例输入：

6
10 9 2 5 3 7

样例输出：

解答过程：

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

步骤：

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

Python代码实现及详细注释：

import bisect

def 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)，表示生成括号对的数量。

输出格式：

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

样例输入：

样例输出：

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

解答过程：

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

步骤：

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

Python代码实现及详细注释：

def generate_parenthesis(n):
    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return
        
        if 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)