力推C语言必会题目终章（完结篇）-Toy模板网

这篇具有很好参考价值的文章主要介绍了力推C语言必会题目终章（完结篇）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力推C语言必会题目终章（完结篇）,c语言,开发语言

W...Y的主页 😊

代码仓库分享 💕

今天是分享C语言必会题目最终章，全部都是硬货，大家都坐好准备开始喽！！！

编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次

例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。

数据范围： 0 <= n <= 500

输入描述：输入一行没有空格的字符串。

输出描述：输出输入字符串中范围在(0~127，包括0和127)字符的种数。

OJ链接【牛客网题号： HJ10 字符个数统计】

示例：输入：abc 输入：aaa

输出：3 输出：1

这道题非常简单，ASCII码的范围为127，我们只需要创建一个char类型的数组进行全部初始化为0，然后将字符作为数组下标在数组中进行标记，若数组中没有标记过表示第一次出现，进行计数，否则表示重复字符。

示例：查表法， "aaa" ，首先把a字符( ascii 值为 97 )作为下标，将标记数组的第 97 位置 1 ，下次如果还有 a 字符出现，到下标 'a' 或者 97 的位置一看是1就表示a已经统计过了，使用if进行判断即可成功。

下面为代码实现：
#include <stdio.h>

int main() {
    char tmp[501] = {0};
    while(scanf("%s", tmp) != EOF)
    {
        char mark[128] = {0};
        int count = 0;
        char *ptr = tmp;
        while(*ptr)
        {
            if(mark[*ptr] != 1)
            {
                count++;
            }
            mark[*ptr] = 1;
            ptr++;
        }
        printf("%d\n", count);
    }
    return 0;
}

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

OJ链接【 leetcode 题号：169. 多数元素】

示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length

1 <= n <= 5 * 104

进阶：尝试设计时间复杂度为 O（n）、空间复杂度为 O（1）的算法解决此问题。

解法一：

首先我们得清楚这个数组中一定会有一个元素出现次数大于等于n/2，所以当我们排序后再取中间的元素返回一定是多数元素。（只需要极少量的代码即可完成）

时间复杂度O(nlogn),空间复杂度O(1)。
#include <stdio.h>
#include<string.h>
#include<stdlib.h>

int compar(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}


int majorityElement(int* nums, int numsSize){
    qsort(nums, numsSize,sizeof(int), compar);
    
    return nums[numsSize / 2];
}
进阶解法二：

一个数组中有一个数字出现次数大于 n/2 ，从第 0 个字符开始，假设它就是最多的那个数字，遇到相同的数字则计数 +1 ，遇到不同的则计数 -1 ，其实就是互相消耗，等到计数为 0 的时候，表示本次互拼完毕，从下一个字符重新开始互拼，但是归根结底出现次数大于 n/2 的这个数字数量更多，因此也是最后保留的字符。

示例： "23335" 首先从字符 2 开始计数 1 ，遇到 3 ，不同则 -1 ，互拼消耗重新从剩下的 "335" 开始的过程，这时候保存的字符为 3 ，遇到 3 则计数 +1 ，遇到5则计数 -1 ，在计数不为 0 时，走到末尾保存的字符就是个数超过 n/2 的字符。

这种方法不容易被想到，但是优化了时间复杂度。
int majorityElement(int* nums, int numsSize){
    int count = 1;
    int tmp = nums[0];
    for(int i = 1; i < numsSize; i++)
    {
            if(tmp == nums[i])
            {
                count++;
            }
            else
            {
                count--;
            }
            if(count == 0)
            {
                tmp = nums[i+1];
            }
    }
    return tmp;
}

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

数据范围：两个数都满足 0≤n≤1000

OJ链接【牛客网题号： JZ65 不用加减乘除做加法】

进阶：空间复杂度 O(1)，时间复杂度O(1)

示例：输入：1,2 返回值：3

十进制相加思想： 15+07 ，先计算不考虑进位的相加结果 12 （因为 5+7 的不考虑进位的结果是 2 ，遇 10 进位嘛），然后计算进位 5+7 进位是 10 ，则 10 与 12 再次相加，得到 22 ，进位为 0 ，则计算到此结束。

