一. NC107寻找峰值
题目描述:
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = −∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗？
数据范围：
1 ≤ nums.length ≤ 2×10 ^ 5
-2 ^ 31 <= nums[i] <= 2 ^31 - 1
如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：
链接：点这里
来源： 牛客网
解题思路：
方法一：二分法
时间复杂度o(logn),空间复杂度o(1)
思想:上坡一定有波峰，下坡不一定有波峰
题目将数组边界看成最小值（ nums[-1] = nums[n] = −∞），而我们只需要找到其中一个波峰，因此只要不断地往高处走（上坡），一定会有波峰；如果向低处走，可能会有波峰，但不一定；所以可以使用二分法使峰值的取值不断的在上坡范围内收缩，最终首尾相遇的位置一定就是波峰；
对于条件的控制应该做如下处理：
nums[mid] < nums[mid + 1]说明在“上坡”，则可以使left = mid + 1（因为mid肯定不是峰值），向“峰”处压缩
nums[mid] > nums[mid + 1]说明在“下坡”，则应该使right = mid（mid可能是峰值），往“峰”处压缩
方法二：找最大值
时间复杂度O(n)，空间复杂度O(1)
两个端点值是-∞（且元素不重复），我只需要一直找最大的值，那么这个值一定是波峰
代码实现：
import java.util.*; public class Solution { //方法一 public int findPeakElement (int[] nums) { int left = 0; int right = nums.length-1; int mid = 0; while(left < right) { mid = left+(right-left)/2; //下坡，不一定有波峰 if(nums[mid] > nums[mid+1]) { right = mid; } //上波，一定有波峰 if(nums[mid] < nums[mid+1]) { left = mid+1; } } return right; } //方法二 /*public int findPeakElement (int[] nums) { // 最大值一定是峰值 int max = 0; for(int i = 1; i < nums.length; i++) { if(nums[i] > nums[max]) { max = i; } } return max; }*/ }
提交结果：
二. HJ31单词倒排
题目描述:
对字符串中的所有单词进行倒排。
说明：
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
链接：点这里
来源： 牛客网
解题思路：
先将整个字符串整体逆序，再将字符串中的每个单词进行进行逆序即可，要注意字符串中的间隔符不止有空格，而输出结果中间隔符只能有空格，所以要将非空格的间隔符替换为空格
代码实现：
#include<stdio.h> #include<string.h> #include<assert.h> #include<ctype.h> void reverseString(char* left, char* right) { assert(left && right); while(left <= right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } int main() { char str[10001] = {0}; gets(str); int len = strlen(str); //首先将字符串整体进行逆序 reverseString(str, str+len-1); //再进行局部逆序 char* end = str; char* start = end; while(*end) { while((isupper(*end) || islower(*end)) && *end != '\0') { end++; } if(*end != ' ') { *end = ' '; } reverseString(start, end-1); if(*end != '\0') { end++; } start = end; } printf("%s", str); return 0; }
