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

﹏ヽ暗。殇╰゛Y 2022-10-29 07:33 142阅读 0赞

> 前言：主要目的是为了持续输出，用浅显易懂，各种各样的方式来解析算法题，同时提高算法能力。答主的水平也有限，大家共同进步。

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

题目：

#### 实现一个算法，确定一个字符串`s`的所有字符是否全都不同 ####

##### 示例1： #####

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

##### 示例2： #####

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

##### 限制 #####

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

这是一道很简单的算法题，解题方法有很多，我们介绍几种不同思路的算法，以后遇到相同类型的算法题，我也会更新在此帖下面。

先来一种简单、出其不意的方式。

##### 1. 巧用`indexOf`与`lastIndexOf` #####

执行用时：80 ms, 在所有 JavaScript 提交中击败了67%的用户  
内存消耗：37.6 MB, 在所有 JavaScript 提交中击败了70%的用户

解析：`indexOf`和`lastIndexOf`这两个方法，顾名思义，前者用来找到某个值是否存在于该数组（字符串）中，如果找到，返回某值第一次出现的下标，后者相同，区别就是前者是正序查找（也就是从字符串的第一位开始进行对比），后者是倒序查找（从字符串的最后一位开始对比）。  
由此可得，如果某个值在该数组（字符串）中只出现了一次，那么他正序查到和倒序查找返回的下标肯定是一致的，反之则证明至少出现了两次。

所以，当正序和倒序的坐标不相同时，我们可以直接返回`false`,游戏结束；当整个循环都进行完毕，还是结束时，我们就可以判定该字符串中没有相同的值了，可直接返回`true`。

##### 2. 利用`ES6`新特性`Set` #####

var isUnique = function(astr) { 
        return new Set([...astr]).size === astr.length;
    };

执行用时：88 ms, 在所有 JavaScript 提交中击败了28%的用户  
内存消耗：37.7 MB, 在所有 JavaScript 提交中击败了32%的用户

可谓是失之毫厘，差之千里。相差了0.08ms而已…

解析：`Set`是`ES6`提供的数据结构，类似于数组，但是成员的值都是唯一的，没有重复的值。 – ES6入门（阮一峰）

具体关于`Set`的介绍，各位看官如果有兴趣的话，可以去百度上搜一下这本书啊，都有详细的介绍，也可以购买实体书籍。

所以，我们只需要判定长度就可以了，如果相同，证明没有重复的元素，反之相反。

##### 3. 利用`indexOf`特性 #####

其实解法1和2都不是最优解，都是利用了原生的一些特性，但解法1显然还有优化的空间。

各位看官是否还记得`indexOf`其实还有第二个参数。

stringObject.indexOf(searchvalue,fromindex)
    searchvalue -> 必需。规定需检索的字符串值。
    fromindex -> 可选的整数参数。规定在字符串中开始检索的位置。它的合法取值是 0 到 stringObject.length - 1。如省略该参数，则将从字符串的首字符开始检索。 --w3school.com.cn

上面这一段话，就是直接从网站上拿下来的，我们可以利用该方法的第二个参数来做文章完成此次题目。

如果某字符串中没有相同的字母，那我们从该字母所在的位置后开始查找，将会查不到结果，所以我们可以利用该特性算出结果，同时也减少了`indexOf`的计算次数。

代码如下：

执行用时：80 ms, 在所有 JavaScript 提交中击败了66.01%的用户  
内存消耗：37.3 MB, 在所有 JavaScript 提交中击败了96.74%的用户

其实这道题的解法还有很多，比如利用循环来代替`indexOf`，或者用一个新对象来代替`new Set`去重，思路都大题相同，所以在此不再重复，方法千千万万，能够真正为自己所用，才是目的。

#### 总结 ####

总结一下我们三种方法的三种思路吧，在遇到同种类型的题时，我们也可以轻松写出答案。

*  解法一利用了倒序和正序的差值来确定是否具有唯一性
 *  解法二利用了去重后的长度和原始长度的对比
 *  解法三通过去掉自身后找与自身重复的方法来判定唯一性

突然想到了这道题的延伸题目：

实现一个算法，确定一个字符串s的所有字符是否全都不同，如果有相同的字母，请算出相同的次数。

这个题目就作为我们本次的延伸题目吧，答案会放在之后的文章中。

文章会同步更新到知乎账号