C++【面试重要题目】 只出现一次的数字的集合.
文章目录
- 前言
- 一、前提要点补充
- 二、题集
- 总结
前言
本篇笔者将会对 cpp 中比较有意思的类型题目进行细致讲解 . 这类题同时也是面试中比较重要的算法题 , 其算法思想需要学者掌握.
以下题目均来自力扣
一、前提要点补充
● 几个运用运算符
因为笔者介绍的题目均会用到二进制相关知识 , 所以涉及一些操作符的知识 , 以下给出补充 !
◎ & (按位与)
▶ 作用 : 本操作符通常用于提取 或 检查某些特定的二进制位.
▶ 规则 : 记忆法 – 两个都为真才为真
● 两个位都为 1 时 , 结果为 1
● 有一个位为 0 时 , 结果为 0
▶ 代码介绍
#include <iostream>
using namespace std;
//按位& 操作符
// & --- 一般用于提取 \ 检查 二进制位
int main()
{
int a = 3;
//二进制: 32位 , 这里笔者省略写 ----- 0011 - 3
//判断最低位比特位是 0 还是 1 ?
//对最低位进行标志 , 要判断最低位这里我们的思路就是将该数 & 1 , 因为1的二进制是 0001
int maska = a & 1; // 0011 & 0001 ---- 0001 - 1
if (maska == 0)
cout << "0" << endl;
else
cout << maska << endl;
return 0;
}
◎ | (按位或)
▶ 作用 : 本操作符通常用于设置某些特定的二进制位 , 也常用于二进制位恢复整数的操作.
▶ 规则 : 记忆法 – 一个为真就为真
● 两个位都为 0 时 , 结果为 0
● 有一个位为 1 时 , 结果为 1
▶ 代码介绍
#include <iostream>
using namespace std;
int main()
{
int a = 2;
//二进制: 32位 , 这里笔者省略写 ----- 0010 - 2
//将该数的最低位比特位置为 1
//因为要给最低位赋值,我们考虑用 | , 但是一般都是和 1结合,因为1的二进制位是 0001
int maska = a | 1; // 0010 | 0001 ---- 0011 - 3
//输出
cout << maska << endl;
return 0;
}
重点总结 : 一般 & 可以用来提取进制位 , | 用于复原操作位 .
◎ ^ (异或)
▶ 作用 : 可以用于数字的消除
▶ 规则 :
● 两个位相同时 , 结果为 0 ----- 相同为0
● 两个位不同时 , 结果为 1 ----- 相异为1
● 0 ^ 任何数都为它本身
● 满足交换律
▶ 代码介绍
#include <iostream>
using namespace std;
int main()
{
int a = 1;
int b = 2;
int c = 1;
int ret = a ^ b ^ c;
// 1 ^ 2 ^ 1 -- 满足交换律 -- 1 ^ 1 ^ 2 -- 0 ^ 2 -- 2
cout << ret << endl;
return 0;
}
▶ 面试题
不创建第三个变量, 完成两个变量的交换.
题目中要求不创建第三个变量 , 还要完成交换 , 以我们常规的思路 , 交换变量就是依靠一个临时变量 ,但这个思路就被 Pass 掉了 , 所以这里就引出了一个新的思路 , 用 ^ 操作符.
#include <iostream>
using namespace std;
int main()
{
int a = 1;
int b = 2;
cout << "交换前 a : " << a << endl;
cout << "交换前 b : " << b << endl;
a = a ^ b; // a = 1 ^ 2
b = a ^ b; // b = a ^ b ^ b = a
a = a ^ b; // a = a ^ a ^ b = b
cout << "交换后 a : " << a << endl;
cout << "交换后 b : " << b << endl;
return 0;
}
◎ << 和 >> (左移操作符和右移操作符)
这里注意与流提取和流插入操作符区分 , 当涉及二进制时 , 这里的 << \ >> 就代表了用于进制的 左移 和 右移了.
▶ 左移操作符
规则 : 左边抛弃 , 右边补 0
▶ 右移操作符
右移分为两种 : 逻辑右移 , 算术右移.
逻辑右移 : 左边用 0 填充个 , 右边直接抛弃.
算术右移 : 左边用原该数值的符号位填充 , 右边直接丢弃.
区分 那么什么时候用逻辑右移 , 什么时候用算术右移呢 ?
可以发现 , 逻辑右移与数值的符号无关.
故:
● 当处理无符号数时 , 用逻辑右移
● 当处理有符号数时 , 用算术右移
以上就是基本知识的铺垫 : 如下为本篇重要内容 , 题目均可点击跳转 .
二、题集
◎ 只出现一次的数字 |
◎ 只出现一次的数字 ||
◎ 只出现一次的数字 |||
讲解
◎ 只出现一次的数字 |
这里笔者就不附图片了 , 直接对本题进行描述 .
本题的要求很简单 : 只有一个数字出现一次 , 其余均出现两次 , 要求 : 返回只出现一次的元素.
▶ 算法思路
抓住题中字眼 : 两次
关于两次 , 我们可以考虑一种思路就是用二进制 , 目的是对出现两次的数字消除 , 只留下出现一次的数字.这个思路
正好符合 ^ 操作符的规则 , 相同异或为0 , 不同的为1 , 0 ^ 任何数都为自己.
▶ OJ代码
class Solution {
//依据题 , 只有一个数字出现一次 ,其余出现两次 ,考虑用 ^
public:
int singleNumber(vector<int>& nums) {
int res = 0;
//把所有元素异或就是出现一次的元素
for(auto e: nums)
{
res ^= e;
}
// 此时的 res 就是出现一次的那个数字
return res;
}
};
◎ 只出现一次的数字 ||
明显的可以看到本题的难度有所上升 , 但要是说通过该题那就是相当容易了, 直接一个暴力遍历也可解决问题 , 但这里笔者给出新的思路.
▶ 算法思路
依据 只出现一次的数字 | 题的思想 , 用二进制 , 那么本题也同样 , 可以用二进制的思想来进行.
首先 : 题目是 : 只有一个数字出现一次 , 其余数字出现三次 , 如果单纯的用 ^ 就会返现不可行了.
因为异或操作符的本质就是 % 2 .
抓题目字眼 : 三次 , 那么怎么对这个三 下手 , 只留下 一 呢 ?
不妨这样想:
● 对于出现三次的数字来说 , 要转化成其二进制 , 二进制都是 0 \ 1 组成 , 那么把这些元素的二进制对应的二进制位相加 , 则 : 对应位的和一定是 3 的倍数(即 : %3 == 0).
● 但当加入出现一次的数字后 , 其在某一比特位上是 0 , 则不会对该比特位上的和有影响 , 但当该比特位是 1 时就对该比特位的和有影响了, 则 : 这个比特位对应的数就是 %3 的余数了.
举例 : nums = [2,2,3,2]
▶ OJ代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
//用于存放出现一次的数
int res = 0;
//判断对应位二进制的和是否为3的倍数
for(int i = 0; i < 32 ; ++i)
{
int count = 0; //记录每一个对应比特位的和
for(auto e: nums)
{
//这里涉及得到每一个二进制位,根据笔者之前的前提知识结论,一般 & 是提取二进制位,都是与 1相关
//故可以思考方向如下: 每一位对应的二进制位 & 1 就是对应的该位的二进制位
//例如: 2 ---- 0010 , 要得到 2 的第0位
// (2 >> i) & 1 , (i = 0,1,2,3,4...32),这样可以得到2的每一位
// 当 i = 0 时, 0010 >> 0 -- 0010 & 0001 --- 0000 -- 0(i = 0,时该位为0)
// 当 i = 1 时, 0010 >> 1 -- 0001 & 0001 --- 0001 -- 1(i = 1,时该位为1)
count += (e >> i) & 1;
}
//判断对应位二进制的和是否为3的倍数
if(count % 3) // != 0 , 证明该位属于出现一次数字的第 i 位比特位
{
//那么就要把第 i 位置为1,,即笔者前提知识结论,一般 | 是可以给对应二进制位赋值
// 1 << i --- 把第 i 位变成 1
res |= 1 << i;
// i = 0 , 1 << 0 --- 0001 --- 1 , 第1位为1
// i = 1 , 1 << 1 --- 0010 --- 2 , 第2位为1
}
}
return res;
}
};
◎ 只出现一次的数字 |||
▶ 算法思路
本题又是第一题的变题.
题目描述: 恰好有两个元素只出现一次，其余所有元素均出现两次。要求: 返回出现两次的两个数.
● 本题除了出现两次的两个数以后 , 其余均出现两次 , 这我们可以考虑 ^ 操作符 将出现两次的数全部抵消.
● 思路转化为 :异或全部元素 , 这样就把出现两次的元素全部异或掉了 , 那么最后一次的异或就是出现一次
的两个数进行异或.
● 但我们的目的是找出现一次的两个数 , 在进行一次全部异或操作后把两个出现一次的元素异或成了一个值.
这时就要想办法把这两个值还原出来.
● 那么要区分两个数就要把两个数分为两组 .
▶ OJ代码
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int xoxALL = 0;
//对所以元素进行异或,最后一次的异或就是两个出现一次的数的异或操作
for(auto e :nums)
{
xoxALL ^= e;
}
//xoxALL 为最后一次异或的结果,进行区分标志
//例如: 3 , 5要区分的位置是第2位,要得到第2位一般考虑 &
// xoxALL = 6 , -xoxALL = -6;
// 0110 - 6
//~0110+1 -- 1001+1 -- 1010 --- -6
// 0110 & 1010 --- 0010 - 2
//判断溢出:当 xoxALL 为INT_MIN 时,对其取反 + 1就超过了整型表达范围了
int mask = (xoxALL == INT_MIN) ? INT_MIN: xoxALL & (-xoxALL);
//判断
int type1 = 0 , type2 = 0;
for(auto e:nums)
{
if(e & mask) // !=0 为一组
type1 ^= e;
else
type2 ^= e;
}
return {type1,type2};
}
};
总结
以上为只出现一次的数字的题目集合 , 是比较重要的题目 ,希望学者认真理解 !