 空间的 7 语言题解)
★ FEATURED ARTICLE 示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南聚焦 doocs/leetcode 仓库中《程序员面试金典第 6 版》系列第一题 01.01 Is Unique判定字符是否唯一完整解析题目约束、进阶追问与位运算解题思路并结合仓库内 Python、Java、C、Go、TypeScript、JavaScript、Swift 七种语言的 Solution 源码 逐一剖析实现细节。读完后你既能独立写出通过该题的多语言代码也能理解用整数掩码替代哈希表这一面试高频位运算技巧的底层原理与适用边界。题目描述与约束分析题目原文见 英文题解 与 中文题解要求Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?即实现一个算法确定字符串s的所有字符是否全都不同并追问——如果不允许使用额外的数据结构该怎么办。题目给出的两个示例输入输出说明s leetcodefalsee重复出现两次s abctrue所有字符互不相同约束条件0 len(s) 100字符串可能为空串限制中特别注明如果你不使用额外的数据结构会很加分见 中文题解。这是一个典型的先给宽松解法、再逼你优化空间的面试题长度上限只有 100用哈希表或布尔数组一次扫描即可通过但进阶要求把辅助空间从 O(字符集大小) 压缩到 O(1)。思路演进从哈希表到位掩码第一层哈希集合一次扫描最直观的做法是用一个集合记录已经见过的字符遍历字符串若当前字符已在集合中说明存在重复返回false否则将当前字符加入集合继续扫描。该方案时间复杂度 O(n)但空间复杂度与字符集规模成正比——对任意 Unicode 字符而言最坏情况下需要存储整个字符集这正是进阶要求不允许的额外数据结构。第二层布尔数组如果提前限定字符范围例如 ASCII 字符集可以使用一个长度为 128 的布尔数组代替集合。数组本身是固定大小的数据结构但仍算使用了额外的数据空间。第三层整数位掩码本题解题目给出的示例输入全部由小写字母组成仓库文档中注明根据示例可以假定字符串中只包含小写字母实际验证也符合该假设即字符种类至多 26 种。因此可以用一个 32 位整数的每一位bit代表一个小写字母是否已出现字符c映射到位索引i c - a取值 025查询(mask i) 1是否为 1判断该字符是否已出现插入mask | 1 i把对应位置 1。位运算把集合查询与集合插入都压缩为常数时间的整数操作同时空间占用恒定为一个整数O(1)完美满足不使用额外数据结构的进阶要求。这就是为什么用掩码而不是哈希表或布尔数组——详见 英文题解中的 Thinking 注释。七种语言的实现与逐行解析仓库在该题目目录下同时维护了 README 文档 与各语言的独立 Solution 文件实现逻辑完全一致。下面逐一展开。Python3文件Solution.pyclass Solution: def isUnique(self, astr: str) - bool: mask 0 for i in map(lambda c: ord(c) - ord(a), astr): if (mask i) 1: return False mask | 1 i return True要点ord(c) - ord(a)将小写字母映射为 025 的位索引map(lambda c: ord(c) - ord(a), astr)惰性生成位索引序列无需额外列表一旦发现某位已被置 1 即返回False提前终止。Java文件Solution.javaclass Solution { public boolean isUnique(String astr) { int mask 0; for (char c : astr.toCharArray()) { int i c - a; if (((mask i) 1) 1) { return false; } mask | 1 i; } return true; } }要点Java 的int为 32 位有符号整数位 025 足够容纳 26 个小写字母c - a依赖 char 到 int 的隐式提升。C文件Solution.cppclass Solution { public: bool isUnique(string astr) { int mask 0; for (char c : astr) { int i c - a; if (mask i 1) { return false; } mask | 1 i; } return true; } };要点注意mask i 1中移位运算符优先级高于按位与实际等价于(mask i) 1这是 C/C 中常见的写法。Go文件Solution.gofunc isUnique(astr string) bool { mask : 0 for _, c : range astr { i : c - a if maski1 1 { return false } mask | 1 i } return true }要点for _, c : range astr中c是runeint32c - a得到 025 的位索引与 Go 的int类型直接兼容。TypeScript文件Solution.tsfunction isUnique(astr: string): boolean { let mask 0; for (let j 0; j astr.length; j) { const i astr.charCodeAt(j) - a.charCodeAt(0); if ((mask i) 1) { return false; } mask | 1 i; } return true; }要点TS/JS 中没有char - char的运算须用charCodeAt()取码点相减mask声明为let因为需要在循环中重新赋值。值得说明的是 JS 的位运算会将操作数转为 32 位有符号整数位 025 完全在安全范围内。JavaScript文件Solution.js/** * param {string} astr * return {boolean} */ var isUnique function (astr) { let mask 0; for (const c of astr) { const i c.charCodeAt() - a.charCodeAt(); if ((mask i) 1) { return false; } mask | 1 i; } return true; };要点与 TypeScript 版本逻辑等价c.charCodeAt()不传参数时默认取下标 0因为c是单字符结果一致。Swift文件Solution.swiftclass Solution { func isUnique(_ astr: String) - Bool { var mask 0 for c in astr { let i Int(c.asciiValue! - Character(a).asciiValue!) if (mask i) 1 ! 0 { return false } mask | 1 i } return true } }要点Swift 的Character没有直接的减法须通过asciiValueUInt8 可选值取 ASCII 码后强转Int再相减因题目限定小写字母asciiValue必然非空故使用!强制解包是安全的。复杂度与正确性分析时间复杂度 O(n)单趟扫描每个字符执行常数次位运算移位、按位与、按位或n 为字符串长度空间复杂度 O(1)只使用一个整数mask与输入规模无关。正确性论证充分性若字符串存在重复字符第二次遇到该字符时其对应的位在mask中必然已为 1查询(mask i) 1返回真函数提前返回false必要性若所有字符互不相同则每个字符的位索引只会被置 1 一次循环结束后返回true边界情况空字符串len(s) 0直接返回true语义正确长度 1 的字符串也自然返回true。方案的适用前提与局限该位掩码方案能够成立依赖于一个关键假设字符串仅包含小写字母26 个字符。仓库文档明确说明这是基于题目示例做出的合理假设。因此在面试或做题时需要注意若输入可能包含大写字母需要先归一化如tolower或调整位索引映射若输入包含任意 ASCII 字符128 种单个 32 位整数不够可改用两个整数或 128 位布尔位图若输入是任意 Unicode 字符串位掩码方案失效此时必须回到哈希表或对字符串排序后比较相邻字符后者可做到常数辅助空间但时间复杂度升至 O(n log n)。从源码结构看仓库在 lcci.json 中为本题记录了标签Array、难度Easy并在 lcci/README.md 的题解总表中列为《程序员面试金典》系列的开篇第一题适合作为位运算技巧的入门练习。相关资源导航题目文档英文题解 中文题解各语言提交文件Python3、Java、C、Go、TypeScript、JavaScript、Swift系列总览《程序员面试金典第 6 版》题解目录延伸阅读同系列中同样考察位运算的题目还有 05.03 翻转数位、05.06 整数转换、05.07 配对交换可对比体会用整数的位表达集合状态这一思想的复用方式。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐doocs/leetcode 题解面试题 01.02 判定是否互为字符重排Check Permutation的计数与排序双解法doocs/leetcode 题解面试题 01.02 判定是否互为字符重排Check Permutation的计数与排序双解法 本文围绕 LeetCode示例工程教程LeetCode 186 翻转字符串中的单词顺序基于 leetcode 仓库的 O(1) 空间原地解法与多语言源码剖析LeetCode 186 翻转字符串中的单词顺序基于 leetcode 仓库的 O 1 空间原地解法与多语言源码剖析 LeetCode 186 Revers示例工程教程LeetCode-Go 题解1207. Unique Number of Occurrences 唯一出现次数判断LeetCode Go 题解1207. Unique Number of Occurrences 唯一出现次数判断 导读 本篇围绕 LeetCode 第 12示例工程上一篇videomae-crime-detector-maxdata-v1部署指南云端与本地环境配置完整教程下一篇Statsmodels 优化器深度解析从线性代数、IRLS 到 scipy 优化的完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
