1.贪心1.1分糖果描述一群孩子做游戏现在请你根据游戏得分来发糖果要求如下1. 每个孩子不管得分多少起码分到一个糖果。2. 任意两个相邻的孩子之间得分较多的孩子必须拿多一些糖果。(若相同则无此限制)给定一个数组 arr 代表得分数组请返回最少需要多少糖果。要求: 时间复杂度为O(n) 空间复杂度为 O(n)数据范围 1≤n≤100000 1≤≤1000示例1输入[1,1,2]返回值4说明最优分配方案为1,1,2思路:两次遍历左到右、右到左 初始化每个孩子先发 1 个糖果 左到右如果 arr[i] arr[i-1]则 candy[i] candy[i-1] 1 → 保证右边得分高的人比左边多 右到左如果 arr[i] arr[i1]则 candy[i] max(candy[i], candy[i1] 1) → 保证左边得分高的人比右边多 最后累加 candy[] 即可/** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * pick candy * param arr int整型一维数组 the array * param arrLen int arr数组长度 * return int整型 */ int candy(int* arr, int arrLen ) { // write code here int candy[arrLen]; for(int i0;iarrLen;i) { candy[i]1; } for(int i1;iarrLen-1;i) { if(arr[i]arr[i-1]) { candy[i]candy[i-1]1; } } for(int iarrLen-2;i0;i--) { if(arr[i]arr[i1]) { if(candy[i]candy[i1]) candy[i]candy[i1]1; } } int sum0; for(int i0;iarrLen;i) { sumcandy[i]; } return sum; }1.2主持调度描述有 n 个活动即将举办每个活动都有开始时间与活动的结束时间第 i 个活动的开始时间是,第 i 个活动的结束时间是,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动换句话说一个主持人参与了第 i 个活动那么该主持人在 (,) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动最少需要多少名主持人。数据范围: 1≤n≤-≤≤≤复杂度要求时间复杂度O(nlogn) 空间复杂度 O(n)示例1输入2,[[1,2],[2,3]]返回值1说明只需要一个主持人就能成功举办这两个活动思路 将开始时间、结束时间分别排序 用双指针遍历遇到开始时间就 1需要新主持人遇到结束时间就 -1主持人空闲 过程中的最大值就是答案 eg活动: [1,3], [2,4], [3,6], [5,7] 排序后: 开始时间: 1, 2, 3, 5 结束时间: 3, 4, 6, 7 指针扫描: i0(start1) → count1, max1 i1(start2) → count2, max2 i2(start3) → 先处理结束时间: end[0]3 ≤ 3 → count1, 然后 start3 → count2 i3(start5) → 先处理结束时间: end[1]4 ≤5 → count1, end[2]65不动, 然后 start5 → count2 最大重叠数 2需要2名主持人#include stdlib.h // 比较函数升序 int cmp(const void*a,const void*b) { int x *(int*)a; int y *(int*)b; if (x y) return -1; if (x y) return 1; return 0; } int minmumNumberOfHost(int n, int** startEnd, int startEndRowLen, int* startEndColLen) { if (n 0 || startEndRowLen 0) { return 0; } // 1. 提取开始时间和结束时间 int* start (int*)malloc(n * sizeof(int)); int* end (int*)malloc(n * sizeof(int)); for (int i 0; i n; i) { start[i] startEnd[i][0]; end[i] startEnd[i][1]; } // 2. 分别排序 qsort(start, n, sizeof(int), cmp); qsort(end, n, sizeof(int), cmp); // 3. 双指针扫描 int host 0; int j 0; // 指向结束时间数组 for (int i 0; i n; i) { if (j n start[i] end[j]) { // 当前活动开始前已有活动结束可以复用主持人 j; } else { // 需要新主持人 host; } } // 释放内存 free(start); free(end); return host; }知识点解析1 int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }void*是通用指针可以指向任何类型const表示不会修改指向的内容因为 qsort 不知道你传的是int*、float*还是结构体指针所以统一用void*接收。(int*)a将void*强制转换为int*类型指针。*(int*)a*表示取指针指向的值。return *(int*)a - *(int*)b返回两个整数的差值是qsort排序依据。实例中写成了int cmp(const void*a,const void*b){int x *(int*)a;int y *(int*)b;if (x y) return -1;if (x y) return 1;return 0;}防止大数据溢出int范围导致cmp无法判断负数、正数、或任何值。测试用例中-2147483648 - (-2147483647) -1✅ 没溢出2147483646 - (-2147483648)2147483646 2147483648超出 int 范围→ 溢出2qsort(start, startLen, sizeof(int), cmp);return a - b→ 升序小的在前return b - a→ 降序大的在前2.双指针2.1最长回文子串描述在123ABBAABAKA1233214abaaab类似构成的字符串中找到最长的对称子串输入的字符串里包含长度不同的对称子字符串和一些无关字符不区分字母大小写示例输入12ABAAAB返回BAAAB思路 中心扩展法每个字符或两个字符之间都可能是回文中心 奇数回文 中心是1个字符如 ABA → 从 B 向两边扩 偶数回文 中心是2个相同字符如 ABBA → 从 BB 中间向两边扩 将字符串遍历每个字符判断各字符为中心的最长子串长度再取其最大值即可#include stdio.h #include string.h // 从中心向两边扩展返回回文串长度 int expandAroundCenter(char *s, int left, int right) { int len strlen(s); // left和right是中心奇数长度时相同偶数长度时相邻 while (left 0 right len s[left] s[right]) { left--; right; } // 退出时多走了一步所以长度是 right - left - 1 return right - left - 1; } //比如12321字符串扩展结束后left-1right5 int longestPalindrome(char *s) { if (s NULL || strlen(s) 0) { return 0; } int start 0; // 最长回文串的起始位置 int maxLen 0; // 最长回文串的长度 int len strlen(s); for (int i 0; i len; i) { // 情况1奇数长度回文中心是单个字符如 ABA int len1 expandAroundCenter(s, i, i); // 情况2偶数长度回文中心是两个相同字符如 ABBA int len2 expandAroundCenter(s, i, i 1); // 取两种情况的最大值 int curLen len1 len2 ? len1 : len2; // 更新最长回文串 if (curLen maxLen) { maxLen curLen; start i - (curLen - 1) / 2; // 计算起始位置 } } return maxLen; } int main() { char str[10000]; scanf(%s, str); int result longestPalindrome(str); // 输出最长回文子串本身 printf(长度: %d\n, result); printf(子串: ); for (int i start; i start result; i) { putchar(str[i]); } printf(\n); return 0; }