软件网站开发公司,vps建立多个网站,信用湘潭网站,搭建网站首页题一#xff1a;只出现一次的数字#xff08;1#xff09; 1.链接
136. 只出现一次的数字 - 力扣#xff08;LeetCode#xff09;
2.思想 借用位运算中异或操作符的特点#xff0c;a^a0#xff0c;0^aa先定义一个sum0就用一个循环来遍历这个数组#xff0c;每次都进行…题一只出现一次的数字1 1.链接
136. 只出现一次的数字 - 力扣LeetCode
2.思想 借用位运算中异或操作符的特点a^a00^aa先定义一个sum0就用一个循环来遍历这个数组每次都进行 sum ^ nums[i]当循环结束那么此刻sum里就是正确答案 3.代码
class Solution {
public:int singleNumber(vectorint nums) {int resultnums[0];for(int i0;inums.size()-1;i){resultresult^nums[i1];}return result;}
};
题二丢失的数字 1.链接
268. 丢失的数字 - 力扣LeetCode
2.思路 借用位运算中异或操作符的特点a^a00^aa先定义一个变量sum并初始化为0然后在利用一个for循环来处理每次循环都进行 sum^i 的操作在去遍历整个数组遍历时进行sum^nums[i]的操作最终sum就是要找的那个值 3.代码
class Solution {
public:int missingNumber(vectorint nums) {int sum0;for(int i1;inums.size();i){sum^i;}for(int i0;inums.size();i){sum^nums[i];}return sum;}
};
题三只出现一次的数字 2 1.链接
137. 只出现一次的数字 II - 力扣LeetCode
2.思路 位图的思想 前提我们让出现一次的数为a出现三次的数统称为b; 由于数据的特殊性我们可以统计这些数据用二进制表示时每个位数出现一的个数判断该位数是出现1的个数。a 的二进制在该位数时的结果是0或1而 b 的二进制在该位数时的结果3的倍数或者0则统计各个位数出现1的结果则可能是03的倍数13的倍数0001此时我们可以对其进行%3的操作结果等于1那么则就代表a在这个位是1当%3的操作结果等于1那么则就将数字在该位修改为1 由于数据范围是- 2 的31次方——2 的 31 次 方 - 1那么数据类型为int就可以进行位图思想 3.代码
class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for (int i 0; i 32; i) {int sum 0;for (auto x : nums)if (((x i) 1) 1)sum;sum sum % 3;if (sum 1)ret | (1 i);}return ret;}
};
题四只出现一次的数字 3 1.链接
260. 只出现一次的数字 III - 力扣LeetCode
2.思路 先定义一个int类型的变量 sum 并初始化为0 先遍历这个数组并进行 sum ^ nums[ i ]的操作完成遍历操作后得到的其实就是二个只出现一次的数进行异或的结果(sum)考虑异或的性质相同为0相异为1sum的二进制表示中从左往右出现的第一个1就是二个只出现一次的数 的二进制表示形式 的第一个不同处我们可以进行 sum -sum的操作这样就得到了从左往右出现的第一个1( rs 并且其它位全为0然后对数据进行分组处理按照nums [ i ] rs 等于0 和 不等于0 进行处理当不等于0时对数据进行 tmp ^ nums[ i ]的操作最终 tmp就是二个只出现一次的数的其中之一然后再将 sum ^ tmp , 就得到了另外一个数 3.代码
class Solution {
public:vectorint singleNumber(vectorint nums) {long long sum 0;for (int j 0; j nums.size(); j) {sum ^ nums[j];}long long rs sum (-sum);int tmp 0;for (int j 0; j nums.size(); j) {if (nums[j] rs)tmp ^ nums[j];}int bsum^ tmp;return {tmp, b};}
}; 题五消失的两个数字消失的数字的综合题 1.链接
面试题 17.19. 消失的两个数字 - 力扣LeetCode 2.思路 总体思路是 这个问题可以转化为题四这里其实就是一组数据其中只有二个数据只出现一次其它都出现二次那么就可以找到只出现一次的二个数据再二进制表示时第一个不同的位置然后根据这个为依据进行分组处理处理的思路就是题1 3.代码
class Solution {
public:vectorint missingTwo(vectorint nums) {int n nums.size();int ret 0;for (int i 1; i n 2; i) {ret ^ i;}int sum 0;for (int i 0; i n; i) {sum ^ nums[i];}int rsum ret ^ sum;int rs rsum (-rsum);int tmp 0, rtmp 0;for (int i 0; i n; i) {if (nums[i] rs)tmp ^ nums[i];else {rtmp ^ nums[i];}}for (int i 0; i n 2; i) {if (i rs)tmp ^ i;elsertmp ^ i;}return {rtmp, tmp};}
};
