力扣刷题训练

2022-10-26
吉林
本文字数：1538 字
阅读完需：约 5 分钟

前言

这里的 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 相异为 10 到 n 共有 n+1 个数而题中的 0 到 n 个数中间缺少一个所以是 n 个数本题分为两步:1.将输入（中间缺一个的所有数）全部异或在一起赋值给 sum2. 将没有缺得 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 中就返回另一个数