面试题 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