实现一个算法，确定一个字符串 s 的所有字符是否全都不同（两种方法）

你的名字 2023-02-17 02:26 11阅读 0赞

题目：

> 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。  
> 示例 1：  
> 输入: s = “leetcode”  
> 输出: false  
> 示例 2：  
> 输入: s = “abc”  
> 输出: true  
>   
> 限制：  
> 0 <= len(s) <= 100  
> 如果你不使用额外的数据结构，会很加分。

### 一、双循环牺牲时间 ###

**不使用额外的数据结构**，所以计数的方法不能用。

这种情况来说，容易想到的就是牺牲时间换空间，第一种方法就是用双循环来代替额外的数据结构。

内外循环都遍历整个字符串，然后对比是否除了自身之外还有别的位置是一样的字符。

class Solution {
        
        public boolean isUnique(String astr) {
        
            if(astr.length()==0||astr.length()==1){
        
                return true;
            }
            for(int i=0;i<astr.length();i++){
        
                for(int j=0;j<astr.length()&&j!=i;j++){
        
                    if(astr.charAt(i)==astr.charAt(j)){
        
                        return false;
                    }
                }
            }
            return true;
        }
    }

### 二、二进制数作哈希表 ###

额外的空间不可使用？能不能有替代方案。

来看看这种做法，最近做了比较多的题都是在用位运算，然后就看到了这一种非常妙的做法。

我们先来复习一下位运算。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]

然后，我们想一个问题，**由于 ASCII 码字符个数为 128 个。**（注意，扩展的 ASCII 不是128个字符，有256个），并不多，如果用额外数组存储显然是不符合要求了。

但是，可以使用 **两个 64 位的 long 变量** 来存储是否出现某个字符，他们对应的**二进制位 1** **表示出现过**，**0 表示未出现过**。

128个字符，每个字符都对应的是一个唯一的数字，我们可以直接转为二进制， long 类型长度为 64 个二进制位，所以用两个数字。

每个字符按照对应的 ASCII 码值，可以分为 >= 64 (64~127) 和 <64 （0~63），记码值为 c ，则 ，0 <= c < 128。

*  那么 c 可以对应 long 数字的某一个位，我们只需要将这一位，置为 1 就可以，具体的做法，就是**将 1 左移 c 次**；
 *  在把对应位置置 1 之前判断，这一位是不是已经是 1 了？是的话就说明重复了，直接可以 return false。

class Solution {
        
      public boolean isUnique(String astr) {
        
            long low64 = 0;
            long high64 = 0;
    
            for (char c : astr.toCharArray()) {
        
                if (c >= 64) {
        
                    long bitIndex = 1L << (c-64);//如果>=64，先统一左移64位
                    if ((high64 & bitIndex) != 0) {
        
                        return false;//如果这一位已经是 1 ，那么进行与操作得到结果不是 0
                    }
                    high64 |= bitIndex;//进行或运算，结果是把对应位置为 1
    
                } else {
        
                    long bitIndex = 1L << c;
                    if ((low64 & bitIndex) != 0) {
        
                        return false;
                    }
                    low64 |= bitIndex;
                }
            }
            return true;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610224319221.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70