实现一个算法,确定一个字符串 s 的所有字符是否全都不同。不使用额外的数据结构

示例1:

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

示例2:

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

用map存储出现过的字符,很容易做出来。如何不适用额外的数据结构(额外的空间)实现呢?可以使用位运算

举例 [3, 0, 3] 判断数组有重复元素
1. 利用左移运算 1 << 3 是 8 转换二进制 是 '1000'
2. 当遍历到0时,进行左移运算, 1 << 0 是 1 转换二进制 是 '0001'
3. 每次都与上一次结果进行或运算,8 | 1 是 9 转换二进制 是 '1001', 
   这时可以看到我们用二进制中的位数是1来代表出现过。
4. 那如何快速判断是否出现过呢,可以采用与运算(位数都是1才会是1)的特性。
   如果之前没有出现过,那二进制中位数为1的位置对应不上,最后结果应该是0。
   例如:9 & (1 << 3) 会等于8,说明倒数第四位数,也就是 3重复了。
5. 我们将字母计算出左移的长度,即可像上述操作一样,检测是否只出现一次。
/**
 * @param {string} astr
 * @return {boolean}
 */
var isUnique = function(astr) {
  let mark = 0;
  for (let char of astr) {
    // 需要左移的位数
    const c = char.charCodeAt() - 97;
    // mark 与 左移结果进行与运算,如果不是0,说明其中有一位都是1,说明重复
    if ((mark & (1 << c)) !== 0) {
      return false;
    }
    // 不重复,mark 与 左移结果 进行或运算,相当于保存该值
    mark = mark | (1 << c);
  }
  return true;
};