【优选算法】（第十七篇）
目录
判断字符是否唯⼀（easy）
题目解析
讲解算法原理
编写代码
丢失的数字（easy）
题目解析
讲解算法原理
编写代码
判断字符是否唯⼀（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
实现⼀个算法，确定⼀个字符串s的所有字符是否全都不同。
⽰例1：
输⼊:s="leetcode"
输出:false
⽰例2：
输⼊:s="abc"
输出:true
限制：
0<=len(s)<=100
s[i]仅包含⼩写字⺟
如果你不使⽤额外的数据结构，会很加分。
讲解算法原理
解法（位图的思想）：
算法思路：
利⽤「位图」的思想，每⼀个「⽐特位」代表⼀个「字符，⼀个 int 类型的变量的 32 位⾜够表⽰所有的⼩写字⺟。⽐特位⾥⾯如果是 0 ，表⽰这个字符没有出现过。⽐特位⾥⾯的值是 1 ，表⽰该字符出现过。
那么我们就可以⽤⼀个「整数」来充当「哈希表」。
编写代码
c++算法代码：
class Solution
{
public:bool isUnique(string astr) {// 利⽤鸽巢原理来做的优化if(astr.size() > 26) return false; int bitMap = 0;for(auto ch : astr){int i = ch - 'a';// 先判断字符是否已经出现过if(((bitMap >> i) & 1) == 1) return false;// 把当前字符加⼊到位图中bitMap |= 1 << i;}return true;}
};java算法代码：
class Solution {public boolean isUnique(String astr) {// 利⽤鸽巢原理来做优化if(astr.length() > 26) return false;int bitMap = 0;for(int i = 0; i < astr.length(); i++){int x = astr.charAt(i) - 'a';// 先判断字符是否在位图中if(((bitMap >> x) & 1) == 1) return false;// 把当前字符加⼊到位图中bitMap |= 1 << x;}return true;}
}丢失的数字（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个包含[0,n]中n个数的数组nums，找出[0,n]这个范围内没有出现在数组中的那个数。
⽰例1：
输⼊：nums=[3,0,1]输出：2
解释：n=3，因为有3个数字，所以所有的数字都在范围[0,3]内。2是丢失的数字，因为它没有出现在nums中。
⽰例2：
输⼊：nums=[0,1]
输出：2
解释：n=2，因为有2个数字，所以所有的数字都在范围[0,2]内。2是丢失的数字，因为它没有出现在nums中。
⽰例3：
输⼊：nums=[9,6,4,2,3,5,7,0,1]输出：8
解释：n=9，因为有9个数字，所以所有的数字都在范围[0,9]内。8是丢失的数字，因为它没有出现在nums中。
⽰例4：
输⼊：nums=[0]
输出：1
解释：n=1，因为有1个数字，所以所有的数字都在范围[0,1]内。1是丢失的数字，因为它没有出现在nums中。
提⽰：
n==nums.length
1<=n<=10^4
0<=nums[i]<=n
nums中的所有数字都独⼀⽆⼆
进阶：你能否实现线性时间复杂度、仅使⽤额外常数空间的算法解决此问题?
讲解算法原理
解法（位运算）：
算法思路：
设数组的⼤⼩为 n ，那么缺失之前的数就是 [0, n] ，数组中是在 [0, n] 中缺失⼀个数形成的序列。
如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在⼀起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数~
编写代码
c++算法代码：
class Solution
{
public:int missingNumber(vector<int>& nums) {int ret = 0;for(auto x : nums) ret ^= x;for(int i = 0; i <= nums.size(); i++) ret ^= i;return ret;}
};java算法代码：
class Solution {public int missingNumber(int[] nums) {int ret = 0;for(int x : nums) ret ^= x;for(int i = 0; i <= nums.length; i++) ret ^= i;return ret;}
}