Steven Blogs

面试题 01.01. 判定字符是否唯一

题目：面试题 01.01. 判定字符是否唯一open in new window

原题链接open in new window,简单。

要求：实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = "leetcode"
输出: false

示例 2：

输入: s = "abc"
输出: true

限制： 0 <= len(s) <= 100 如果你不使用额外的数据结构，会很加分。

提示：

  1. 试试散列表
  2. 位向量有用吗？
  3. 你能用O(NlogN)的时间复杂度解决它吗？这样的解法会是什么样呢？

解答

  1. 双重循环
public bool IsUnique(string astr) {
    // 冒泡类似的，双重循环 效率不好
    for(int i=0;i<astr.Length;i++){
        for(int j=i+1;j<astr.Length;j++){
            if(astr[j]==astr[i])
                return false;
        }
    }
    return true;
}
  1. 记字符，参考了答案，使用 bool数组
public bool IsUnique(string astr) {   
    if(astr == null || astr=="")
        return true;
    
    // ASCII码字符个数为128个
    bool[] charArr = new bool[128]; // 默认值都是false

    for(char c in astr){
        if(charArr[c])  // 如果为true 说明已经有相同的字符了，返回不唯一 false
            return false;
        else
            charArr[c] = true; // 第一次遇到字符，设置当前字符标志为 true
    }
    return true;
}
  1. 位运算，参考了答案
/*
常用知识
a & (1<<k) 用于判断a的第k位数字是0是1，其实和我们使用数组差不错。相等于 nums[k];
a | (1<<k) 用于将a的第k位数字赋值为1, 相当于nums[k]=1
*/
public bool isUnique(string astr){
    long low64 = 0;  // long 数据类型长 64； ASCII码字符个数128；使用两个 long来处理所有的字符；
    long high64 = 0;

    foreach(char c in astr)
    {
        if (c >= 64) // ASCII码后 64 个字符
        {
            long bitIndex = 1L << (c - 64);  // c-64 计算相对位置；注意 1L不能变，原因 long类型； 计算位移后的数据
            if ((high64 & bitIndex) != 0)   // 确定当前位置是否为1
                return false;
            high64 |= bitIndex;  // 不为1 当前位置的值改为 1
        }
        else  // ASCII码前 64 个字符
        {
            long bitIndex = 1L << c;
            if ((low64 & bitIndex) != 0)
                return false;
            low64 |= bitIndex;
        }
    }
    return true;
}

反思

看了答案之后，才明白这道题真正考察的是位运算，这块是自己一个模糊概念。

  1. 计算机处理的都是 0 1 0 1
  2. 编程语言处理数据也都是基于0101的，都是各自有规定。

不太会组织，大概意思就是想说 计算机底层都是处理0101的，C#的值类型都是0101 看是多少位归于那种类型

位运算符和移位运算符（C# 参考）open in new window 先的明白<<左移运算，如下，一看便知

// Convert.ToString(1L,2) 后面2代表 2进制
Convert.ToString(0L,2)     // "0" 
Convert.ToString(1L,2)     // "1"
Convert.ToString(1L<<1,2)  // "10"
Convert.ToString(1L<<2,2)  // "100"
Convert.ToString(1L<<3,2)  // "1000"
Convert.ToString(1L<<63,2) // "1000000000000000000000000000000000000000000000000000000000000000"
Convert.ToString(0L<<22,2) // "0"

|

Convert.ToString(0L,2)          // "0" 
Convert.ToString(1L<<2,2)       // "100"

Convert.ToString(0L|(1L<<2),2)  // "100"
Convert.ToString(1L|(1L<<2),2)  // "101" 
Convert.ToString(3L,2)          // "11"
Convert.ToString(3L|(1L<<2),2)  // "011"|"100"="111"

&

Convert.ToString(0L,2)          // "0" 
Convert.ToString(1L<<2,2)       // "100"

Convert.ToString(0L&(1L<<2),2)  // "0"

Convert.ToString(4L,2)         //"100"
Convert.ToString(4L&(1L<<2),2) //"100"

Convert.ToString(5L,2)         //"101"
Convert.ToString(5L&(1L<<2),2) //"100"

看完就明白了

Contributors: FHL