admin管理员组文章数量:1440489
【位运算】判定字符是否唯一 && 丢失的数字
面试题 01.01. 判定字符是否唯一
面试题 01.01. 判定字符是否唯一
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
代码语言：javascript代码运行次数：0运行复制输入: s = "leetcode"
输出: false 示例 2：
代码语言：javascript代码运行次数：0运行复制输入: s = "abc"
输出: true限制：
0 <= len(s) <= 100s[i]仅包含小写字母- 如果你不使用额外的数据结构，会很加分。
解题思路：位运算
拿到这道题的第一反应就是使用哈希表来记录字符串的每一个字符，但是这道题其实还可以做到更极致一些，使用一个变量来充当哈希表，然后通过位运算实现哈希映射操作，因为当前只有小写字母，并且只要求出现过一次，那么我们就让一个变量的每一个比特位表示出现过 0 还是 1 次，只要每次循环判断到当前比特位是 1 了，说明之前有出现过该字符，则直接返回错误，如果不存在的话就将该比特位置一即可！
此外还可以运用之前学到的鸽巢原理，就是小写字符有 26 个，那么最多不重复的就是 26 个，也就是说如果字符串长度超过了 26，则代表一定出现了重复的字符！
思路简单，这里就不再赘述了，看代码实现：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
bool isUnique(string astr) {
// 鸽巢原理：当小写字符数量超过了26个，说明一定会出现重复的
if(astr.size() > 26)
return false;
// 采用位运算的思想
int hash = 0;
for(int i = 0; i < astr.size(); ++i)
{
// 如果已经出现了一次说明重复了
if((hash >> (astr[i] - 'a')) & 1)
return false;
hash |= (1 << (astr[i] - 'a'));
}
return true;
}
};268. 丢失的数字
268. 丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
代码语言：javascript代码运行次数：0运行复制输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。示例 2：
代码语言：javascript代码运行次数：0运行复制输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。示例 3：
代码语言：javascript代码运行次数：0运行复制输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。示例 4：
代码语言：javascript代码运行次数：0运行复制输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。提示：
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums中的所有数字都 独一无二
进阶： 你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
解题思路：位运算
设数组的大小为 n ，那么缺失之前的数就是 [0, n] ，数组中是在 [0, n] 中缺失一个数形成的序列。
如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在一起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数了~
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = 0;
for(int i = 0; i <= nums.size(); ++i)
n ^= i;
for(int i = 0; i < nums.size(); ++i)
n ^= nums[i];
return n;
}
};本文标签： 位运算判定字符是否唯一 ampamp 丢失的数字
版权声明：本文标题：【位运算】判定字符是否唯一 && 丢失的数字 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/biancheng/1747741782a2752470.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论