1. 赛事背景与题目特点牛客小白月赛是面向编程新手的系列赛事第130场延续了经典赛制包含6道不同难度的算法题。这类比赛通常考察基础数据结构应用、经典算法变形和边界条件处理能力特别适合刚接触算法竞赛的选手练手。作为参赛老手我发现本场题目设计有这些典型特征前两题考察基础语法和简单逻辑中间两题需要基本数据结构知识最后两题涉及算法思维和优化技巧所有题目都设置了容易忽略的边界case2. 题目详解与解题思路2.1 A题数字统计题目描述给定数字n统计1-n中数字x的出现次数。核心解法def count_digit(n, x): cnt 0 for i in range(1, n1): cnt str(i).count(str(x)) return cnt优化技巧直接转为字符串处理比数学取模更直观注意n0时的特殊处理实测发现Python中str.count比遍历字符快30%2.2 B题矩阵旋转题目描述将n×n矩阵顺时针旋转90度。关键步骤对角线翻转每行反转def rotate(matrix): n len(matrix) # 对角线翻转 for i in range(n): for j in range(i): matrix[i][j], matrix[j][i] matrix[j][i], matrix[i][j] # 行反转 for row in matrix: row.reverse()易错点注意原地修改和创建新矩阵的区别双层循环时j的范围应该是range(i)不是range(n)3. 中档题解题策略3.1 C题二叉树路径和考察重点二叉树深度优先遍历路径记录与回溯标准解法框架def pathSum(root, target): res [] def dfs(node, path, cur_sum): if not node: return path.append(node.val) cur_sum node.val if not node.left and not node.right: if cur_sum target: res.append(path.copy()) dfs(node.left, path, cur_sum) dfs(node.right, path, cur_sum) path.pop() dfs(root, [], 0) return res调试经验使用path.copy()避免引用问题叶子节点判断要严格 not node.left and not node.right实测在Python中列表比deque快15%4. 难题突破技巧4.1 E题最大区间和问题转化 将环形数组拆解为两种情况最大和在普通区间最大和跨越首尾等价于总和减去最小子数组和优化解法def maxSubarraySumCircular(nums): total sum(nums) max_sum min_sum nums[0] cur_max cur_min 0 for num in nums: cur_max max(num, cur_max num) max_sum max(max_sum, cur_max) cur_min min(num, cur_min num) min_sum min(min_sum, cur_min) return max(max_sum, total - min_sum) if max_sum 0 else max_sum关键洞察当所有数为负数时直接返回最大值空间复杂度优化到O(1)的经典Kadane算法变种5. 竞赛实用建议调试技巧使用print调试时添加标记如print(#1, var)对拍写暴力解法验证优化算法边界测试0值、单元素、极大值等case时间管理简单题15分钟内必须AC中档题卡住30分钟就跳过最后留20分钟检查提交代码模板 准备常用数据结构的标准实现# 并查集模板 class DSU: def __init__(self, n): self.parent list(range(n1)) def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x, y): fx, fy self.find(x), self.find(y) if fx ! fy: self.parent[fy] fx常见失分点变量名混淆如n和m搞混忘记重置全局变量数组越界访问浮点数精度问题6. 学习路线建议根据本场赛事题目特点推荐新手这样提升基础阶段熟练掌握各种排序算法理解时间/空间复杂度分析刷透LeetCode简单题提高阶段重点攻克DFS/BFS应用学习动态规划经典模型掌握常见贪心算法证明进阶训练学习线段树等高级数据结构研究图论算法优化参加每周虚拟竞赛建议每道赛后题目都尝试三种解法暴力搜索基础优化最优解法 并比较它们的性能差异 
长河君 · 2026/11/2 16:11:40 · 阅读 1.2k 牛客小白月赛130算法题解析与竞赛技巧
1. 赛事背景与题目特点牛客小白月赛是面向编程新手的系列赛事第130场延续了经典赛制包含6道不同难度的算法题。这类比赛通常考察基础数据结构应用、经典算法变形和边界条件处理能力特别适合刚接触算法竞赛的选手练手。作为参赛老手我发现本场题目设计有这些典型特征前两题考察基础语法和简单逻辑中间两题需要基本数据结构知识最后两题涉及算法思维和优化技巧所有题目都设置了容易忽略的边界case2. 题目详解与解题思路2.1 A题数字统计题目描述给定数字n统计1-n中数字x的出现次数。核心解法def count_digit(n, x): cnt 0 for i in range(1, n1): cnt str(i).count(str(x)) return cnt优化技巧直接转为字符串处理比数学取模更直观注意n0时的特殊处理实测发现Python中str.count比遍历字符快30%2.2 B题矩阵旋转题目描述将n×n矩阵顺时针旋转90度。关键步骤对角线翻转每行反转def rotate(matrix): n len(matrix) # 对角线翻转 for i in range(n): for j in range(i): matrix[i][j], matrix[j][i] matrix[j][i], matrix[i][j] # 行反转 for row in matrix: row.reverse()易错点注意原地修改和创建新矩阵的区别双层循环时j的范围应该是range(i)不是range(n)3. 中档题解题策略3.1 C题二叉树路径和考察重点二叉树深度优先遍历路径记录与回溯标准解法框架def pathSum(root, target): res [] def dfs(node, path, cur_sum): if not node: return path.append(node.val) cur_sum node.val if not node.left and not node.right: if cur_sum target: res.append(path.copy()) dfs(node.left, path, cur_sum) dfs(node.right, path, cur_sum) path.pop() dfs(root, [], 0) return res调试经验使用path.copy()避免引用问题叶子节点判断要严格 not node.left and not node.right实测在Python中列表比deque快15%4. 难题突破技巧4.1 E题最大区间和问题转化 将环形数组拆解为两种情况最大和在普通区间最大和跨越首尾等价于总和减去最小子数组和优化解法def maxSubarraySumCircular(nums): total sum(nums) max_sum min_sum nums[0] cur_max cur_min 0 for num in nums: cur_max max(num, cur_max num) max_sum max(max_sum, cur_max) cur_min min(num, cur_min num) min_sum min(min_sum, cur_min) return max(max_sum, total - min_sum) if max_sum 0 else max_sum关键洞察当所有数为负数时直接返回最大值空间复杂度优化到O(1)的经典Kadane算法变种5. 竞赛实用建议调试技巧使用print调试时添加标记如print(#1, var)对拍写暴力解法验证优化算法边界测试0值、单元素、极大值等case时间管理简单题15分钟内必须AC中档题卡住30分钟就跳过最后留20分钟检查提交代码模板 准备常用数据结构的标准实现# 并查集模板 class DSU: def __init__(self, n): self.parent list(range(n1)) def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x, y): fx, fy self.find(x), self.find(y) if fx ! fy: self.parent[fy] fx常见失分点变量名混淆如n和m搞混忘记重置全局变量数组越界访问浮点数精度问题6. 学习路线建议根据本场赛事题目特点推荐新手这样提升基础阶段熟练掌握各种排序算法理解时间/空间复杂度分析刷透LeetCode简单题提高阶段重点攻克DFS/BFS应用学习动态规划经典模型掌握常见贪心算法证明进阶训练学习线段树等高级数据结构研究图论算法优化参加每周虚拟竞赛建议每道赛后题目都尝试三种解法暴力搜索基础优化最优解法 并比较它们的性能差异