算法

Hailin

蓝桥杯 正则问题

题目描述考虑一种简单的正则表达式：只由 x ( ) | 组成的正则表达式。求这个正则表达式能接受的最长字符串的长度。例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是 xxxxxx，长度是 6。输入：一个由 x ( ) | 组成的正则表达式，长度不超过 100，保证合法。输出：能接受的最长字符串的长度。解题方法：栈模拟核心思路是用栈来模拟正则表达式的求值过程。正则中的 | 表示"

算法

Hailin

取球博弈

题目描述两个人玩取球游戏。一共有 N 个球，每人轮流取球，每次可取集合 {n1, n2, n3} 中的任意数目。如果无法继续取球，则游戏结束。此时，持有奇数个球的一方获胜。如果两人都是奇数，则为平局。双方都采用最优策略，判断先手是否能赢。解题思路博弈 + 记忆化搜索，状态定义很关键。游戏涉及三个维度：剩余球数 num当前玩家持有的球数奇偶性 x1对方持有的球数奇偶性 x2轮到谁 i（先手/后手）用

算法

Hailin

蓝桥杯 蓝桥国王

题目描述蓝桥王国中有 N 个城市，编号从 1 到 N，王国首都是 1 号城市。国王需要知道从首都到每个城市的最短距离。给定 M 条有向道路，每条道路连接两个城市 u 和 v，长度为 w。如果某个城市从首都不可达，则输出 -1。解题方法：Dijkstra 堆优化标准的单源最短路问题，所有边权非负，直接使用 Dijkstra 堆优化求解。从起点（首都）出发，用优先队列不断松弛邻边，最终得到所有节点的最

算法

Hailin

Dijkstra 堆优化版

题目描述给定一个有向带权图，求从起点到所有其他节点的最短路径长度。图中可能存在重边和自环，边权为正数。Dijkstra 算法适用于所有边权非负的图。堆优化版本通过优先队列（最小堆）快速取出当前距离最小的未确定节点，将时间复杂度从 O(V²) 优化到 O((V + E)log V)。解题方法：Dijkstra + 堆优化算法思路维护一个距离数组 dist，初始时起点距离为 0，其余为无穷大。用最小堆

算法

Hailin

KMP 算法

题目描述给定一个文本串 s 和一个模式串 p，在 s 中查找 p 第一次出现的位置。如果不存在则返回 -1。暴力匹配的时间复杂度为 O(m × n)，而 KMP 算法通过预处理模式串的"前后缀信息"，将匹配过程优化到 O(m + n)，核心思想是匹配失败时利用已知信息跳过不必要的比较。解题方法：KMP（Knuth-Morris-Pratt）KMP 算法的关键在于 next 数组（也称前缀函数）。它