当前位置：首页 > article >正文

蓝桥杯例题二

article 2025/3/1 15:34:22

不管前方是否有艰难险阻，也不管生活是否给予了你重重困扰，要相信自己的力量，相信自己的坚强和勇气。成功的路上充满了挑战和困难，但正是这些困难使我们变得更加坚定和成熟。无论何时何地，都不要放弃自己的梦想和追求，因为只有坚持不懈的努力，才能实现自己的目标。每一次的跌倒都是一次宝贵的经验，每一次的失败都是一次重要的教训。只要不断学习和成长，就没有什么是无法克服的。在追逐梦想的路上要坚持积极向前，抱着乐观的心态面对一切困难和挑战。相信自己的能力和潜力，勇敢迎接未知的风险，努力拼搏，相信总会有一个美好的明天等待着你。无论遇到多少艰难困苦，只要心中燃起希望的火花，就一定能够战胜一切困难，迎接美好的未来。

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

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

题目3：数字三角形的最大路径和

背景描述：

输入格式：

输出格式：

样例输入：

样例输出：

解答过程：

Python代码实现及详细注释：

题目4：回文子串计数

背景描述：

输入格式：

输出格式：

样例输入：

样例输出：

解答过程：

Python代码实现及详细注释：

进一步解释

数字三角形的最大路径和：

回文子串计数：

题目3：数字三角形的最大路径和

背景描述：

给定一个由整数组成的数字三角形，要求从顶部到底部找到一条路径，使得这条路径上的数字之和最大。每次只能移动到下一行中相邻的数字上（即左下方或右下方）。

输入格式：

第一行包含一个整数n (1 <= n <= 100)，表示数字三角形的行数。接下来n行，第i行包含i个整数，表示数字三角形的第i行元素。

输出格式：

输出一个整数，表示从顶到底的最大路径和。

样例输入：

样例输出：

解答过程：

动态规划（DP）算法 是解决此类问题的有效方法。我们使用自底向上的方法来构建一个二维数组 dp，其中 dp[i][j] 表示从位置 (i, j) 到达底部的最大路径和。

步骤：

初始化：
- 创建一个与输入相同大小的二维数组 dp。
- 将最后一行复制到 dp 的最后一行。
填充dp表：
- 从倒数第二行开始向上遍历，对于每个元素 dp[i][j]，它等于当前元素加上其下一行相邻元素中的较大值。
结果：
- 最终答案就是 dp[0][0]，即从顶部到底部的最大路径和。

Python代码实现及详细注释：

def max_path_sum(triangle):
    if not triangle:
        return 0
    
    # 初始化dp表，直接在triangle基础上操作以节省空间
    # 我们不需要额外的空间，因为可以从下往上更新
    for row in range(len(triangle) - 2, -1, -1):  # 从倒数第二行开始
        for col in range(len(triangle[row])):
            # 当前元素加上其下一行相邻元素中的较大值
            triangle[row][col] += max(triangle[row + 1][col], triangle[row + 1][col + 1])
    
    # 最终答案是dp表的第一个元素，即从顶到底的最大路径和
    return triangle[0][0]

# 示例输入
triangle_input = [
    [7],
    [3, 8],
    [8, 1, 0],
    [2, 7, 4, 4],
    [4, 5, 2, 6, 5]
]

# 调用函数并打印结果
print(max_path_sum(triangle_input))  # 输出: 30

题目4：回文子串计数

背景描述：

给定一个字符串，要求计算该字符串中所有不同长度的回文子串的数量。回文是指正读和反读都相同的字符串。

输入格式：

输入一行包含一个字符串s，仅包含小写字母，长度不超过1000。

输出格式：

输出一个整数，表示字符串中所有不同长度的回文子串的数量。

样例输入：

abc

样例输出：

解答过程：

中心扩展法 是一种高效的方法来查找所有可能的回文子串。对于每个字符（或两个相邻字符之间的空隙），我们可以尝试将其作为回文中心，并向外扩展直到不能再形成回文为止。

步骤：

遍历中心：
- 对于每一个字符位置以及每两个字符之间的空隙，尝试将其作为回文中心。
扩展：
- 如果左右两边字符相等，则继续向外扩展；否则停止。
计数：
- 每次成功扩展后，增加回文子串计数。

Python代码实现及详细注释：

def count_palindromic_substrings(s):
    def expand_around_center(left, right):
        """
        辅助函数，用于从给定的中心位置left和right向外扩展，
        并计算该中心能形成的回文子串数量。
        """
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            # 每找到一个回文子串就增加计数
            count += 1
            # 向外扩展
            left -= 1
            right += 1
        return count
    
    total_count = 0
    for i in range(len(s)):
        # 单个字符为中心的情况
        total_count += expand_around_center(i, i)
        # 两个字符之间为中心的情况
        total_count += expand_around_center(i, i + 1)
    
    return total_count

# 示例输入
s = "abc"

# 调用函数并打印结果
print(count_palindromic_substrings(s))  # 输出: 3

进一步解释

数字三角形的最大路径和：

优化空间复杂度： 在这个例子中，我们直接在原始的 triangle 上进行修改，从而避免了创建额外的 dp 表。这是因为我们在更新时只依赖于下一行的数据，因此可以直接覆盖旧值。
时间复杂度： O(n^2)，其中n是三角形的行数。这是因为我们需要遍历整个三角形两次，一次是填充dp表，另一次是从上往下计算最大路径和。

回文子串计数：

中心扩展法的优点： 这种方法的时间复杂度为O(n^2)，并且能够有效地处理所有长度的回文子串。通过考虑单个字符和字符间的空隙作为中心，确保不会遗漏任何可能的回文子串。
辅助函数的作用： expand_around_center 函数简化了主逻辑，使得代码更加清晰易读。它负责从指定的中心向外扩展，同时统计有效回文子串的数量。

这两个题目不仅涉及了动态规划和回文检查的经典算法，而且通过具体的例子展示了如何应用这些算法来解决问题。

查看全文

http://www.kler.cn/a/518996.html