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

简介: 面试题 01.01:判定字符是否唯一

题目

题目链接

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

示例 1:

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

示例 2:

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

解题

方法一:哈希表

哈希表实现思路简单,但是使用了额外的数据结构。

class Solution {
public:
    bool isUnique(string astr) {
        unordered_set<int> set;
        for(char c:astr){
            if(set.count(c)){
                return false;
            }
            set.insert(c);
        }
        return true;
    }
};

方法二:位运算

实际上这个方法和哈希表差不多的思路,只不过实现的方法不一样。

经检查,字符范围是’a’~‘z’,因此可以使用下面的方法

参考链接

把字符串中每个字符转化为一个二进制数,转化方法为1向左N位的位运算,N为这个字符和字符‘a’的距离;

例如 Na = 0,Nb=1,Nc = 2…a = 1<<0 = 1 ,b = 1<<1 = 10, c = 1<<2 = 100…;

所以,每个字符串对应位置为1;

这种情况下,如果当前字符如果曾经出现过,也就是其中某一位对应位数的值为1,就意味着曾经出现,返回False;

否则,如果没有出现过,那么通过|或运算,把这一位的值改写为1;

例如 ‘abca’ : a= 1,b=10,c=100,前三次结果mark为111,最后一次111与001有相同符合条件,返回False

class Solution {
public:
    bool isUnique(string astr) {
        int mask=0;
        for(char c:astr){
            int moveBit=c-'a';
            if((mask&(1<<moveBit))!=0) return false;
            else{
                mask|=(1<<moveBit);
            }
        }
        return true;
    }
};
相关文章
|
6月前
|
存储 算法 程序员
【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表
可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;
|
算法 程序员
【Leetcode】NC31 第一个只出现一次的字符(牛客网)、面试题 01.01. 判定字符是否唯一
题目描述: 描述 在一个长为n字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)
69 0
|
6月前
剑指Offer LeetCode 面试题50. 第一个只出现一次的字符
剑指Offer LeetCode 面试题50. 第一个只出现一次的字符
34 0
|
Java 数据处理
Java IO(File、字节输入输出流、字符输入输出流、打印流)附带相关面试题
1.File类,2.字节输入输出流(InputStream Outputstream),3.Writer与Reader字符输入输出流,4.打印流
86 0
|
编译器 C语言 C++
C语言面试题 - 字符空间操作类
C语言面试题 - 字符空间操作类
83 0
|
算法 索引
【Day15】算法刷题(解题思路+详细注释)[面试题 17.09. 第 k 个数 ][424. 替换后的最长重复字符 ][438. 找到字符串中所有字母异位词 ]
了解[面试题 17.09. 第 k 个数 ][424. 替换后的最长重复字符 ][438. 找到字符串中所有字母异位词 ]。
172 0
【Day15】算法刷题(解题思路+详细注释)[面试题 17.09. 第 k 个数 ][424. 替换后的最长重复字符 ][438. 找到字符串中所有字母异位词 ]
|
存储 算法
面试高频算法题---无重复字符的最长子串
给定一个字符串s,请你找出其中不含有重复字符的最长子串长度
面试高频算法题---无重复字符的最长子串
|
存储 关系型数据库 MySQL
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(3)
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(3)
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(3)
|
存储 关系型数据库 MySQL
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(2)
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(2)
702 0
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(2)
|
存储 SQL 缓存
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(1)
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。
174 0
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(1)