毕业设计医院网站设计怎么做,现在都用什么软件做网站,全国造价工程师管理系统官网,电商公司怎么运营和管理目录
前言#xff1a;
判定字符是否唯一
丢失的数字
比特位计数
只出现一次的数字III 前言#xff1a;
本文的主题是位运算#xff0c;通过四道题目讲解#xff0c;一道是判断字符是否唯一#xff0c;一道是只出现一次的数字III#xff0c;一道是比特位计数…目录
前言
判定字符是否唯一
丢失的数字
比特位计数
只出现一次的数字III 前言
本文的主题是位运算通过四道题目讲解一道是判断字符是否唯一一道是只出现一次的数字III一道是比特位计数一道是丢失的数字。 链接分别为
338. 比特位计数 - 力扣LeetCode 面试题 01.01. 判定字符是否唯一 - 力扣LeetCode
260. 只出现一次的数字 III - 力扣LeetCode 268. 丢失的数字 - 力扣LeetCode
因为这些题目都是比较简单的所以一一揉在一起介绍。
那么话不多说直接进行主题咯。 判定字符是否唯一 这道题目是作为面试题目出现的作为一道面试题目它有很多解法比如我们可以使用哈希映射使用map 使用set使用函数count就可以判断是否出现了两次也可以使用数组遍历一遍看哪个下标对应的值是2就返回false即可解法是非常非常多的说白了这道题目就是让我们判读这堆“数字”里面是否有重复的数字。
那么前两个方法多多少少都用到了额外的数据结构额外的空间相对来说还是没有那么好毕竟空间还是大了一点我们不妨利用位图的思想一个Int就可以搞定遍历到的时候将位图对应的位置置为1再次如果判断到了直接返回false即可。
当然了这道题目可以使用鸽巢原理进行优化一共才26个英文字符如果字符串的长度超过了26直接返回false即可。
以上是题目解析 算法原理以下是原理编写
class Solution
{
public:bool isUnique(string astr) {int bitmap 0;for(auto e : astr){int x e - a;if(((bitmap x) 1) 1) return false;else bitmap | (1 x);} return true;}
};
丢失的数字 题目十分简单我们现在应该思考的是我们可以用多少种解法这道题目无非就是让我们从一个连续的数集里面找到缺失的数字就可以了。“那这道题不就是缺失的数字吗”
第一种解法高斯求和因为数字肯定是从0开始到n的所以我们可以将0到n这段区间的所有的数字加起来最后减去给我们的这段区间的和即可。时间复杂度为O(N) 空间复杂度为O(1)
第二种解法哈希映射我们就开一个n 1的数组遍历数组对应下标1看谁为2即可。时间复杂度为O(N) 空间复杂度为O(N)相对来说就不是那么好了。
第三种解法遍历数组看i 1是否为前一个数 1即可。
第四种解法异或的运算律数组的下标和数异或看谁空出来了就可以了。
class Solution {
public:int missingNumber(vectorint nums) { sort(nums.begin(),nums.end());if(nums[0] ! 0) return 0;int i 0;for(i 0; i nums.size() - 1; i){if(nums[i] ! (nums[i 1] - 1)) return nums[i] 1;} return nums[i] 1;}
};
对于第三种解法是比较差劲的因为还是注意许多细节问题比如需要先排序还要判断1 2的这种情况那么对于异或来说就很不错了
class Solution
{
public:int missingNumber(vectorint nums) {int ret 0;for(auto e : nums) ret ^ e;for(int i 1;i nums.size();i)ret ^ i;return ret;}
};
比特位计数 题目的要求是计算从0到n的所有的数中的二进制表示中1的个数将个数插入到顺序表然后返回就可以了。
那这道题不就是多次计算比特位中1的个数吗我们甚至可以直接复用上篇那道题目的代码
class Solution
{
public:int countone(int n){int x 0;while(n){n (n - 1);x;}return x;}vectorint countBits(int n) {vectorint v;for(int i 0; i n; i){v.push_back(countone(i));}return v;}
};
只出现一次的数字III 这道题目无非就是找单身狗plus版本而已就是缺失的数字嘛对吧
我们需要找到两个数那么异或整个数组肯定是少不了的异或了之后剩余的是两个数的异或结果那么我们如何分离出来呢
我们可以结合基本题目 提取最低位的1提取出来之后两个只出现一次的数字在该位上一定是不同的因为异或出来结果是1其他的数也异或掉了所以一定是一个为1一个为0。
那么我们利用这个特点将数组中的每个数组和最低位的数字一运算一下就可以得到结果了因为没有要求顺序所以我们可以直接输出。
class Solution
{
public:vectorint singleNumber(vectorint nums) {//先将整个数组异或int ret 0;for(auto e : nums) ret ^ e;//获取最低位的1-实际上是分组// int low_bit ret -ret;int low_bit (ret INT_MIN ? ret : ret (-ret));//开始分组int ans1 0, ans2 0;for(auto e : nums){if(e low_bit) ans1 ^ e;else ans2 ^ e;}return { ans1, ans2 };}
};
以上就是位运算的多个题目解析。 感谢阅读
