leetcode 136. Single Number 、 137. Single Number II 、 260. Single Number III(剑指offer40 数组中只出现一次的数字)
2024-10-07 12:13:01
136. Single Number
除了一个数字,其他数字都出现了两遍。
用异或解决,亦或的特点:1.相同的数结果为0,不同的数结果为1
2.与自己亦或为0,与0亦或为原来的数
class Solution {
public:
int singleNumber(vector<int>& nums) {
if(nums.empty())
return -;
int res = ;
for(int i = ;i < nums.size();i++)
res ^= nums[i];
return res;
}
};
137. Single Number II
除了一个数字其他数字都出现了三遍。
因为数字为int型,就有32位。统计每个位上1的个数,然后在每位取余,余下的每位的结果肯定是那个单独的数在每位的结果
https://www.cnblogs.com/grandyang/p/4263927.html
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = ;
for(int i = ;i < ;i++){
int tmp = ;
for(int j = ;j < nums.size();j++){
tmp += (nums[j] >> i) & ;
}
res |= (tmp % ) << i;
}
return res;
}
};
260. Single Number III
有两个数字都只出现了一次,其他数字都出现了两遍。
两个只出现一次的数字在所有位中肯定有一位是不同的,所以亦或出来可以将两个数分开,剩下数无论那一位是否为1肯定都是成对出现,这个时候就可以利用136. Single Number的方法单独处理两个小的数组。findFirstOne其实就是找生成的结果第一个为1的,这个index实际上可以用第几位来表达,比如返回结果3,就是第三位。但我这样处理,直接返回第三位为1,其他位为0,方便之后直接划分数组。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> result;
if(nums.empty())
return result;
int num = ;
for(int i = ;i < nums.size();i++)
num ^= nums[i];
int index = findFirstOne(num);
vector<int> nums1,nums2;
for(int i = ;i < nums.size();i++){
if(nums[i] & index)
nums1.push_back(nums[i]);
else
nums2.push_back(nums[i]);
}
int num1 = ;
for(int i = ;i < nums1.size();i++)
num1 ^= nums1[i];
result.push_back(num1);
int num2 = ;
for(int i = ;i < nums2.size();i++)
num2 ^= nums2[i];
result.push_back(num2);
return result;
}
int findFirstOne(int num){
int index = ;
int tmp = num & index;
while(!tmp){
index = index << ;
tmp = num & index;
}
return index;
}
};
剑指offer40 数组中只出现一次的数字:
错误写法:
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int length = data.size();
if(length <= )
return;
int num = ;
for(int i = ;i < length;i++){
num = num ^ data[i];
}
int number = FindFirst1(num);
vector<int> data1;
vector<int> data2;
for(int i = ;i < length;i++){
if(data[i] & number)
data1.push_back(data[i]);
else
data2.push_back(data[i]);
}
*num1 = ;
*num2 = ;
for(int i = ;i < data1.size();i++){
*num1 ^= data1[i];
}
for(int i = ;i < data2.size();i++){
*num2 ^= data2[i];
}
}
int FindFirst1(int num){
int number = ;
int res = num & number;
while(res == ){
number << ; //这里并没有对number进行更新
res = num & number;
}
return number;
}
};
正确写法:
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int length = data.size();
if(length <= )
return;
int num = ;
for(int i = ;i < length;i++){
num = num ^ data[i];
}
int number = FindFirst1(num);
vector<int> data1;
vector<int> data2;
for(int i = ;i < length;i++){
if(data[i] & number)
data1.push_back(data[i]);
else
data2.push_back(data[i]);
}
*num1 = ;
*num2 = ;
for(int i = ;i < data1.size();i++){
*num1 ^= data1[i];
}
for(int i = ;i < data2.size();i++){
*num2 ^= data2[i];
}
}
int FindFirst1(int num){
int number = ;
int res = num & number;
while(res == ){
number = number << ;
res = num & number;
}
return number;
}
};
最新文章
- 1、开篇:公司管理经验谈 - CEO之公司管理经验谈
- Android ViewPager滑动背景渐变
- arcgis10.2.2地图服务切图具体步骤
- 如何接触学习java
- Palindrome Linked List
- [MetaHook] Load DTX texture to OpenGL
- Java设计原则:面向接口的设计
- Android(java)学习笔记201:网络图片浏览器的实现(ANR)
- 小W与网格
- 安装oracle后,Tomcat 登陆 localhost 要求用户名和密码
- 百度统计API的使用
- vue中的钩子函数的理解
- 开源播放器 ijkplayer (二) :ijkplayer倍速变调问题解决方案
- 理解 Delphi 的类(十) - 深入方法[17] - 提前声明
- JavaScript变量作用域(Variable Scope)和闭包(closure)的基础知识
- C++ STL--顺序容器(vector)
- 面试问题:你了解Java内存模型么(Java7、8、9内存模型的区别)
- Python 基础进阶
- Jenkins常见任务配置
- Elasticsearch Java API简介