LeetCode 面试题 01.01. 判定字符是否唯一-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 面试题 01.01. 判定字符是否唯一。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目

实现一个算法，确定一个字符串 s 的所有字符是否全都不同，点击此处跳转。

示例 1：

输入: s = “leetcode”
输出: false

示例 2：

输入: s = “abc”
输出: true

限制：

0 <= len(s) <= 100
s[i] 仅包含小写字母
如果你不使用额外的数据结构，会很加分。

二、C# 题解

使用数组记录出现次数，时间、空间复杂度均为 $O (n)$ ：

public class Solution {
    public bool IsUnique(string astr) {
        int[] record = new int[26];              // 记录数组
        for (int i = 0; i < astr.Length; i++) {  // 遍历字符串
            int index = (int) (astr[i] - 'a');   // 得到每个字符在数组中对应的下标
            if (record[index] > 0) return false; // 出现，则返回 false
            else record[index]++;                // 未出现，则记录 + 1
        }
        return true;                             // 到此步，则返回 true
    }
}

数组记录有些浪费内存空间了，因此使用位运算记录也可。因为题目要求是字符串内仅包含小写字母，因此只会出现26种不同的字符，使用 int 变量有 32 位长度，足以覆盖范围。

$\quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000\\ ↓ 'c'\\ 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0100\\ ↓ 'g'\\ 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0100 \quad 0100\\ ↓ 'a'\\ 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0100 \quad 0101\\ ↓ 'c'\\ 重复，返回 false$

位运算记录的本质与上述数组记录类似，差别仅是内存使用。数组使用一个 int（32 位 bit）记录，而位运算使用 1 个 bit 记录，本质无区别。当然，运行速度会快些。

public class Solution {
    public bool IsUnique(string astr) {
        int record = 0;                              // 记录 int
        for (int i = 0; i < astr.Length; i++) {      // 遍历字符串
            int index = 1 << (int) (astr[i] - 'a');  // 得到每个字符在 int 中对应的 bit 位数
            if ((record & index) != 0) return false; // 与运算结果不为 0，则表示出现过
            else record |= index;                    // 未出现，则或运算记录下该字符
        }
        return true;                                 // 到此步，则返回 true
    }
}