大家好！我是沐曦希💕
给大家介绍一款超牛的斩获大厂offer利器——牛客网
1. 小乐乐与字符串
题目链接： BC119 小乐乐与字符串
思路
1.暴力枚举超时。
2.抓住“CHN”字符串只有三个字符这个特点。
3.统计C的数量countC
4.每遇到一个H字符，就能构成countC数量的CH串，countCH += countC
5.每遇到一个N字符，就能构成countCH数量的CHN串，所以ans += countCH
6.最后的结果就是ans
解法一：创建一个数组来存储该字符串，通过指针变量来访问该字符串，并通过指针变量不断加一来访问所有的字符串，并通过if来判断指针变量所指的字符是否为C,H,N来是否加一
解法二：创建一个数组来存储该字符串，通过for或者while语句来实现访问所有的字符串。
代码
//code1
#include<stdio.h>
int main()
{
char s[8001] = {'\0'};
gets(s);
char* ps = s;
long long count = 0;
long long c = 0;
long long h = 0;
while (*ps != '\0')
{
if (*ps == 'C')
{
c++;
} else if (*ps == 'H')
h += c;
else if (*ps == 'N')
count += h;
ps++;
}
printf("%lld\n", count);
return 0;
}
//code2
#include <stdio.h>
#include <string.h>
int main()
{
char str[8005];
gets(str);
long long i,cnt_c=0,cnt_h=0,cnt_n=0;
for(i=0;str[i]!='\0';i++)
{
if(str[i]=='C') cnt_c++;
else if(str[i]=='H') cnt_h+=cnt_c;
else if(str[i]=='N') cnt_n+=cnt_h;
//printf("%c",str[i]);
}
printf("%lld\n",cnt_n);
}
2.单词倒排
题目链接:HJ31 单词倒排
思路
定义一个字符指针数组，用于保存每个单词的起始字符地址，接下来将非字母字符全部替换成为字符串结尾标志，则单词字符字母遇到结尾就结束了，相当于把一个字符串以非字母字符进行切割成为了多个字符串，最终对字符指针数组进行逆序打印每个单词即可。
代码
#include <stdio.h>
#include <string.h>
int main()
{
char str[10001] = { 0 };//字符串最长10000
int row = 0;
while (gets(str) > 0)
{
char* ptr = str;
char* word[10000] = { NULL };
while (*ptr != '\0')
{
//如果是个字母字符，则是单词的起始字符
if (('z' >= *ptr && *ptr >= 'a') || ('Z' >= *ptr && *ptr >= 'A'))
{
word[row++] = ptr;//保存每个单词的起始地址
//把本次的单词字母字符走完，直到遇到非字母字符
while (*ptr != '\0' &&
(('z' >= *ptr && *ptr >= 'a') || ('Z' >= *ptr && *ptr >= 'A')))
{
ptr++;
}
continue;//不能继续向下，因为下边的ptr++会跳过当前的非字母字符
}
*ptr = '\0';//把非字母的数据全部替换为结尾标志
ptr++;
}
for (int i = row - 1; i >= 0; i--)
{
printf("%s ", word[i]);//针对所有单词的起始地址逆序开始打印即可
}
printf("\n");
}
return 0;
}
3.寻找峰值
题目链接:NC107 寻找峰值
思路
暴力破解： 遍历数组，从 [1，n-1] 号位置开始，哪个位置的数据大于上一个数据和下一个数据即可。
更优思想：二分思想，中间比右边大，认为从右往左半边递增，则把 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) {
//边界情况处理，1个元素前后都是负无穷 以及 0号位置大于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, 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;
}
4.写在最后
那么就到这里了。
