“开关是灯的日出日落，日出日落是灯的开关”

本篇是C语言刷题大杂烩，收集了笔者遇到的认为有价值的题目，本篇会持续更新~~

day01

至少是其他数字两倍的最大数

题目原文：

题意解析：

请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

个人思路：

题目要求最大元素大于等于数组其他每个元素的2倍，可能一开始就会直接想遍历数组的所有元素，然后与最大元素一一比较。其实仔细想想，只要最大元素大于等于数组中第二个较大值的2倍就行了，这样就保证了最大元素大于等于数组其他每个元素的2倍。

个人代码：

int dominantIndex(int* nums, int numsSize) {
    int m1 = -1, m2 = -1;//m1表示最大值，m2表示数组中第二个最大值
    int index = -1;//最大值下标
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > m1) {
            m2 = m1;
            m1 = nums[i];
            index = i;
        }
        else if (nums[i] > m2) {
            m2 = nums[i];
        }
    }
    return m1 >= m2 * 2 ? index : -1;//三目操作符，值得注意使用
}

两个数组的交集

题目原文：

题目解析：

找出两个数组中相同的元素，存储到动态开辟的新数组中，新数组中的元素是唯一的，不能有重复。

个人思路：

定义一个新数组，把其中一个数组的元素值当作新数组的下标，初始化新数组，这样做的目的是防止数组中的重复元素多次比较。然后把第二个数组的元素值也当作新数组的下标，遍历新数组，如果遍历结果大于0，那么此时下标就是两个元素的交集。

个人代码：

// 两个数组的交集
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int nums1Cnt[1000] = { 0 };//用于存储、比较两个数组的元素是否相等，
    int lessSize = nums1Size < nums2Size ? nums1Size : nums2Size;//节约空间
    int* result = (int*)calloc(lessSize, sizeof(int));//动态开辟数组指针
    int resultIndex = 0;//动态开辟数组下标
    int* tempNums;

    int i;

    for (i = 0; i < nums1Size; i++) {
        nums1Cnt[nums1[i]]++;//解决数组中有重复的元素
    }

    for (i = 0; i < nums2Size; i++) {
        if (nums1Cnt[nums2[i]] > 0) {
            result[resultIndex] = nums2[i];
            resultIndex++;
            nums1Cnt[nums2[i]] = 0;//防止重复元素的比较
        }
    }

    *returnSize = resultIndex;
    return result;
}

day02

多数元素

题目原文：

题目解析：

返回数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

个人思路：

投票法。先确定一个投票对象，然后遍历数组，相同元素票数加1，不同元素票数减1。因为多数元素个数多所以票数一定多。当票数为0时，此时说明该投票对象不是多数，更改投票对象。

个人代码：

int majorityElement(int* nums, int numsSize)
{

    int ans = 0;//投票对象
    int cnts = 0;//票数
    for (int i = 0; i < numsSize; i++)
    {
        if (ans == nums[i])
        {
            cnts++;
        }
        else if (cnts == 0)
        {
            ans = nums[i];
        }
        else
        {
            cnts--;

        }
    }
    return ans;
}

字符个数统计

题目原文：

题目解析：

计算字符串中含有的不同字符的个数，多个相同的字符只计算一次

个人思路：

由于字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，都是正整数，且多个相同的字符只计算一次，所以我们可以采用把字符当作数组下标的方式来存储，这样就解决了相同字符的问题。

个人代码：

int main()
{
    int i, num = 0, len;
    char a[1000];
    char b[128] = { 0 };
    gets(a);
    len = strlen(a);
    for (i = 0; i < len; i++)
    {
        if (a[i] >= 0 && a[i] <= 127)
            b[a[i]]++;
    }
    for (i = 0; i < 127; i++)
    {
        if (b[i] > 0)
            num++;
    }
    printf("%d", num);
    return 0;
}

day03

自除数

题目原文：

题目解析：

给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数 。
一个数中如果含0，由于0不能作为被除数则该数对0取余不成立，则含0的数不满足题意

个人思路：

1.创建数组：int ret=(int)malloc(sizeof(int)*(right-left+1));
此外，要返回数组大小，在判断时要记录进入数组中元素的大小
2.循环语句：对于left与right之间的元素一一进行判断（用judge函数判断）
3.judge函数：对于一个数temp进行判断：用while语句进行判断，用flag求得被除数，每进行一次取余的判断，temp就除10，此外用num记录初始的数字

个人代码：

 bool judge(int temp){
    int num,flag;
    num=temp;
    while(temp>0){
        flag=temp%10;
        temp/=10;
        if(flag==0){
            return false;
        }
        if(num%flag!=0){
            return false;
        }
    }
    return true;
} 


int* selfDividingNumbers(int left, int right, int* returnSize) 
{
    int *ret=(int*)malloc(sizeof(int)*(right-left+1));
    int count=0;
    for(int i=left;i<=right;i++){
        if(judge(i)){
            ret[count++]=i;
        }
    }
    *returnSize=count;
    return ret;

}

