力扣刷题训练
前言
这里的oj题全都是接口型 也就是只给出一个函数 填写即可
提示：以下是本篇文章正文内容，下面案例可供参考
一、剑指 Offer 56 - II. 数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 示例 1： 输入：nums = [3,4,3,3] 输出：4 示例 2： 输入：nums = [9,1,7,9,7,9,7] 输出：1
int singleNumber(int* nums, int numsSize){
int i=0;
int j=0;
int count=0;
for(i=0;i<numsSize;i++)
{
count=0;
for(j=0;j<numsSize;j++)
{
if(nums[i]==nums[j])
{
count++;
}
}
if(count==1)
{
return nums[i];
}
}
return NULL;
}只需要遍历 判断count是否为1 为1就返回 这道题难度竟然是中等 没有标记时间复杂度为多少 是在很容易做 给大家信心
二、面试题 17.04. 消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？ 注意：本题相对书上原题稍作改动
示例 1： 输入：[3,0,1] 输出：2
示例 2： 输入：[9,6,4,2,3,5,7,0,1] 输出：8
int missingNumber(int* nums, int numsSize){
int i=0;
int sum=0;
for(i=0;i< numsSize;i++)
{
sum^=(nums[i]);
}
for(i=0;i<numsSize+1;i++)
{
sum^=i;
}
return sum;
return 0;
}这道题标记是简单 如果异或学的不好 无从下手 异或: 相同为0 相异为1 0到n共有n+1个数 而题中的0到n个数 中间缺少一个 所以是n个数 本题分为两步: 1.将输入（中间缺一个的所有数）全部异或在一起 赋值给sum 2. 将没有缺得0到n个数 与sum异或在一起
三、剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例 1：
输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1] 示例 2：
输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* singleNumbers(int* nums, int numsSize, int* returnSize){
int*ptr=(int*)malloc(2*sizeof(int));
int ret=0;
int i=0;
for(i=0;i<numsSize;i++)//第一步
{
ret^=nums[i];
}
int n=0;
for(i=0;i<32;i++)//第二步 因为第一步两者异或 一定有一位是1
{
if((ret>>i)&1==1)// 从右向左 依次向右移位 跟1判断是否当前位为1
{
n=i;//如果是1就返回
break;
}
}
int num1=0;
int num2=0;
for(i=0;i<numsSize;i++)//第三步
{
if((nums[i]>>n)&1==1)
{
num1^=nums[i];
}
else
{
num2^=nums[i];
}
}
ptr[0]=num1;//一定要注意的是 不要将ptr[0]和ptr[1]直接放在循环中异或 会报错
ptr[1]=num2;
*returnSize=2;//返回的是两个值
return ptr;
}此题难度为中等，感觉这个才是真的中等 需要得依然是异或 相同为0 ，相异为1 分为三步: 1.将所有的值异或，得到就是单个的两个数的异或 相异为1 所以一定有一位是1 .... 2.我们想到就是通过二进制位中的同位1/0区分两个不同的数 ... 3.先把要判断的数组移位到能够判断1/0的位上面 如果是1就返回sum1中 ,进行异或 如果为0就返回sum2中,进行异或 因为把不同的数放在不同的数组中 而数组中的其他数都是成对出现的，都可以异或为0 即sum1中就返回 一个数 sum2中就返回另一个数
腾讯云开发者
