- 科学计算
【免费下载链接】codeforces-go
算法竞赛模板库 by 灵茶山艾府 💭💡🎈
本文以 leetcode/biweekly/104/a/README.md 为蓝本,完整讲解力扣双周赛 104 第一题(题目名 Number of Senior Citizens,老年市民计数)的解题思路、六种主流语言实现,并结合本仓库中的 Go 源码(a.go、a_test.go、a.txt)与 LeetCode 测试框架(leetcode/testutil/leetcode.go)做源码级剖析。读完本文,你将掌握"从定长字符串的固定偏移位置提取子串并做数值比较"这类签到题的通用解法,以及 Go 中利用 ASCII 编码特性用位运算替代字符减法的优化技巧。
题目背景与输入格式
details是一个字符串数组,其中每个字符串都是定长 15 位的乘客信息,字段布局固定如下:
| 下标区间 | 含义 |
|---|---|
| 0 ~ 9(10 个字符) | 电话号码 |
| 10 | 性别(M或F) |
| 11 ~ 12(2 个字符) | 年龄 |
| 13 ~ 14(2 个字符) | 座位号 |
题目要求统计年龄严格大于 60的乘客数量("senior citizen" 的定义是年龄大于 60 岁,恰好 60 岁不算)。
从仓库的测试数据文件 a.txt 可以看到题目样例的原始形态:
["7868190130M7522","5303914400F9211","9273338290F4010"] 2 ["1313579440F2036","2921522980M5644"] 0手动拆解第一个样例即可验证字段布局:"7868190130M7522"中7868190130为电话,M为性别,第 11、12 位是75(年龄 75 > 60,计入),22为座位号;"5303914400F9211"年龄为92(计入);"9273338290F4010"年龄为40(不计入),合计答案为 2。第二个样例中两位乘客年龄分别为20和56,均不超过 60,答案为 0。
核心解题思路
由于字符串定长且字段位置固定,最直接的做法是:遍历每个字符串s,取出第 11 和第 12 位字符组成的两位数,判断它是否大于 60。若大于 60,答案加一。
这一思路的时间复杂度为 O(n),其中 n 为details的长度;空间复杂度为 O(1),只用了常数个额外变量,无需借助任何额外数据结构。
六种语言实现
以下是原文档给出的全部实现,可直接复制使用。
Python3
利用切片s[11:13]一步取出两位数,再与 60 比较:
class Solution: def countSeniors(self, details: List[str]) -> int: return sum(int(s[11:13]) > 60 for s in details)int(s[11:13])将两个字符的切片直接解析为整数,布尔值在sum中自动按 1/0 累加。
Java
由于 Java 字符串不支持切片,改用charAt取单个字符,并通过- '0'将字符转为数字:
class Solution { public int countSeniors(String[] details) { int ans = 0; for (String s : details) if ((s.charAt(11) - '0') * 10 + s.charAt(12) - '0' > 60) ans++; return ans; } }注意这里必须用括号包裹(s.charAt(11) - '0'),因为 Java 中*的优先级高于-,若不括起来会先计算'0' * 10,结果将完全错误。
C++
与 Java 思路一致,std::string支持下标随机访问,直接用s[11] - '0':
class Solution { public: int countSeniors(vector<string> &details) { int ans = 0; for (auto &s: details) ans += (s[11] - '0') * 10 + s[12] - '0' > 60; return ans; } };C++ 中bool可以隐式转换为int,因此(s[11] - '0') * 10 + s[12] - '0' > 60这个布尔表达式的真假会直接作为 1 或 0 累加到ans中。
Go(仓库源码)
仓库中的正式实现位于 a.go,它没有使用- '0',而是用了一个更巧妙的位运算:
func countSeniors(details []string) (ans int) { for _, s := range details { // 对于数字字符,&15 等价于 -'0',但是不需要加括号 if s[11]&15*10+s[12]&15 > 60 { ans++ } } return }这段代码的细节将在下一节单独展开。
JavaScript
利用parseInt直接解析子串为十进制数:
var countSeniors = function(details) { let ans = 0; for (const s of details) { ans += parseInt(s.substring(11, 13)) > 60 ? 1 : 0; } return ans; };substring(11, 13)与 Python 切片语义一致,取下标 11、12 两个字符(左闭右开)。
Rust
Rust 的&s[11..13]切片后调用parse::<i32>():
impl Solution { pub fn count_seniors(details: Vec<String>) -> i32 { let mut ans = 0; for s in &details { if s[11..13].parse::<i32>().unwrap() > 60 { ans += 1; } } ans } }Rust 对字符串按字节索引切片,由于该字符串全部由 ASCII 字符组成,s[11..13]恰好落在字节边界上,可以安全切片;parse::<i32>()返回Result,这里用unwrap()处理(输入保证合法)。
深入解析 Go 实现中的&15位运算技巧
这是原文档中最值得品读的细节。字符'0'的 ASCII 码是0x30(十进制 48),其二进制为110000;字符'1'是0x31,依此类推,'9'是0x39。观察规律:数字字符'0'~'9'的低 4 位恰好就是其数值本身('0'&15=0,'1'&15=1,……,'9'&15=9)。
因此s[i]&15等价于s[i]-'0',可以一步完成"字符转数字",且不需要像 Java/C++ 那样写(s[i] - '0')的括号。
为什么"不需要加括号"?因为 Go 运算符优先级表中,*和&处于同一优先级(第 5 级),且二元运算符左结合,所以:
s[11]&15*10+s[12]&15 > 60严格按优先级解析为:
((s[11]&15)*10 + (s[12]&15)) > 60即&先与左侧的s[11]结合,再参与*10,完全等价于(s[11]&15)*10,无需任何括号。这正是 a.go 第 6 行注释"对于数字字符,&15等价于-'0',但是不需要加括号"所说明的内容。而 Java/C++ 中*优先级高于&,同样写法会被错误地解析为s[11]&(15*10),这就是为什么其他语言版本必须使用-'0'并加括号,或依赖语言内置的字符串解析能力。
该技巧的适用范围:仅当确信待解析字符是数字字符时,&15才等价于-'0';若字符可能是字母或其他符号,则不能使用此写法。
复杂度分析
- 时间复杂度:O(n),其中 n 为
details的长度。每个字符串只需常数次字符访问与一次比较,与字符串内部长度无关(定长 15)。 - 空间复杂度:O(1)。仅使用若干个普通变量,未开辟随输入规模增长的额外空间(忽略排序等栈开销,本题无排序)。
仓库中的工程化实践:测试如何驱动这道题
这份题解在本仓库中不是孤立的说明文字,而是有完整的"代码 + 测试数据 + 测试脚本"工程化配套,非常值得学习其自动化验证方式。
测试数据文件 a.txt
a.txt 以"每两行一组(输入 + 期望输出)"的方式存放样例数据,题解中的两个样例都被收录其中。该文件由 copypasta/template/leetcode/generator.go 中的writeTestDataFile方法自动生成:它读取比赛页面解析出的样例输入输出,逐组写入.txt,并在每组之间插入空行便于阅读。
测试文件 a_test.go
a_test.go 中同时调用了测试框架的两个能力:
func Test_a(t *testing.T) { targetCaseNum := 0 // -1 if err := testutil.RunLeetCodeFuncWithFile(t, countSeniors, "a.txt", targetCaseNum); err != nil { t.Fatal(err) } if err := testutil.RunFuncWithRandomInput(t, countSeniors); err != nil { t.Fatal(err) } }RunLeetCodeFuncWithFile负责读取a.txt中的官方样例数据,通过反射调用countSeniors并断言输出,见 leetcode/testutil/leetcode.go。该函数先按"每NumIn+NumOut行一组"切分文件内容,再对每组数据做反射解析与结果比对;targetCaseNum = 0表示跑全部用例,设为-1则只跑最后一个用例,便于调试。RunFuncWithRandomInput则对函数做随机输入对拍(该模式在双周赛各题测试中普遍使用,见 leetcode/biweekly/102/a/a_test.go 等大量同构用例),用于捕捉样例覆盖不到的边界情况。
测试框架本身还内置了超时检测(isTLE,通过DebugTLE控制检测时长,见 leetcode/testutil/leetcode.go)以及针对字符串、整数、切片、*TreeNode、*ListNode等多种参数类型的反射解析器(parseRawArg),这也是本仓库数百个 LeetCode 题目能统一用题目号.txt+ 泛型测试脚本验证的原因。
小结
本题是典型的签到题,核心价值在于两点:一是识别定长字符串的固定字段布局,直接从固定偏移处取子串,而不必做复杂解析;二是体会Go 位运算技巧——利用 ASCII 码数字字符低 4 位即数值的特性,用s[i]&15替代s[i]-'0',并借助 Go 运算符优先级省去括号,让代码更紧凑。如果你在本仓库中看到类似的&15、&1等位运算写法,可参照 a.go 的注释理解其等价转换关系。
- 科学计算
【免费下载链接】codeforces-go
算法竞赛模板库 by 灵茶山艾府 💭💡🎈
相关推荐
LeetCode 2678 Number of Senior Citizens 多语言题解:从字符串解析到字符级运算的两种高效实现
LeetCode 2678 Number of Senior Citizens 多语言题解:从字符串解析到字符级运算的两种高效实现 本篇技术指南围绕 LeetC
示例工程教程codeforces-go 仓库实战:力扣双周赛 104「英雄的力量」贡献法递推题解全解析
codeforces go 仓库实战:力扣双周赛 104「英雄的力量」贡献法递推题解全解析 导读 本篇技术指南以仓库中 双周赛 104 第四题题解 https:
科学计算amis 帮助类字体大小(Font Size)工具类全解析:text-xs 到 text-8xl 的用法、原理与响应式实践
amis 帮助类字体大小(Font Size)工具类全解析:text xs 到 text 8xl 的用法、原理与响应式实践 本文以 packages/amis
科学计算
创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考