这里使用二进制求和完成，思想类似，但是二进制计算相加和进位不需要使用 + 符号

二进制相加思想：与十进制相同，先计算不考虑进位的相加结果（ 0+0 得 0 ， 1+1 进位得 0 ， 1+0 得 1 ），使用异或可以取得；然后计算相加的进位结果（同 1 的位置左移一位即可），使用相与后左移取得。

示例：

5 0101 + 7 0111 不考虑进位的相加结果 0101^0111 -> 0010 相加的进位 0101&0111 -> 0101 因为进位左移得到 1010

1010 + 0010 不考虑进位的相加结果 1010 ^ 0010 -> 1000 相加的进位 1010 & 0010 -> 0010 因为进位左移得到 0100

1000 + 0100 不考虑进位的相加结果 1000 ^ 0100 -> 1100 相加的进位 1000 & 0100 -> 0000 进位为0结束运算。
int Add(int num1, int num2 ) {
   int sum = 0;
   while(num2 != 0)//进位不为0则持续与相加结果进行相加
   {
    sum = num1 ^ num2;//进位不为0则持续与相加结果进行相加
    num2 = (num1 & num2) << 1;//同1的位相加则会进位
    num1 = sum;
   }

   return num1;
}

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

OJ链接【 leetcode 题号：485. 最大连续 1 的个数】

示例：输入：[1,1,0,1,1,1] 输出：3

解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

这道题思路比较简单，统计连续1的个数，遇到0时表示连续中断，判断如果当前的统计数大于之前最大的则替换，然后继续下一个位置开始的统计即可。
int findMaxConsecutiveOnes(int* nums, int numsSize){
    int max = 0;
    int count = 0;
    for(int i = 0; i < numsSize; i++)
    {
        if(nums[i] == 1)
        {
            count++;
            if(max < count)
            {
                max = count;
            }
        }
        else
        {
            count = 0;
        }
    }
    return max;
}

求输出n以内(含n)完全数的个数。完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。

例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。

注意：本题输入含有多组样例。

输入描述：输入一个数字n 输出描述：输出不超过n的完全数的个数

OJ链接【牛客网题号： HJ56 完全数计算】

示例：输入：1000 7 100 输出：3 1 2

这道题的关键在于完全数的判断：完全数指的是一个数字的所有约数的和和自身相等。我们只需要从 1 开始将这个数的约数相加求和即可。

约数就是能够被数字整除，而这里简化的一个思路是数字能够被整除，则除数和结果就都是约数，这种思路下，只需要从1计算到平方根即可

比如：数字 8 ，能够整除 2 ，结果是 4 ，则除数 2 和结果 4 都是约数，而这两个只需要一次计算判断即可。

需要注意的是 4，9，25... 这种，除数和结果相同的情况，则除数或者结果只相加一次就够了。
#include <stdio.h>
#include<math.h>
int is_perfect_num(int num)
{
int sum = 1;
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {//判断是否能够整除i，能整除则i和结果都是约数
sum += i; //与除数相加
if (i != sqrt(num))//防止除数和结果相同的情况下重复相加
sum += num / i; //与相除结果相加
}
}
if (sum == num) return 1;
return 0;
}
int main()
{
int n;
while(~scanf("%d", &n)){
int count = 0;
for(int i = 2; i <= n; i++) {//对n以内的数字都进行判断是否是完全数，注意1不参与判断
if (is_perfect_num(i)) count++;
}
printf("%d\n", count);
}
return 0;
}

数列的定义如下：数列的第一项为n，以后各项为前一项的平方根，求数列的前m项的和。输入描述：输入数据有多组，每组占一行，由两个整数 n(n<10000) 和 m(m<1000) 组成，n和m的含义如前所述。

输出描述：对于每组输入数据，输出该数列的和，每个测试实例占一行，要求精度保留2位小数。

OJ链接【牛客网题号： ZJ16 数列的和】

输入：
81 4
2 2
输出：
94.73
3.41
求取一个数字的平方根可以使用数学库中的 double sqrt(double num) 函数完成，接下来只需要从数字自身开始进行求和并在求和后将 n 自身计算成为自身的平方根即可。
#include <stdio.h>
#include<math.h>
int main() {
    double m, n;
    while(scanf("%lf %lf", &n, &m) != EOF)
    {
        double sum = 0;
        while(m-- > 0)
        {
            sum +=n;
            n = sqrt(n);
        }
        printf("%.2lf\n",sum);
    }
    return 0;
}

