目录
题目一：
题目二：
题目三：
题目四：
题目五：
题目六：
题目七：
题目八：
题目九：
题目十：
题目十一：
题目十二：
题目十三：
题目十四：
题目十五：
题目十六：
题目十七：
题目十八：
题目十九：
题目二十：
题目二十一：
题目二十二：
题目二十三：
题目二十四：
题目二十五：
题目二十六：
题目二十七：
题目二十八：
题目二十九：
题目三十
题目一：
题目：打印从1到最大的n位数
题目内容：
- 输入数字 n ，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3 ，则打印出 1、2、3 一直到最大的 3 位数 999 。
- 用返回一个整数列表来代替打印
- n 为正整数
【牛客网】打印从1到最大的n位数
思路讲解：
- 可以将n当成位数，如n为3，则最高位是3位数。
- 那得到最高位数的最大数，然后依次打印即可。如3位数的最大数是999。
- 那么如何得到呢？我们可以进行拆分一下，如果是1位数，那最大数是9，2位数最大数是99，3位数最大数是999。那给每一位数乘10，如3位数，将每一位数乘10，1×10×10×10，那最后会得到4位数的最小数，即10000，那再减1，则得出3位数的最大数。
- 故我们可以得出一个公式，n位数的最大数为：10^n - 1
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int* printNumbers(int n, int* returnSize)
{
*returnSize = (int)pow(10, n) - 1; //确定最大的数字,//pow函数-->求次幂数，第一个参数是底数，第二个参数是指数
int* arr = (int*)malloc(sizeof(int) * (*returnSize));//申请足够大小的空间
for (int i = 0; i < *returnSize; i++) {
arr[i] = i + 1;//下标从0开始，而数值从1开始
}
return arr;
}
int main()
{
int n = 0;
scanf("%d", &n);
int i = 0;
int* Size = &i;
int* res = printNumbers(n, Size);
for (int i = 0; i < *Size; i++)
{
printf("%d ", *(res+i));
}
return 0;
}题目二：
题目：HJ76 尼科彻斯定理 《OJ牛客网 尼科彻斯定理》
题目内容：
验证尼科彻斯定理，即：任何一个整数m的立方都可以写成m个连续奇数之和。
例如：
1^3=1
2^3=3+5
3^3=7+9+11
4^3=13+15+17+19
输入一个正整数m（m≤100），将m的立方写成m个连续奇数之和的形式输出。
数据范围：1≤m≤100
输入描述：
输入一个int整数
输出描述：
输出分解后的string
示例1
输入：6
输出：31+33+35+37+39+41
思路讲解：
- 想计算m的立方由哪几个奇数组成的，首先要计算出m的起始奇数。
- 起始奇数计算公式：m × (m-1) + 1
推导过程：
奇数起始项规律：
首先所有奇数项构成一个差值为2的等差数列， 1 3 5 7 9 ....
其次，1的起始奇数是第1个等差数列项，2的起始奇数是第2个等差数列项，3的起始奇数是第4个等差数列项... 形成规律： 1 2 4 7....，而他们的差值分别是1 2 3 4 5...，所以第n项就是一个从1开始到n-1的等差数列之和+1
因此当有了需求m的立方，首先计算他的第一个奇数项是总体的第几个 。
等差数列求和公式 Sn=n(a1+an)/2 m * (m - 1) / 2
等差数列第n项公式 an=a1+(n-1)d 1 + （(m * (m - 1) / 2) + 1 - 1) * 2
最终得到m的立方的表达式起始奇数： m * (m - 1) + 1
- 接着求出m的起始奇数，并进行存储，这里要求输出一个字符串，那该怎么把整形存储到字符串中呢，这里介绍一个库函数：sprintf
sprintf：
- 将格式化数据写入字符串
- 第一个参数要传一个字符指针，即字符串的地址
- 第二个参数为格式化符号，与printf输出函数一样，进行格式化输出时，需要制定类型对应的格式化符。
- 之后的参数，根据格式化符号进行填写，如%d则写入整形，依次类推。
- 可以看看cplusplus官方对sprintf的解释：sprintf
- 最后将剩余的m-1个奇数写入字符串即可。
int main()
{
int a;
char arr[1024] = { 0 };
while (scanf("%d", &a) != EOF)
{
int start = a * (a - 1) + 1; //计算起始奇数
//将起始奇数写入字符串中
sprintf(arr, "%d", start); //sprintf库函数，将格式化数据写入字符串
//将剩余的a-1个奇数写入字符串中
for (int i = 1; i < a; i++)
{
sprintf(arr, "%s+%d", arr, start += 2);
}
printf("%s\n", arr);
}
return 0;
}题目三：
题目：HJ97 记负均正
描述：
首先输入要输入的整数个数n，然后输入n个整数。输出为n个整数中负数的个数，和所有正整数的平均值，结果保留一位小数。
0即不是正整数，也不是负数，不计入计算。如果没有正数，则平均值为0。
数据范围：1<=n<=2000
输入的整数都满足：∣val∣≤1000
输入描述：
首先输入一个正整数n，
然后输入n个整数。输出描述：
输出负数的个数，和所有正整数的平均值。
思路：
- 遍历数组，元素<0，则进行统计。
- 元素>0时，对正整数进行相加求和，并且统计正整数的个数。
- 循环结束后，打印负数个数和计算正整数平均值。
- 需要注意当数组没有正整数时，0.0 / 0 会得出一个 -nan(ind)，为什么呢？因为在C语言中尝试用
0.0 / 0这样的表达式进行除法运算会导致一个运行时错误，因为除以零是未定义行为，因此循环结束后，我们要进行判断。
#include <stdio.h>
int main() {
int a = 0;
while (scanf("%d", &a) != EOF) {
int count = 0; //统计负数的个数
double flag = 0.0; //计算正数的个数
double sum = 0.0; //计算正数之和
int arr[2000] = { 0 }; //存放输入的a个数
for (int i = 0; i < a; i++) {
scanf("%d", &arr[i]);
//统计负数的个数
if (arr[i] < 0) {
count++;
continue;
}
//计算所有正整数之和
if (arr[i] > 0) {
flag++;
sum += arr[i];
}
}
//如果没有正数，则平均值为0.0
if (!flag)
{
printf("%d %.1lf\n", count, 0.0);
}
else
{
printf("%d %.1lf\n", count, sum / flag);
}
}
return 0;
}题目四：
题目：JZ11 旋转数组的最小数字
描述：
- 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
- 数据范围：1≤n≤10000
- 数组中任意元素的值: 0≤val≤10000
- 要求：空间复杂度：O(1) ，时间复杂度：O(logn)
示例1
输入：[3,4,5,1,2]
返回值：1
示例2
输入：[3,100,200,3]
返回值：3
思路：
- 如果不追求时间复杂度，可以使用暴力求解，即循环遍历数组，找出最小值，但这样的时间复杂度：O(n)
- 效率最高的方法为：二分法
- 二分法，就是二分查找（折半查找法），我们知道二分查找是在一个有序数组中查找某一个数。在该题，可以运用二分查找的思想，因为该题规定的数组时一个非降序数组，那也就是说，是升序的，只不过将数组进行了旋转。
- 对于旋转数组，通俗理解就是将数组前n个元素移到后面，如[1,2,3,4]，旋转后[3,4,1,2]，等等类似情况。
- 通过观察，我们可以总结出三种情况：
- 情况一：中间元素大于右边元素时，如 [3,4,5,1,2]，这种情况数组中的最小值一定在mid的右边。说明最小值在
mid的右边（不包括mid），因此更新left = mid + 1。- 情况二：中间元素小于右边元素时，如[4,5,1,2,3]或[5,1,2,3,4]，这种情况数组中的最小值一定位于mid或mid的左边。说明最小值在
mid的左边或者就是mid本身，因此更新right = mid。- 情况三：中间元素等于右边元素时，如[1,0,1,1,1]，这种情况则无法确定最小值的位置，缩小右边范围。right--。
//方法一：暴力求解，循环遍历数组，找最小值（时间复杂度O(n)）
int minNumberInRotateArray(int* nums, int numsLen)
{
int min = 0;
for (int i = 0; i < numsLen; i++) {
if (i == 0) {
min = nums[i];
}
if (min > nums[i]) {
min = nums[i];
}
}
return min;
}
//方法二：二分法进行查找最小数 时间复杂度：O(logn)
int minNumberInRotateArray(int* nums, int numsLen)
{
//特殊情况一：数组个数为0
if (numsLen == 0) return 0;
int left = 0;//左边数组下标
int right = numsLen - 1;//右边数组下标
int mid = 0; //数组中间元素下标
//特殊情况而：数组没有进行旋转操作
if (nums[right] > nums[left]) return nums[left]; //返回首元素
//需要循环，什么时候结束呢？
当left>=right的时候，说明最小值已查找到
while (left<right)
{
//计算中间元素的下标
mid = left + (right - left) / 2;
情况一：中间元素大于右边元素
if (nums[mid] > nums[right])
{
//此时最小值一定在右边，那mid和mid左边的元素则不需要查找了
left = mid + 1;
}
//情况二：中间元素小于右边元素
else if (nums[mid] < nums[right])
{
此时说明最小值是mid或mid的左边
right = mid;
}
//情况三：中间元素等于右边元素
else
{
//这时候需要缩小范围 right--;，注意不能是
//left++，//因为是非降序数组，所以要缩小右边范围，把较小值向右推，符合我们的判断规则。
right--;
}
}
//此时left>=right
//虽然为>=，但left与right总是相等，因此这里返回nums[left]和nums[right]都可以
return nums[left];
}
int main()
{
int nums[] = { 3,4,5,1,2 };
int min = minNumberInRotateArray(nums, sizeof(nums) / sizeof(nums[0]));
printf("%d\n", min);
return 0;
}
题目五：
题目：错误的集合
描述：
集合
s包含从1到n的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。给定一个数组
nums代表了集合S发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例1：
输入：nums = [1,2,2,4] 输出：[2,3]示例2：
输入：nums = [1,1] 输出：[1,2]输入范围：
2 <= nums.length <= 1041 <= nums[i] <= 104
思路：
- 一个从1~n的集合中某一个元素丢失，并且变成某个元素的重复值。
- 首先创建一个大小为n+1的数组，该数组用于标记丢失数组中的元素，数组内的元素均为1，以丢失数组里的元素为下标，进行标注1.为什么数组的大小是n+1，因为元素是从1~n，需要将1~n当成下标，对应数组内的位置进行标记
- 当发现该数组内的元素为1时，那说明是重复的元素。
- 那就创建一个大小为2的数组，将重复元素进行存储。
- 怎么找到丢失元素呢？因为题目中是一个1~n的集合，那也就是说，将丢失数组-重复数后，该数组的元素之和相当于就比1~n之和少了丢失数组。因此分别计算出两个数组的元素之和。
- 最后将丢失元素存储到Res数组中
int* findErrorNums(int* nums, int numsSize, int* returnSize) {
//用于标记元素，为什么大小是numsSize+1呢？
//因为是1~n的整数，为了方便从下标0开始标记，所有设置numsSize
int *New_nums = (int*)calloc(numsSize+1, sizeof(int));
*returnSize = 2;//两个元素，第一个为重复整数，第二个为丢失整数
int *Res = (int*)calloc(*returnSize, sizeof(int)); //用于存放两个整数
int New_Sum = 0; //用于计算1~numsSize元素之和
int Nums_Sum = 0;//用于计算nums数组里元素之和
for(int i=0; i<numsSize; i++)
{
//判断New_nums[nums[i]]处是否为1，如果为1，代表已经被标记过
//则为重复整数
if(New_nums[nums[i]] == 1) {
Res[0] = nums[i];
}
New_nums[nums[i]] = 1;//做标记,将nums里的元素作为New_nums下标，进行标记为，表示该元素。
New_Sum+=i+1; //计算1~numsSize之和
Nums_Sum+=nums[i];//计算nums数组的元素之和
}
free(New_nums);
//因为nums数组里存在一个相同的元素，我们已将重复元素放置在了Res[0]中
//将nums元素之和 - 重复元素后，此时nums数组中正好差了丢失元素
//因此与1~numsSize之和相减就得到丢失元素
Res[1] = New_Sum - (Nums_Sum-Res[0]);
return Res;
}题目六：
题目：密码检查
描述：
小明同学最近开发了一个网站，在用户注册账户的时候，需要设置账户的密码，为了加强账户的安全性，小明对密码强度有一定要求：
- 密码只能由大写字母，小写字母，数字构成；
- 密码不能以数字开头；
- 密码中至少出现大写字母，小写字母和数字这三种字符类型中的两种；
- 密码长度至少为8
现在小明受到了n个密码，他想请你写程序判断这些密码中哪些是合适的，哪些是不合法的。
输入描述：
输入一个数n，接下来有n(n≤100)行，每行一个字符串，表示一个密码，输入保证字符串中只出现大写字母，小写字母和数字，字符串长度不超过100。
输出描述：
输入n行，如果密码合法，输出YES，不合法输出NO
示例1
输入：
1 CdKfIfsiBgohWsydFYlMVRrGUpMALbmygeXdNpTmWkfyiZIKPtiflcgppuR输出：
YES
思路：
- 这道题只需要将字符串从头到尾的每种字符（大写字符，小写字符，数字，其他字符）分别统计出来后。然后逐个判断是否符合条件即可
- 而条件的判断包含有：
- 长度不小于8
- 不能以数字开头
- 只能包含字母和数字
- 大小写和字符必须具备两种以上
- 这道题可以关注如何判断大小写和字符必须具备两种以上这个条件是如何做的，主要是判断统计的三种字符类型是否大于0，大于0就为真，小于或等于就为假，真为1，假为0，三个字符类型相加>1就符合要求了。
#include <stdio.h>
#include <string.h>
int main() {
int n;
while (scanf("%d", &n) != EOF) {
for (int i=0; i<n; i++) {
char password[101];
scanf("%s", password);
//如果密码长度少于8位
if (strlen(password) < 8) {
printf("NO\n");
continue;
}
//密码不能以数字开头
if (password[0]>='0' && password[0]<='9') {
printf("NO\n");
continue;
}
char *tmp = password;
int upper = 0;
int lower = 0;
int number = 0;
int other = 0;
//统计密码中各种字符的个数
//密码只能由大写字母、小写字母、数字构成
while (*tmp != '\0') {
if (*tmp>='A' && *tmp<='Z') upper++; //统计密码中大写字母个数
else if (*tmp>='a' && *tmp<='z') lower++; //统计密码中小写字母个数
else if (*tmp>='0' && *tmp<='9') number++; //统计密码中数字个数
else other++; //统计其它个数
tmp++;
}
//判断other是否大于0.如果是,则说明密码不是由大写字母、小写字母、数字构成
if (other > 0) {
printf("NO\n");
continue;
}
//密码中至少出现大写字母，小写字母和数字这三种字符类型中的两种
//对三种字符类型判断，刚才对密码中三种字符进行了统计
//判断每一种字符类型是否大于0，如果有两种以上大于0，则YES
//如果没有，则NO。技巧是真为1，假为0，相加>1则符合
if ((upper>0)+(lower>0)+(number>0) < 2) {
printf("NO\n");
continue;
}
//此时密码都符合
printf("YES\n");
}
}
return 0;
}题目七：
题目：数字在升序数组中出现的次数
描述：
给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
要求：
时间复杂度O(logn);空间复杂度O(1)
数据范围：
0<=n<=1000; 0<= k <= 100; 数组中每个元素的值满足0<= val <= 100
示例1:
输入：[1,2,3,3,3,3,4,5],3
返回值：4
示例2：
输入：[1,3,4,5],6
返回值：0
思路：
- 因为时非降序数组，那就是升序数组，当出现多个k时，那k必然是连续出现的
- 因此我们分别找到出现k的起始下标，和结束下标，进行相减+1操作，就能得出k的出现个数
- 对于这种有序数组的操作，并且要求时间复杂度O(logn)，一般使用二分查找思想。
- 当进行找k的起始和结束下标时，会出现三种情况：
- mid == left/mid == right，这种情况可以确定mid就是k的起始/结束下标了，因为当mid == left/mid == right时，left的左边不可能出现k/right的右边不可能出现k，那left/right就是k的起始/结束下标了，那mid自然也是了。
- nums[mid-1]/nums[mid+1] != k，这种情况很好理解，当nums[mid-1]/[mid+1]不是k时,那mid结束起始/结束下标
- 以上两种情况都不符和的话，那就说明mid下标还不是k的起始/结束下标了，那就继续找：right = mid-1/left = mid + 1
//用于找到k的最左坐标/最右坐标
int Count(int* nums, int len, int k, int flag)
{
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
//当k>num[mid]时，则左边不用再找
if (k > nums[mid]) {
left = mid + 1;
}
//当k<nums[mid]时，则右边不用再找
else if (k < nums[mid]) {
right = mid - 1;
}
//此时nums[mid] == k
//则根据flag值，找k的最左/最右坐标
else {
//找k的最左坐标
if (flag == 0) {
//如果mid == left，说明此时的mid下标为k的最左边索引
//如果nums[mid-1] != k，说明此时的mid下标为k的最左边索引
//因为这是一个有序数组,当k出现多次时,必然时连续的,当mid-1表示k,则为k的起始下标
if (mid == left || nums[mid - 1] != k) return mid;
//如果没有进行返回，则说明此时mid找到的k并不是最左位置的k
//继续向左寻找k的最左下标
else right = mid - 1;
}
//找k的最右坐标
else {
//如果mid == right，说明此时的mid下标为k的最右边索引
//如果nums[mid+1] != k，说明此时的mid下标为k的最右边索引
//因为这是一个有序数组,当k出现多次时,必然时连续的,当mid-1表示k,则为k的结束下标
if (mid == right || nums[mid + 1] != k) return mid;
//如果没有进行返回，则说明此时mid找到的k并不是最右位置的k
//继续向右寻找k的最左下标
else left = mid + 1;
}
}
}
//此时还没进行return的话，则表示左边/右边都没有k
return -1;
}
int GetNumberOfK(int* nums, int numsLen, int k) {
int left = Count(nums, numsLen, k, 0);
int right = Count(nums, numsLen, k, 1);
if (left == -1 && right == -1) {
return 0;
}
//k的最右下标-最左边下标 + 1 等于k出现的次数
return right - left + 1;
}题目八：
题目：面试题 05.06. 整数转换 - 力扣（LeetCode）
描述：
整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
示例1：
输入：A = 29 （或者0b11101）, B = 15（或者0b01111） 输出：2示例2：
输入：A = 1，B = 2 输出：2A，B范围在[-2147483648, 2147483647]之间
思路1：
- 对一个数进行按位与1操作，能的到该数最低位的二进制是1还是0
- 分别对A、B进行按位与1，进行比较，则二进制位不同就是要修改的位，就能的出要修改几个位
- 比较完后，更新二进制最低位：对A、B进行右移操作。
- 因为二进制由32个bit位组成，因此循环32次
int convertInteger(int A, int B) {
//对一个数进行按位与1操作，能的到该数最低位的二进制是1还是0
//分别对A、B进行按位与1，进行比较，则二进制位不同就是要修改的位，就能的出要修改几个位
//比较完后，更新二进制最低位：对A、B进行右移操作。
//因为二进制由32个bit位组成，因此循环32次
int count = 0;
for (int i = 0; i < 32; i++) {
int tmp_a = A & 1;
int tmp_b = B & 1;
if (tmp_a != tmp_b) {
count++;
}
A >>= 1;
B >>= 1;
}
return count;
}思路2：
- 先将A和B进行异或操作，因为异或：相同为0，相异为1
- 对异或后的二进制的最低位进行判断是否为1，因为相异为1，那为1的位置，就是A和B不同的。
- 不断更新最低位。
//思路2
int func2(int num) {
int count = 0;
for (int i = 0; i < 32; i++)
{
//对num进行右移i，一个32次，移动后进行&1，结果为1就是不同的位
if ((num >> i) & 1)
{
count++;
}
}
return count;
}
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a,&b);
int count2 = func2(a^b);
printf("思路2：%d\n", count2);
return 0;
}题目九：
题目：747. 至少是其他数字两倍的最大数 - 力扣（LeetCode）
描述：
给你一个整数数组
nums，其中总是存在 唯一的 一个最大整数 。请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回
-1。示例1：
输入：nums = [3,6,1,0] 输出：1 解释：6 是最大的整数，对于数组中的其他整数，6 至少是数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。示例2：
输入：nums = [1,2,3,4] 输出：-1 解释：4 没有超过 3 的两倍大，所以返回 -1 。提示：
-
2 <= nums.length <= 500 <= nums[i] <= 100nums中的最大元素是唯一的
两种思路：
思路1：暴力求解
- 找出最大值。
- 依次进行比较
思路2：
- 找出最大值和次大值。
- 如果最大值大于次大值的2倍，则其它元素必然也大于
//思路1：暴力求解
int dominantIndex(int* nums, int numsSize) {
//先找出数组中最大值
int max = 0;
int flag = 0; //标记max在数组里的下标
for(int i=0; i<numsSize; i++){
//假设第一个数就为最大值
if(i == 0)
max = nums[i];
if(max < nums[i]){
max = nums[i];
flag = i;
}
}
//依次判断max是否符合至少是数组中每个其他数字的两倍
for(int i=0; i<numsSize; i++) {
if(i == flag) {
continue;
}
//如果有元素的两倍大于max的话，则不符合条件。返回-1
if(nums[i] * 2 > max){
return -1;
}
}
//此时说明至少是数组中每个其他数字的两倍，返回max的下标
return flag;
}//思路2：
int dominantIndex(int* nums, int numsSize) {
//1、找出最大值和次大值
int flag = 0; //记录最大值的下标
int max, sec;
//给max和sec赋初值
//max肯定是比sec大的
if (nums[0] > nums[1])
{
max = nums[0];
flag = 0;
sec = nums[1];
}
else
{
max = nums[1];
flag = 1;
sec = nums[0];
}
//2、找出真正的max和sec
//因为给max和sec赋初值时，已经比较过第1第2个元素了，因此从第3个元素开始
for (int i = 2; i < numsSize; i++)
{
if (nums[i] > max)
{
//sec就变为max
sec = max;
max = nums[i];
flag = i;
}
//这条判断语句是防止nums[0]正好就是最大值的情况
//因此就要在剩余元素中找出次大值，不可能保持初始值的nums[1]
else if (nums[i] > sec)
{
sec = nums[i];
}
}
//判断max是否大于sec的两倍
if (max>=sec*2)
{
return flag;
}
return -1;
}题目十：
题目：349. 两个数组的交集 - 力扣（LeetCode）
描述：
给定两个数组
nums1和nums2，返回 它们的 交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的范围：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
思路：
- 使用一个map标记数组。
- 首先将nums1数组里的元素作为下标，索引到map数组相对应的位置，并且赋值为1
- 接着再将nums2数组里的元素作为下标，索引到map数组相对应的位置，判断该位置是否为1
- 如果是，则进入判断体，然后将map里对应的位置进行++操作，接着将对应元素放入交集数组中
- 对map对应位置进行++操作的原因：因为可能数组里不只有一个重复的元素，可能有多个，但只保存一个
- 因此，只需要保存第一次进入判断题的元素就好了，将对于map位置的1修改后，后面再有相同的元素则进入不了判断体
- 列如：nums1[1, 2, 2, 1] nums2[2,2] map[0,1,1]，如果我们不修改map对应位置1的值，则会出现这种情况：
- map[nums[0]]为1，记录一次，map[nums[1]]为1，又记录一次，如果在map[nums[0]]为1，记录后，对该位置进行修改
- map[0,1,2]，那下一次map[nums[1]]-->map[2]不等于1了，就避免了重复元素
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int map[1001] = { 0 };
int* res = (int*)calloc(1000, sizeof(int));
if (res == NULL) {
return NULL;
}
*returnSize = 0;
//通过nums1数组里的元素，在map数组里做标记
for (int i = 0; i < nums1Size; i++) {
map[nums1[i]] = 1; //做标记
}
//拿map数组跟nums2的元素进行判断，是否为1
for (int i = 0; i < nums2Size; i++) {
//如果nums2里的元素当成map下标，发现也是1，那就说明交集
if (map[nums2[i]] == 1) {
map[nums2[i]]++; //这里是防止重复，只需要每个元素只需要一次就够了，
//一次后改变map里对应元素的大小，下次相同元素就进入不了
res[*returnSize] = nums2[i]; //将交集数据存储起来
*returnSize += 1;
}
}
return res;
}题目十一：
题目：图片整理_牛客题霸_牛客网 (nowcoder.com)
描述：
Lily上课时使用字母数字图片教小朋友们学习英语单词，每次都需要把这些图片按照大小（ASCII码值从小到大）排列收好。请大家给Lily帮忙，通过代码解决。
Lily使用的图片使用字符"A"到"Z"、"a"到"z"、"0"到"9"表示。
输入描述：
一行，一个字符串，字符串中的每个字符表示一张Lily使用的图片。
输出描述：
Lily的所有图片按照从小到大的顺序输出
示例：
输入：Ihave1nose2hands10fingers
输出：0112Iaadeeefghhinnnorsssv
思路：
- 创建一个字符数组，用于存储输入的字符。
- 输入字符可以用gets(指针)或者getchar()
- 这里使用getchar()，什么时候停止输入呢？当getchar() == \n时，为什么？因为输入会先存储到缓冲区中，在最后我们按下回车\n，也会放入缓冲区中，因此getchar() == \n时，说明已将想输入的字符存放入字符数组中。
- 冒泡排序对字符数组进行排升序。
- 冒泡排序思想：相邻数据之间进行比较交换，将较大或较小的数据向后推到数组末尾，然后开始下一轮次大数据的冒泡过程。嵌套循环，外层控制趟数，内层控制一趟的比较次数。
#include <stdio.h>
#include <string.h>
int main() {
char str[1000] = {0};
//'A'~'Z'的Ascll码值范围：65~90
//'a'~'z'的Ascll码值范围：97~122
//'0'~'9'的Ascll码值范围：48~57
int i = 0;
char ch = {0};
//输入字符串
//输入操作会先输入到缓冲区中，注意最后的\n也会输入到缓冲区中
//当getchar()读取到\n时，说明已经将字符存储进了str中
while ((ch = getchar()) != '\n') {
str[i++] = ch;
}
//对字符数组进行排序
//冒泡排序：相邻两个元素进行比较
//核心思想：外层控制趟数，内层控制一趟的比较次数
for (size_t i = 0; i < strlen(str) - 1; i++) {
for (size_t j = 0; j < strlen(str) - 1 - i; j++) {
//升序
if (str[j] > str[j + 1]) {
char tmp = str[j];
str[j] = str[j + 1];
str[j + 1] = tmp;
}
}
}
//打印排完序的字符串
puts(str);
return 0;
}题目十二：
题目：724. 寻找数组的中心下标 - 力扣（LeetCode）
描述：
给你一个整数数组
nums，请计算数组的 中心下标 。数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为
0，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回
-1。示例 1：
输入：nums = [1, 7, 3, 6, 5, 6] 输出：3 解释： 中心下标是 3 。 左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ， 右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。示例 2：
输入：nums = [1, 2, 3] 输出：-1 解释： 数组中不存在满足此条件的中心下标。示例 3：
输入：nums = [2, 1, -1] 输出：0 解释： 中心下标是 0 。 左侧数之和 sum = 0 ，（下标 0 左侧不存在元素）， 右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。数据范围：
1 <= nums.length <= 104-1000 <= nums[i] <= 1000
思路：
- 统计左边元素之和和统计右边元素之和。
- 对数组的每一个元素都要进行判断统计左右两边之和。
- 当左右之和相等时，则为中心下标。
- 即使有多个中心下标也不怕，因为题目规定返回最左边的，因此当发现一个时，就返回了。
- 即使左边第一个元素为中心下标或者右边第一个元素为中心下标也没影响，因为统计左边和统计右边的变量初始化为0，因此会返回0.
int pivotIndex(int* nums, int numsSize) {
//1、分别统计左边数组元素和右边数组元素
int LeftSum = 0;
int RightSum = 0;
//外层循环用于提供数组nums每个元素
for(int i=0; i<numsSize; i++){
LeftSum = 0;
RightSum = 0;
//内层循环用于统计每个nums每个元素的左边之和和右边之和
for(int j=0; j<numsSize; j++){
//当下标j<下标i时，表示统计i元素左边之和
if(j<i) {
LeftSum+=nums[j];
}
//当下标j>下标i时，表示统计i元素右边之和
else if(j>i){
RightSum+=nums[j];
}
}
//当发现LeftSum == RightSum时，说明此时的i为中心下标
if(LeftSum == RightSum){
return i;
}
}
//此时说明没有中心下标
return -1;
}题目十三：
题目：字符个数统计_牛客题霸_牛客网 (nowcoder.com)
描述：
编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。
数据范围： 1≤𝑛≤500 1≤n≤500
输入描述：
输入一行没有空格的字符串。
输出描述：
输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。
示例1
输入：abc
输出：3
示例2
输入：aaa
输出：1
思路：
- 元素标记法
- 创建一个数组大小为128的数组，为什么128，因为题目规定字符的Ascll码值0~127
- 依次输入字符，并且将输入的元素作为标记数组的下标，进行赋值为1。
- 最后遍历标记数组，统计该数组内有几个1。
#include<stdio.h>
#include <string.h>
int main() {
char str[500] = { 0 };
int tmp[128] = { 0 };
char ch;
int i = 0;
int k = 0;
while ((ch = getchar()) != '\n' && ch >= 0 && ch <= 127 ) {
str[i++] = ch;
//标记字符数组内的所有元素
tmp[str[k++]] = 1;
}
//统计tmp中有几个1
int count = 0;
for (int i = 0; i < 128; i++) {
if (tmp[i] == 1) {
count++;
}
}
printf("%d\n", count);
return 0;
}题目十四：
题目：169. 多数元素 - 力扣（LeetCode）
描述：
给定一个大小为
n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
思路：
- 题目中要求在数组中找出出现最多次的元素，查看该元素出现次数是否大于 (数组元素个数/2)
- 题目也给出可以假设该数组是一个非空数组，并且一定存在多数元素。因此该题实际上就是求数组中哪个元素出现的次数最多
- 因此可以从数组中的首元素开始统计，往后进行判断，如发现相同元素进行+1，发现不相同元素-1，当次数为0时，
- 更换为其它元素，进行判断，直到数组遍历结束，此时的元素就是多数元素。
- 核心思想就是抵消，如：[2,2,3,3,3,3] 将从2开始，因此一开始可以将count赋值为1，依次往后进行判断，当遇到3时，count为2
- 那就进行-1操作，又遇到3，又进行-1操作，此时的count为0，因此已经出现和2元素个数相同的另外一个元素了，此时相当于从0开始，
- 因此就要改变统计对象，因此就要指向下标为4的3开始，继续进行统计,当遍历结束后，此时的多数元素就是该元素3.
int majorityElement(int* nums, int numsSize) {
//假设nums首元素就是数组中重新最多次的元素
int tmp = nums[0];
int count = 1;
for (int i = 1; i < numsSize; i++) {
//如果tmp与后面元素相等，则+1
if (tmp == nums[i]) count++;
//反之，--，相当于相互抵消
else {
count--;
//当count == 0时，说明已经出现>=tmp的数了，因此要更换
if (count == 0) {
tmp = nums[i + 1];
}
}
}
//此时的tmp就是数组内最多的元素，也就是多数元素
return tmp;
}题目十五：
题目：728. 自除数 - 力扣（LeetCode）
描述：
自除数 是指可以被它包含的每一位数整除的数。
- 例如，
128是一个 自除数 ，因为128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。自除数 不允许包含 0 。
给定两个整数
left和right，返回一个列表，列表的元素是范围[left, right]内所有的 自除数 。示例 1：
输入：left = 1, right = 22 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]示例 2:
输入：left = 47, right = 85 输出：[48,55,66,77]提示：
1 <= left <= right <= 104
思路：
- 自除数：就是一个数，能被该数的每一位整除。
- 因此我们可以循环的获取到该数的每一位，然后对该数进行整除。
- 判断该数每一位是否出现为0或者不能进行整除的情况。
- 获取一个数最后一位，就给该数取模10，获取一个去除最后一位的后的数，就给该数除上一个10。
- 因此当发现该数等于0时，结束循环，说明该数为自除数。
/*
思路：
自除数的判断，数字的每一位都能被源数字整除，有了这个规则，咱们只需要循环获取一个数字的每一位，然后与源
数字取模判断是否为 0 ，如果中间有任意一次不为 0 ，则表示不是自除数。
接下来，只需要遍历数组中的每个元素，判断是否是自除数即可，如果是则加入到返回数组中。
*/
#include <stdlib.h>
int* selfDividingNumbers(int left, int right, int* returnSize) {
*returnSize = 0;
int* list = (int*)calloc(right - left + 1, (right - left + 1) * sizeof(int));
if (list == NULL)
return NULL;
//外层循环为每一个数
for (int i = left; i <= right; i++) {
int tmp = i; //将该数赋值给tmp
//while循环的判断条件为tmp真，即不为0
while (tmp) {
//得到该数的最后一个数
int n = tmp % 10;
//如果最后一位数为0或者不能对该整除该数，则不是自除数
if (n == 0 || i % n != 0) {
break;
}
//得到除最后一位数的其它数。
tmp = tmp / 10;
}
//当tmp等于0时，说明i为自除数
if (tmp == 0) {
list[(*returnSize)++] = i;
}
}
return list;
}题目十六：
题目：238. 除自身以外数组的乘积 - 力扣（LeetCode）
描述：
给你一个整数数组
nums，返回 数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积 。题目数据 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请 不要使用除法，且在
O(n)时间复杂度内完成此题。示例 1:
输入: nums =[1,2,3,4]输出:[24,12,8,6]示例 2:
输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]提示：
2 <= nums.length <= 105-30 <= nums[i] <= 30- 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
思路：
- 初始化：首先，使用calloc函数分配一个与输入数组nums大小相同的整数数组tmp，并将所有元素初始化为1。这是为了避免后续乘法操作中的任何非预期影响。如果内存分配失败，则返回NULL。
- 计算前缀乘积：使用变量left来存储当前元素左侧所有元素的乘积。从数组的第二个元素开始遍历，对于每个位置i，将left乘以nums[i - 1]（即当前元素左侧的元素），然后将结果乘以tmp[i]（此时tmp[i]的值为1，但后续会更新）。
- 计算后缀乘积：同时，使用变量right来存储当前元素右侧所有元素的乘积。从数组的倒数第二个元素开始遍历，对于每个位置i，将right乘以nums[numsSize - i]（即当前元素右侧的元素），然后将结果乘以tmp[numsSize - i - 1]（对称地更新结果数组）。
- 返回结果：最后，设置returnSize为numsSize，即结果数组的大小，并返回tmp数组。
#include <stdlib.h>
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
int* tmp = (int*)calloc(numsSize, numsSize * sizeof(int));
if (tmp == NULL) return NULL;
for (int i = 0; i < numsSize; i++)
{
tmp[i] = 1;
}
int left = 1;
int right = 1;
for (int i = 1; i < numsSize; i++) {
left *= nums[i - 1];//计算前缀乘积
right *= nums[numsSize - i];//计算后缀乘积
tmp[i] *= left; //更新结果数组
tmp[numsSize - i - 1] *= right; //更新结果数组
}
*returnSize = numsSize; //设置返回数组大小
return tmp;
}题目十七：
题目：不用加减乘除做加法_牛客题霸_牛客网 (nowcoder.com)
描述：
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
数据范围：两个数都满足 −10≤𝑛≤1000−10≤n≤1000
进阶：空间复杂度 𝑂(1)O(1)，时间复杂度 𝑂(1)O(1)示例1
输入：1,2
返回值：3
示例2
输入：0,0
返回值：0
思路：
- 十进制相加思想：如7+15，可以拆分为：07 + 15，不进位，0+1，7+5，值为12。
- 然后再计算进位的值，也就是5+7每进位的值，那就是10.
- 再将12和10进行相加，等于22。
- 再进行计算进制的值，发现为0，因此最后的值就为22.
- 本题通过二进制操作，与十进制相同思想。
- 先计算不考虑进位的相加结果：异或，因为 0+0 得 0 ， 1+1 进位得 0 ， 1+0 得 1（相当于 不进位+进位值）
- 再计算相加的进位结果：按位与+左移1。
- 循环，直到计算相加的进位结果为0，则代表异或后的值为正确的值
int Add(int num1, int num2) {
while (num2 != 0) {
int tmp = num1 ^ num2; //计算不进行进位的操作后的值
num2 = (num1 & num2) << 1; //计算相加的进位结果（同 1 的位置左移一位即可），使用相与后左移取得
num1 = tmp;
}
return num1;
}题目十八：
题目：448. 找到所有数组中消失的数字 - 力扣（LeetCode）
描述：
给你一个含
n个整数的数组nums，其中nums[i]在区间[1, n]内。请你找出所有在[1, n]范围内但没有出现在nums中的数字，并以数组的形式返回结果。示例 1：
输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]示例 2：
输入：nums = [1,1] 输出：[2]提示：
n == nums.length1 <= n <= 1051 <= nums[i] <= n
思路：
- 使用标价法。
- 定义一个tmp数组，该数组大小为numsSize+1.初始化为全1，numsSize+1是为了方便之后的下标
- 遍历nums，将nums里的元素作为下标，访问tmp对应的值，如果该位置大于或等于1，则对该位置++。
- 最后再遍历tmp，查看哪些位置为1，注意要从下标1开始遍历，因为是1~n，当位置里的值为1时，那循环变量i的值就是消失的数字了。放入res数组即可
#include <stdlib.h>
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
int* res = (int*)calloc(numsSize, numsSize * sizeof(int));
if (res == NULL) return NULL;
int tmp[numsSize + 1];
*returnSize = 0;
//标记法:1~n
for (int i = 0; i < numsSize + 1; i++) {
tmp[i] = 1;
}
//查看nums数组内缺少了哪些元素
for (int i = 0; i < numsSize; i++) {
if (tmp[nums[i]] >= 1)
tmp[nums[i]]++;
}
//遍历tmp，查看哪些值是1，则该位置的下标+1就是消失的数字
for (int i = 1; i < numsSize + 1; i++) {
if (tmp[i] == 1) {
res[(*returnSize)++] = i;
}
}
return res;
}题目十九：
题目：485. 最大连续 1 的个数 - 力扣（LeetCode）
描述：
给定一个二进制数组
nums， 计算其中最大连续1的个数。示例 1：
输入：nums = [1,1,0,1,1,1] 输出：3 解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.示例 2:
输入：nums = [1,0,1,1,0,1] 输出：2提示：
1 <= nums.length <= 105nums[i]不是0就是1.
思路：
- 遍历数组，两个变量，maxCount和cur_size，maxCount存储最多1的个数cur_size用于统计1的个数。
- 元素为1就cur_size++，当元素为0，则利用三目运算符，更新maxCount。
- 注意循环结束后，还要进行一次判断，更新maxCount，因为可能出现循环结束没进入else的情况。
题目二十：
题目：完全数计算_牛客题霸_牛客网 (nowcoder.com)
描述：
完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。
输入n，请输出n以内(含n)完全数的个数。
数据范围：
1≤𝑛≤5×105
1≤n≤5×105
输入描述：
输入一个数字n
输出描述：
输出不超过n的完全数的个数
示例1
输入：1000
输出：3
思路：
- 封装一个函数用于判断是否为完全数
- 循环1~n依次判断是否为完全数。如果是则++。
- 完全数判断，%i没有余数则为该数的因子，因子之和。
- 判断因子之和是否对于该数
#include <stdio.h>
int isPerfectNumber(int n){
int sum = 0;
for(int i=1; i<n; i++){
//当n能被整除，说明i是n的因子
if(n%i == 0){
sum+=i; //计算n因子之和
}
}
if (sum == n) {
return 1;
}else {
return 0;
}
}
int main() {
int n = 0;
scanf("%d", &n);
int count = 0;
for (int i=1; i<=n; i++) {
//判断是否为完全数
if(isPerfectNumber(i)){
count++;
}
}
printf("%d\n", count);
return 0;
}题目二十一：
题目：数字颠倒_牛客题霸_牛客网 (nowcoder.com)
描述：
输入一个整数，将这个整数以字符串的形式逆序输出
程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001
数据范围： 0≤n≤2^30−1
输入描述：
输入一个int整数
输出描述：
将这个整数以字符串的形式逆序输出
示例1
输入：1516000
输出：0006151
示例2
输入：0
输出：0
思路：
将每一位数字转为字符数字：数字+字符0 == 字符数字，因为字符0的ASCll码值为48，加上数字，可以得出该数字的字符数字ASCll码值
获取每一位，n%10得到最低位，n/10得到除最低位的剩余位
依次获取最低位，放入字符数字中，就为逆序了
#include <stdio.h>
void shift(char* str,int n)
{
int i = 0;
//n为0时，表示所有位已经获取完成
while (n) {
int tmp = n%10; //获取n的最低位
*(str+i) = tmp + '0'; //数字转字符数字
n/=10; //得到除最低位的剩余位
i++;
}
}
int main()
{
int n = 0;
scanf("%d", &n);
//n的取值最大为2^32次方-1，相对应的位数为11位，字符串还有一个\0因此大小为12位。
char str[12] = {0};
//当n为0时，直接输出。
if (n == 0) {
printf("0");
}else {
shift(str,n);
printf("%s\n", str);
}
return 0;
}题目二十二：
题目：单词倒排_牛客题霸_牛客网 (nowcoder.com)
描述：
对字符串中的所有单词进行倒排。
说明：
1、构成单词的字符只有26个大写或小写英文字母；
2、非构成单词的字符均视为单词间隔符；
3、要求倒排后的单词间隔符以一个空格表示；
如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；
4、每个单词最长20个字母；
数据范围：字符串长度满足 1≤n≤10000
输入描述：
输入一行，表示用来倒排的句子
输出描述：
输出句子的倒排结果
示例1
输入：I am a student
输出：student a am I
示例2
输入：$bo*y gi!r#l
输出：l r gi y bo
思路：
定义一个字符指针数组，用于存放该字符串中每个单词的起始地址。
当遍历字符串字符时，发现不是26个大写或小写字母时，改变为字符串结束字符'\0'
最后从后到前，依次打印每个单词，并且打印后加空格
int main() {
char str[10001] = {0};
int row = 0;
while (gets(str) > 0) {
char* n = str;
char* tmp[10000] = {NULL};
while (*n != '\0') {
//判断首地址字符是否符合范围
if (*n <= 'z' && *n >= 'a' || *n <= 'Z' && *n >= 'A') {
//记录该单词的起始地址
tmp[row++] = n;
//记录完后，将指针指向超出范围的字符位置
while (*n != '\0' && (
*n <= 'z' && *n >= 'a' || *n <= 'Z' && *n >= 'A'
)) {
n++;
}
continue; //不能继续向下，因为下边的ptr++会跳过当前的非字母字符
}
//此时的字符不在规定范围，那就改为字符串的结束标志'\0'
*n = '\0';
n++;
}
//将每个单词倒排打印
for (int i=row-1; i>=0; i--) {
printf("%s ", tmp[i]); //没打印一个单词后就跟上一个空格
}
printf("\n");
}
return 0;
}题目二十三：
题目：统计每个月兔子的总数_牛客题霸_牛客网 (nowcoder.com)
描述：
有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。
例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。
一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
数据范围：输入满足1≤n≤31
输入描述：
输入一个int型整数表示第n个月
输出描述：
输出对应的兔子总数
示例1
输入：3
输出：2
思路：
该题与求第n个斐波那契数列的求法一样。
#include <stdio.h>
/*
其实就是斐波那契数列
*/
int main() {
int a = 1;
int b = 1;
int c = 1;
int n = 0;
scanf("%d", &n);
while (n>=3) {
c = a+b;
a = b;
b = c;
n--;
}
printf("%d\n", c);
return 0;
}题目二十四：
题目：数列的和_牛客题霸_牛客网 (nowcoder.com)
描述：
数列的定义如下：数列的第一项为n，以后各项为前一项的平方根，求数列的前m项的和。
输入描述：
输入数据有多组，每组占一行，由两个整数n（n<10000）和m(m<1000)组成，n和m的含义如前所述。
输出描述：
对于每组输入数据，输出该数列的和，每个测试实例占一行，要求精度保留2位小数。
示例1
输入：
81 4
2 2
输出：
94.73
3.41
思路：
- 使用C语言中库函数sqrt()方法，求一个数的平方根，类型为double
- 前m项，因此m--即可，求出每一项的平方根，最后进行相加即可
#include <stdio.h>
#include <math.h>
int main() {
double a, b;
while (scanf("%lf %lf", &a, &b) != EOF) {
double sum = 0;
while (b-- > 0) {
sum += a;
a = sqrt(a);
}
printf("%.2f\n", sum);
}
return 0;
}题目二十五：
题目：面试题 16.15. 珠玑妙算 - 力扣（LeetCode）
描述：
珠玑妙算游戏（the game of master mind）的玩法如下。
计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。作为用户，你试图猜出颜色组合。打个比方，你可能会猜YRGB。要是猜对某个槽的颜色，则算一次“猜中”；
要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。
给定一种颜色组合solution和一个猜测guess，编写一个方法，返回猜中和伪猜中的次数answer，
其中answer[0]为猜中的次数，answer[1]为伪猜中的次数。
示例：
输入： solution="RGBY",guess="GGRR"
输出： [1,1]
解释： 猜中1次，伪猜中1次。
提示：
len(solution) = len(guess) = 4
solution和guess仅包含"R","G","B","Y"这4种字符
思路：
首先要读懂题目：
- "猜中"：猜的颜色与对应槽位颜色一致
- "伪猜中"：不要求必须对应槽位一致，只需要出现过该颜色
- 但需要注意："猜中"不算作"伪猜中"
核心思路如下：
- 依次判断对应槽位是否有相同的，如果有则+1
- 创建两个大小位26的数组，当对应槽位没有相同时，则统计出现的颜色次数。
- 数组大小26是因为26个字母，统计对应颜色的个数，只需要字母-'A'即可，因为是以Ascll码值存储的，如：'B' - 'A' == 66 - 65 == 1，那就是第二个元素
- 最后，遍历数组，比较26个位置中，对应位置，取较小的一方。这是因为，即使一个颜色出现多次了，但只需要取一次就够了。
int* masterMind(char* solution, char* guess, int* returnSize){
*returnSize = 2;
int* arr = (int*)calloc(*returnSize,*returnSize * sizeof(int));
int Tmp_solution[26] = {0};
int Tmp_guess[26] = {0};
for(int i=0; i<4; i++){
//判断是否有正好猜中的情况，即槽位颜色与猜的颜色一致
if(solution[i] == guess[i]){
arr[0]+=1; //arr数组第一个元素存放猜中的次数
}else{ //如果对应的槽位颜色与猜的颜色不一致，则统计solution和guess各自颜色的个数
//26个字母，因此可以看作数组中26个位置，分别对应值26个字母
//字符是以Ascll码值进行存储的，因此一个字母减去'A'那就对应着数组中该字母的位置
//如：'B' - 'A' == 66-65 => 1 也就是第二个元素，那就是B了
Tmp_solution[solution[i] - 'A']+=1;
Tmp_guess[guess[i] - 'A']+=1;
}
}
//这里来计算"伪猜中"的次数
//"伪猜中"：颜色一致，但槽位不一致。
//但需要注意，已经"猜中"的不算
for(int i=0; i<26; i++){
//取较小值。
//因为只有4个槽，即使有多个相同颜色，较小的值最大也只会是1次
arr[1]+= Tmp_solution[i]>Tmp_guess[i] ? Tmp_guess[i] : Tmp_solution[i];
}
return arr;
}题目二十六：
题目：两数之和
描述：
给出一个整型数组 numbers 和一个目标值 target ，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
注意：本题只需要找到第一组符合要求的数据下标即可。不需要返回多组
示例：
输入：[3,2,4],6
返回值：[2,3]
说明：因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，
又因为 下标2 < 下标3 ，所以输出[2,3]
思路：
- 遍历即可，从第一个元素开始往后依次遍历判断，直到找到出现两数之和等于目标数的情况
- 如果没有找到，则返回空
#include <stdio.h>
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize)
{
*returnSize = 2;
static int arr[2] = { 0 };
for (int i = 0; i < numbersLen; i++)
{
for (int j = i+1; j < numbersLen; j++)
{
//判断两个下标对应值相加，是否等于target目标值
if (numbers[i] + numbers[j] == target) {
//题目要求下标从1开始
arr[0] = i + 1;
arr[1] = j + 1;
return arr; //取第一次成立的下标
}
}
}
//此时返回，那就表示没有能构成两数之和的结果
return NULL;
}
int main()
{
int arr[] = {2,4,4};
int i = 0;
int* returnSize = &i;
int* sum = twoSum(arr, 3, 6, returnSize);
if (sum == NULL) return;
for (int i = 0; i < *returnSize; i++)
{
printf("%d ", sum[i]);
}
return 0;
}
题目二十七：
题目：寻找奇数_牛客题霸_牛客网 (nowcoder.com)
描述：
现在有一个长度为 n 的正整数序列，
其中只有一种数值出现了奇数次，其他数值均出现偶数次，请你找出那个出现奇数次的数值。
数据范围：
1≤n≤2×10^6
输入描述：
第一行：一个整数n，表示序列的长度。第二行：n个正整数ai，两个数中间以空格隔开。
输出描述：
一个数，即在序列中唯一出现奇数次的数值。
示例1
输入：
5
2 1 2 3 1
输出：3
示例2
输入：1
1
输出：1
思路：
本题可以利用异或的特性：相同为0，相异为1
异或有两个特点：
1、两个相同的数进行异或，结果为0
2、任何数和0进行异或，结果等于本身
因此就可以进行抵消了，当一个数出现偶次数时，最后会被抵消为0，因此相同为0
当一个数为奇数次时，最后均会变成0^这个数，那最后结果就为这个数本身，也就得到结果
#include <stdio.h>
int main() {
int n;
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;
}题目二十八：
题目：寻找峰值_牛客题霸_牛客网 (nowcoder.com)
描述：
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = −∞−∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗？
数据范围：
1≤𝑛𝑢𝑚𝑠.𝑙𝑒𝑛𝑔𝑡ℎ≤2×105 1≤nums.length≤2×105
−231<=𝑛𝑢𝑚𝑠[𝑖]<=231−1−231<=nums[i]<=231−1
如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：
示例1
输入：
[2,4,1,2,7,8,4]
返回值：
1说明：4和8都是峰值元素，返回4的索引1或者8的索引5都可以
示例2
输入：
[1,2,3,1]
返回值：
2
说明：3 是峰值元素，返回其索引 2
思路：
利用二分思想
- 找到数组中间下标，与中间下标右边元素对比
- 如果小于右边元素，那就说明右边有峰值
- 如果不小于右边元素，那左边或者中间元素可能有峰值
- 因此当left与right交叉或相等时，则left就是峰值下标。
- 当然还要排除几种特殊情况：
- 只有一个元素时，前后都是负无穷，或者有两个元素，第一个元素>第二个元素均返回0，即第一个元素为峰值
- 只有两个元素，最后一个元素>倒数第二个元素，返回numsLen-1，也就是最后一个元素
int findPeakElement(int* nums, int numsLen ) {
//边界情况1：只有一个元素，前后都是负无穷，或有两个元素，第一个元素>第二个元素
// -1位置是负无穷情况
if (numsLen == 1 || nums[0] > nums[1]) return 0;
//末尾位置数据大于上一个位置数据，而nums[numsLen]负无穷的情况
if (nums[numsLen - 1] > nums[numsLen - 2]) return numsLen - 1;
int left = 0;
int right = numsLen - 1;
int mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
//中间值小于右边，则代表右边一定有峰值
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {//反之，左边或者mid当前位置一定是峰值
right = mid;
}
}
return left;
}
题目二十九：
题目：数对_牛客题霸_牛客网 (nowcoder.com)
描述：
牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
牛牛希望你能帮他计算一共有多少个可能的数对。输入描述：
输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。
输出描述：
对于每个测试用例, 输出一个正整数表示可能的数对数量。
示例1
输入：5 2
输出：7
说明：
满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)
思路：
假设输入 n=10 , k=3 ；
当 y <=k 时，意味着任何数字取模y的结果都在 [0, k-1]之间，都是不符合条件的。
当 y = k+1=4 时，x符合条件的数字有 3,7
当 y = k+2=5 时，x符合条件的数字有 3,4,8,9
当 y = k+3=6 时，x符合条件的数字有 3,4,5,9,10
当 y = k+n时，
x小于y当前值，且符合条件的数字数量是：y-k个，
x大于y当前值，小于2*y的数据中，且符合条件的数字数量是：y-k个
从上一步能看出来，在y的整数倍区间内，x符合条件的数量就是 (n / y) * (y - k)个
n / y 表示有多少个完整的 0 ~ y区间， y - k 表示有每个区间内有多少个符合条件的数字
最后还要考虑的是6...往后这种超出倍数区间超过n的部分的统计
n % y 就是多出完整区间部分的数字个数，其中k以下的不用考虑，则符合条件的是 n % y - (k-1) 个
这里需要注意的是类似于9这种超出完整区间的数字个数 本就小于k的情况，则为0
最终公式：(n / y) * (y - k) + ((n % y < k) ? 0, (n % y - k + 1));
#include <stdio.h>
int main() {
long n, k;
while (~scanf("%ld %ld", &n, &k)) {
if (k == 0) {
printf("%ld\n", n * n);//任意数对的取模结果都是大于等于0的
continue;
}
long count = 0;
for (long y = k + 1; y <= n; y++) {
count += ((n / y) * (y - k)) + ((n % y < k) ? 0 : (n % y - k + 1));
}
printf("%ld\n", count);
}
return 0;
}题目三十：
题目：截取字符串_牛客题霸_牛客网 (nowcoder.com)
描述：
输入一个字符串和一个整数 k ，截取字符串的前k个字符并输出
数据范围：字符串长度满足
1≤𝑛≤1000
1≤k≤n
输入描述：
1.输入待截取的字符串
2.输入一个正整数k，代表截取的长度
输出描述：
截取后的字符串
思路：
截取字符串前 n 个字符，只需要将数组 n 下标位置的数据替换为字符串结尾标志即可
#include <stdio.h>
int main() {
char str[1000];
int k = 0;
scanf("%s", str);
scanf("%d", &k);
str[k] = '\0';
printf("%s\n", str);
return 0;
}关注我，后续会出更多干货！！
