判定字符是否唯一
题目描述
判断字符串中所有字符是否都是唯一的。
算法思路
解法一：哈希数组
从前往后扫描字符串，将扫描到的字符放入哈希表中。如果对应的值已存在则返回 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。
代码实现
两整数之和
题目描述
不使用运算符 + 和 -，计算两个整数的和。
算法思路
使用位运算（异或无进位相加）。
- 异或 ^ 用于无进位相加。
- 按位与 & 找到需要进位的位置。
- 进位需要左移一位 <<1。
- 重复上述过程直到进位为 0。
对于上图，如果两个数的同一位置进行无进位相加，进位的结果只可能是 1 或者 0。蓝色的两行通过按位与&，可以得到红色的进位结果。
如果还是存在消去进位的情况，就要重复上面的操作，先分别算出 c^d 和 (c&d)<<1 的结果。继续 e^f，此时就没有消去进位的情况，得到的就是最终的结果。
我们只需要以 (a&b)<<1 != 0 作为循环判断条件，对每次得到的进位结果进行判断，直到进位等于 0，结束循环，最终的 a^b 即为最开始 a+b 的结果。
过程总结
代码实现
只出现一次的数字Ⅱ
题目描述
数组中除了一个元素只出现一次外，其余每个元素均出现三次。
算法思路
任意一个比特位，会出现如下四种情况：
- 三个 0
- 两个 0，一个 1
- 一个 0，两个 1
- 三个 1
对四个数的 32 位比特位的某一位之和出现的四种情况进行剖析，我们发现圈起来的数字前后一一对应。左边圈起来的数表示只出现一次的那一个比特位，这个比特位与四个比特位之和 %3 得到的结果相等。
因此，创建一个返回值 ret，把这四个数的每一个比特位加起来，再模 3，得到的结果放入 ret 对应的比特位上。如果模 3 的结果为 0，不用修改 ret 对应的比特位；如果模 3 的结果为 1，就把 ret 对应比特位修改为 1，直到修改完 ret 的 32 位比特位即可。
拓展：如果一个数组中，有一个数出现一次，其他相同的数出现 n 次，把模 3 修改成模 n，其他操作相同。
代码实现
消失的两个数字
题目描述
给定一个包含 0, 1, ..., n 中 n-2 个不同数字的数组，找出缺失的两个数字。
算法思路
这道题的算法原理是 268.丢失的数字 + 只出现一次的数字Ⅲ 的算法原理糅合。
解法：位运算
回忆丢失的数字中的算法原理，就是把 nums 中的数和 0 ~ N 这所有的数都糅合在一起，通过异或来找出丢失的数。
将所有的数异或在一起，定义一个变量 tmp 来接收。通过异或消消乐的特性，最终 tmp = a ^ b，就是缺失的那两个数异或的结果。
接下来，我们要把 a，b 分开。需要先找到 tmp 中，比特位为 1 的那一位。因为 a 和 b 一定是不同的两个数，a^b 的最终结果 tmp 绝对是不等于 0 的，所以在 tmp 的 32 位比特位上，肯定有二进制数为 1 的比特位，记录这个位置的下标为 x。
这个二进制数 1 的出现，是因为异或运算律：相同为 0，相异为 1。所以只要 tmp 中二进制位对应的二进制数为 1，a，b 对应的二进制位肯定是不同的。
那么，就可以根据 x 位的不同，对 a，b 划分成两个单独部分，对每个部分中的所有数进行异或。
思考链路
总结
代码实现
相关题目推荐
191. 位 1 的个数 338. 比特位计数 461. 汉明距离 136.只出现一次的数字 260.只出现一次的数字III
