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

image.png

字符串s中的字母的ASCII码值范围是0-127，刚好128位，使用一个128bit来表示，比如a的ASCII码值是97，则第98个bit位上面是1（从0开始），依次类推，如果前面出现了字符a, 这次是字符b， 则将1<<b位，判断前面的bit值，记为val, val&(1<<b), 如果结果不为0，说明a和b是同一个字符；如果为0，说明a,b不同，将b对应的bit位置为1，由于Java中的数字没有128位的，因此可以用两个long类型分别表示高64位和低64位

a&(1<<k): 判断a的第k位是否为1(k从0开始) a|=(1<<k): 将a的第k位置为1（k从0开始）

  1. class Solution {
  2.     public boolean isUnique(String astr) {
  3.         long low64=0,high64=0;
  4.         for(char c:astr.toCharArray())//ASCII码值0-127
  5.         {
  6.             //0-63 在low64位
  7.             //64-128 在高64位
  8.             if(c>=64)
  9.             {
  10.                 long bitIndex=1L<<(c-64);
  11.                 if((high64&bitIndex)!=0)
  12.                     return false;
  13.                 high64|=(1L<<(c-64));//c对应的bit位置为1
  14.             }
  15.             else
  16.             {
  17.                 long bitIndex=1L<<c;
  18.                 if((low64&bitIndex)!=0)
  19.                     return false;
  20.                 low64|=(1L<<c);
  21.             }
  22.         }
  23.         return true;
  25.     }
  26. }