[CareerCup] 1.1 Unique Characters of a String 字符串中不同的字符

简介:

1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structure?

这道题让我们判断一个字符串中是否有重复的字符,要求不用特殊的数据结构,这里应该是指哈希表之类的不让用。像普通的整型数组应该还是能用的,这道题的小技巧就是用整型数组来代替哈希表,在之前Bitwise AND of Numbers Range 数字范围位相与的解法二中也用到过这种方法。由于ASCII表里的基本表共有128个字符,也就是可以用键盘表示出来的,整个表共有256个字符,所以我们只要用一个大小为256的整型数组就可以包含所有的字符,我们遍历输入字符串,对每一个字符都存入到相应位置,并赋值1,如果遇到已经为1的,说明之前出现过该字符,返回false,如果遍历完s,则返回true,代码如下:

class Solution {
public:
    bool isUniqueChar(string s) {
        if (s.size() > 128) return false;
        int m[256] = {0};
        for (int i = 0; i < s.size(); ++i) {
            if (m[s[i]] > 0) return false;
            m[s[i]] = 1;
        }
        return true;
    }
};

书上还给了另一种解法,是用位操作 Bit Manipulation,但是这种解法只有当输入字符串是由小写字母组成的才成立,因为小写字母只有26个,不超过整型int的32位,对于每个字母,我们将对应位置设为1,然后看之前是否是1,是的话返回false,不是的话设为1。跟上面的方法核心是一样的,只不过空间上省了很多,但是也对输入做了更为严格的限制,代码如下:

// Only works when s consists of lower-case letters a-z
class Solution {
public:
    bool isUniqueChar(string s) {
        int m = 0;
        for (int i = 0; i < s.size(); ++i) {
            int d = s[i] - 'a';
            if (m & (1 << d) > 0) return false;
            m |= (1 << d);
        }
        return true;
    }
};

本文转自博客园Grandyang的博客,原文链接:字符串中不同的字符[CareerCup] 1.1 Unique Characters of a String ,如需转载请自行联系原博主。

相关文章
|
1月前
|
Python
Python中的f-string:更优雅的字符串格式化
Python中的f-string:更优雅的字符串格式化
216 100
|
1月前
|
开发者 Python
Python中的f-string:高效字符串格式化的利器
Python中的f-string:高效字符串格式化的利器
291 99
|
1月前
|
Python
Python中的f-string:更优雅的字符串格式化
Python中的f-string:更优雅的字符串格式化
|
1月前
|
开发者 Python
Python f-string:高效字符串格式化的艺术
Python f-string:高效字符串格式化的艺术
|
2月前
|
Python
Python中的f-string:更简洁的字符串格式化
Python中的f-string:更简洁的字符串格式化
225 92
|
19天前
|
编解码 Java 开发者
Java String类的关键方法总结
以上总结了Java `String` 类最常见和重要功能性方法。每种操作都对应着日常编程任务,并且理解每种操作如何影响及处理 `Strings` 对于任何使用 Java 的开发者来说都至关重要。
165 5
|
4月前
|
存储 编译器 C语言
关于string的‘\0‘与string,vector构造特点,反迭代器与迭代器类等的讨论
你真的了解string的'\0'么?你知道创建一个string a("abcddddddddddddddddddddddddd", 16);这样的string对象要创建多少个对象么?你知道string与vector进行扩容时进行了怎么的操作么?你知道怎么求Vector 最大 最小值 索引 位置么?
99 0
|
7月前
|
缓存 安全 Java
《从头开始学java,一天一个知识点》之:字符串处理:String类的核心API
🌱 **《字符串处理:String类的核心API》一分钟速通!** 本文快速介绍Java中String类的3个高频API:`substring`、`indexOf`和`split`,并通过代码示例展示其用法。重点提示:`substring`的结束索引不包含该位置,`split`支持正则表达式。进一步探讨了String不可变性的高效设计原理及企业级编码规范,如避免使用`new String()`、拼接时使用`StringBuilder`等。最后通过互动解密游戏帮助读者巩固知识。 (上一篇:《多维数组与常见操作》 | 下一篇预告:《输入与输出:Scanner与System类》)
169 11
|
7月前
|
Java
课时14:Java数据类型划分(初见String类)
课时14介绍Java数据类型,重点初见String类。通过三个范例讲解:观察String型变量、&quot;+&quot;操作符的使用问题及转义字符的应用。String不是基本数据类型而是引用类型,但使用方式类似基本类型。课程涵盖字符串连接、数学运算与字符串混合使用时的注意事项以及常用转义字符的用法。
185 9
|
7月前
|
存储 JavaScript Java
课时44:String类对象两种实例化方式比较
本次课程的主要讨论了两种处理模式在Java程序中的应用,直接赋值和构造方法实例化。此外,还讨论了字符串池的概念,指出在Java程序的底层,DOM提供了专门的字符串池,用于存储和查找字符串。 1.直接赋值的对象化模式 2.字符串池的概念 3.构造方法实例化
111 1