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 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 #include#includeint 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 #includeint 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 42 2输出：
94.733.41求取一个数字的平方根可以使用数学库中的 double sqrt(double num) 函数完成，接下来只需要从数字自身开始进行 求和并在求和后将 n 自身计算成为自身的平方根即可。
#include #includeint 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 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 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;}
以上是本次C语言必会题目，都是些非常经典的内容，希望博主的分享对你们有帮助。
你们的支持是博主最大的动力，谢谢观看！！！