判定字符是否唯一
题目描述
判断字符串中所有字符是否都是唯一的。
算法思路
解法一：哈希数组
从前往后扫描字符串，将扫描到的字符放入哈希表中。如果对应的值已存在则返回 false，否则标记为已访问。时间复杂度 O(N)，空间复杂度 O(N)。
不需要真的创建哈希表，只需创建一个大小为 26 的哈希数组，遍历元素时对应位置 +1。
解法二：借助位图思想
单独一个 int 变量有 32 位。从 0 位到 25 位分别代表 a~z 26 个小写字母。只要前面出现过，对应比特位就是 1，否则为 0。大量运用查询某一个比特位是否为 1，以及将某一个比特位修改为 1。
优化：鸽巢原理
因为这道题有 26 个英文字母，当字符串长度 len > 26，就一定有重复字符。所以可以先判断字符串长度是否大于 26。
代码实现
丢失的数字
题目描述
给定包含 n 个不同数字的数组，找出其中缺失的那个数字。
算法思路
解法一：哈希表
在 n+1 个数中找丢失的数，创建同等规模的哈希表，key 为 0 到 n。扫描一遍数组之后，返回 val=0 对应的 key。时间复杂度 O(N)，空间复杂度 O(N)。
解法二：高斯/等差数列求和
利用公式计算总和，减去数组实际总和。时间复杂度 O(N)，空间复杂度 O(1)。
解法三：位运算（异或^运算）
将所有数（上下所有的数）全部异或在一起，相同的数会消去，最终结果就是缺失的数。时间复杂度 O(N)，空间复杂度 O(1)。
为了方便理解两步循环的异或操作，举例如下：假设第一个循环是 ret=1^2^3^5，第二个循环是 ret=ret^1^2^3^4^5，通过异或的消消乐原理，最终计算的就是 ret=1^1^2^2^3^3^4^5^5=4。