除自身以外数组的乘积

题目原文：

题目解析：

求除自身以外数组的乘积，返回到新数组中

个人思路：

前缀后缀法
初始化：创建一个结果数组 ra，并将所有元素初始化为 1。
前缀乘积：从左到右遍历数组，使用变量 pre 累积左侧元素的乘积。
后缀乘积：从右到左遍历数组，使用变量 suf 累积右侧元素的乘积。
组合结果：结合前缀和后缀乘积，存储在结果数组 ra 中。
返回结果：设置返回数组的大小，并返回结果数组 ra

个人代码：

// 数组中除自身以外元素的乘积
int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int *ans = malloc(sizeof(int) * numsSize);
    *returnSize = numsSize;
    ans[0] = 1;
    for (int i = 1; i < numsSize; i++) 
    {
        ans[i] = ans[i - 1] * nums[i - 1];
    }
    int suf = 1;
    for (int i = numsSize - 1; i >= 0; i--) 
    {
        ans[i] *= suf;
        suf *= nums[i];
    }
    return ans;
}

day04

不用加减乘除做加法

题目原文：

题目解析：

要解题其实很简单，我们只需要掌握 按位与、按位或、按位异或 的规则即可。

个人思路：

巧用位运算： 1、num1 & num2，与运算，得到的是2个数都是1的位置，如果进行加法，则需要进位，m =（num1 & num2）<< 1,得到进位后的数。

2、num1 ^ num2,异或，得到的是2个数1个为0另一个为1的位置，如果进行加法，则不需要进位。n = num1 ^ num2,此时如果m + n得到的就是两数之和，但不能做加法，此时我们想到了或运算。但如果将m、n直接进行或运算，无法保证不进位，于是我们重复以上的过程。

3、当n与上m得0 的时候，即再也不需要进位了，此时将m | n返回即可。

个人代码：

int Add(int num1, int num2 ) 
{
    // write code here
    while (num1) 
    { //num1不为0就表示还有进位
        int tmp = num1 ^ num2; //计算不算进位的相加结果
        num1 = (num1 & num2) <<1;//计算有进位的位置，左移1就将进位移到它该在的位置
        num2 = tmp; //将没进位的结果交给num2，直到进位为0，结束计算
    }
    return num2;
}

找到所有数组中消失的数字

题目原文：

题目解析：

求不在数组中的[1, n]的值，返回新数组。

个人思路：

第一个思路是暴力求解法，遍历[1, n]的值，然后遍历数组的元素一一比较。但是：

第二个思路是哈希表，申请空间ans，作为简单哈希表，当nums[i]出现时，将ans对应的下标至 1 ，记录出现元素，ans[nums[i]] = 1最后遍历数组ans，将未出现的元素下标保存输出，可能会疑问不是申请了额外空间吗？不满足进阶要求，但是我们可以将额外空间和输出空间合并为一个空间，即做输出又做记录

个人代码：

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize)
{
    int * ans = malloc(sizeof(int)* (numsSize+1));//申请空间，作为简易哈希表
    for(int i = 0; i< numsSize; i++)
    {
        ans[nums[i]] = 1;//记录出现元素
    }
    *returnSize = 0;
    for(int i = 1; i <= numsSize; i++)
    {
        if(ans[i] != 1)//对为出现的元素保存输出
        {
            ans[(*returnSize)++] = i;
        }
    }
    return ans;
}

day05

完全数计算

题目原文：

题目解析：

求1到n内完全数的个数，完全数：它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。

个人思路：

暴力求解法：遍历1到n，然后再遍历判断是否是完全数。时间复杂度O（n^2）

个人代码：

int main() 
{
    int n;
    while (scanf("%d ", &n) != EOF) 
    { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to 
        
        int ret = 0;
        for(int i = 1;i <= n;i++)
        {
            int count = 0;
            for(int j = 1;j < i;j++)
            {
                if(i % j == 0)
                {
                    count += j;
                }
            }
            if(count == i)
            {
                ret++;
            }
        }
        printf("%d\n",ret);
    }
    return 0;
}

最大连续 1 的个数

题目原文：

题目解析：

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

个人思路：

暴力求解，遍历数组，如果是1，count++，不是的话，先把count与之前保存的count比较，大的那个存下来，然后count置为0，继续遍历，注意，当循环结束时，还要在比较一次。

个人代码：

int findMaxConsecutiveOnes(int* nums, int numsSize) 
{
    //1.暴力求解
    int count = 0;
    int max = 0;
    for(int i = 0;i < numsSize;i++)
    {
        if(nums[i] == 1)
        {
            count++;
        }
        else
        {
            max = max > count ? max : count;
            count = 0;
        }
    }
    max = max > count ? max : count;
    return max;
}