1. 思考题目：实现一个算法，确定一个字符串s的所有字符是否全都不同。
示例1：
输入：s = "leetcode"
输出：false
示例2：
输入：s = “abc”
输出：true
限制：
- 0 <= len(s) <= 100
- 如果你不使用额外的数据结构，会很加分
判断一个集合中（该题中字符串相当于字符的集合）是否所有元素都不相同，首先想到一个快速校验方案：该集合中元素个数是否超过了元素种类个数？如果超过了元素种类个数，那么直接有结论，该集合中元素必定存在重复。
比如元素种类有两种A和B，集合中存在三个元素，那么其中至少有两个元素重复。
根据这一点，自然而然会提出如下问题，以精确程序的适用范围。
该字符串中字符种类的集合是什么？
该问题具体到字符中，即是需要确认该字符串使用了何种字符集？
即有了如下发问：
1. 该字符串是否只包含英文字母？如果只包含英文字母，是否区分大小写？
英文字母26个，包含大小写52个
2. 该字符串是否是ASCⅡ字符串，字符集是ASCⅡ还是扩展ASCⅡ？
ASCⅡ字符集包含128个字符，扩展ASCⅡ字符集包含256个字符
3. 该字符串是否是Unicode字符串？
Unicode字符串难以确定集合数量，按部就班一个个字符比较较为合适
以下假定字符串使用的是ASCⅡ字符集
2. 常规解法这边判断一个集合中是否存在重复元素，且集合中元素最大种类已知，可以构建一个boolean数组，索引i值表示是否存在过集合中第i种元素，若该元素出现两次，立即返回false。
同时当字符串中字符个数超过字符种类的话，也可以直接返回false。
但是注意，这边题目中限制条件0 <= len(s) <= 100，而在ASCⅡ字符集场景下，该限制条件已经避免了字符个数超过字符种类的可能，所以该场景下没有判断必要。
public boolean isUnique(String astr) {
if (astr.length() > 128) {
// 快速校验
// 字符个数超过字符种类，必定存在重复字符
// 由于该题有了限制条件0 <= len(s) <= 100，所以该场景是不需要这个判断的
return false;
}
boolean[] charSet = new boolean[128];
for (int i = 0; i < astr.length(); i++) {
int val = astr.charAt(i);
if (charSet[val]) {
// 当前元素已经出现过
return false;
}
// 当前元素第一次出现
charSet[val] = true;
}
// 所有元素都是第一次出现
return true;
}
该解法中时间复杂度O(n)，空间复杂度O(1)
当然，如果考虑到for循环永远不会超过128次，也可以认为时间复杂度O(1)
3. 位向量优化空间使用时间复杂度已经没有优化空间了，因为判断字符是否重复，必然需要遍历全部字符，空间复杂度虽然达到了O(1)，但是空间使用上仍然可以优化。
上述解法使用了boolean数组，每个boolean值记录当前索引对应元素是否出现过。Java中一个boolean值占1字节，也就是8bit。但是这边只需要记录一个状态，1bit完全可以记录其中一个元素的状态，而不需要1字节(8bit)的boolean。
所以该场景常可以考虑使用位向量替换boolean数组，空间使用可以减少为原来的1/8。
这边同样考虑ASCⅡ字符集，共128个字符种类，一个int值4字节，32bit，即我们需要4个int来替换boolean数组，记录信息。
public boolean isUnique(String astr) {
if (astr.length() > 128) {
// 快速校验
// 字符个数超过字符种类，必定存在重复字符
return false;
}
// 4个int共128位bit，记录状态
// val/32 得到哪一个int中记录了当前字符的状态
// val%32 得到当前int的哪一位记录了当前字符的状态
int[] charSet = new int[4];
for (int i = 0; i < astr.length(); i++) {
int val = astr.charAt(i);
// 找当前字符对应第几个int的哪一位bit
// 当前bit是否为1
if (isExisted(val, charSet)) {
// 已经存在过
return false;
}
// 首次出现
setShowed(val, charSet);
}
// 所有元素都是首次出现
return true;
}
// 判断val对应的bit是否为1
private boolean isExisted(int val, int[] charSet) {
int currInt = charSet[val/32];
// 注意点1
return ((currInt >> (val % 32)) & 1) > 0;
}
// 设置val对应的bit为1
private void setShowed(int val, int[] charSet) {
int currInt = charSet[val/32];
// 注意2
charSet[val/32] = currInt | (1 << (val % 32));
}
这边有两个位运算的注意点
注意点1：判断某一位，比如i位是否为1，这边需要先右移i位，然后与1做与运算，结果如果大于0，说明i位为1，否则为0
注意点2：将某一位，比如i位置为1，这边需要位或运算
4. 不使用额外数据结构如果不使用额外数据结构，可以遍历每一个字符，依次与其他字符比较，存在相同的字符则返回false。
public boolean isUnique(String astr) {
if (astr.length() > 128) {
return false;
}
for (int i = 0; i < astr.length(); i++) {
int currVal = astr.charAt(i);
for (int j = i + 1; j < astr.length(); j++) {
if (currVal == astr.charAt(j)) {
return false;
}
}
}
return true;
}
该算法时间复杂度O(n^2)，空间复杂度O(1)