现在有一个长度为 n 的正整数序列，其中只有一种数值出现了奇数次，其他数值均出现偶数次，请你找出那个出现奇数次的数值。

输入描述：第一行：一个整数n，表示序列的长度。第二行：n个正整数ai，两个数中间以空格隔开。

输出描述：一个数，即在序列中唯一出现奇数次的数值。

OJ链接【牛客网题号： KS33 寻找奇数】

示例：输入：5 2 1 2 3 1 输出：3

异或：二进制比特位相同则0，不同则1.

异或法：两个相同的数字异或得到的是0，基于这个思路，这道题对数组中的所有数据进行逐一异或就可以解决得到奇数次的数字，因为偶数次的数字都被异或成为0了，最后单独保留了奇数次的数字。
#include <stdio.h>

int main() {
    int n;
    while(~scanf("%d", &n))
    {
        int num = 0, tmp = 0;
        //对每个数字进行异或，出现偶数次的就会异或为0了，而奇数次刚好剩下的就是对应数字
        for (int i = 0; i < n; i++)
         {
            scanf("%d", &tmp);
            num ^= tmp;
        }
        printf("%d\n", num);
    }
    return 0;
}

给定一个长度为n的数组 nums ，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = 负无穷小

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

OJ链接【牛客网题号： NC107 寻找峰值】

示例：输入：[2,4,1,2,7,8,4] 返回值：1

说明：4和8都是峰值元素，返回4的索引1或者8的索引5都可以

输入：[5,3,4,2,6] 返回值：0

说明：-1作为下标或者n下标位置都表示负无穷小，则0号下标5是峰值，或者4号下标6也是峰值

方法一：

先将数组中首位进行特殊处理，如果满足题中要求直接返回对应下标，如果不满足条件只需要判断数组中当前元素与下一个元素大小即可，如果当前元素大于下一元素则返回当前元素下标即可，反之则继续循环。
int findPeakElement(int* nums, int numsLen ) {
    if (numsLen == 1 || nums[0] > nums[1]) 
        return 0;
    if (nums[numsLen-1] > nums[numsLen-2]) 
        return numsLen-1;
        int a = 0;
    for(int i = 1; i < numsLen-1; i++)
    {
        if(nums[i] > nums[i+1])
        {
            a = i;
            break;
        }
    }
    return a;
}
方法二：

二分思想，中间比右边大，认为从右往左半边递增，则把 right 不断向左靠拢 right=mid ，注意不能是 mid-1 ，因为这个位置有可能就是峰值点。

直到遇到中间比右边小了，意味着数据开始递降了，则 left 向右偏移， left=mid+1 ; 而一旦 mid+1 位置大于了 right ，意味着刚好这个 mid+1 位置，是一个左半边-右往左递降，右半边-右往左递增的点，就是一个峰值点。

示例： int arr[] = {3, 5, 4, 4, 3, 2, 1} , 这个数组中两边边界都是非峰值点

int left = 0, right = 6;

left=0,right=6,mid=3: arr[3]=4 > arr[4]=3, 则right = mid = 3; //从右往左是递增的 left=0,right=3,mid=1: arr[1]=5 > arr[2]=4, 则right = mid = 1; //从右往左是递增的 left=0,right=1,mid=0: arr[0]=3 < arr[1]=5, 则left = mid + 1 = 1; //从右往左开始递降了

left > right 退出循环，返回left，也就是1号下标位置。

代码实现：
int findPeakElement(int* nums, int numsLen ) {
    if (numsLen == 1 || nums[0] > nums[1]) 
        return 0;
    if (nums[numsLen-1] > nums[numsLen-2]) 
        return numsLen-1;
    int left = 0, right = numsLen - 1, mid;
    while(left < right) {
        mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1])//中间比右边小，意味着右边肯定有个峰值
            left = mid + 1;
        else //否则在左边包括当前位置肯定有个峰值
            right = mid;
    }
    return left;
}