【牛客】NC107寻找峰值,HJ31单词倒排

╰半橙微兮° 2023-09-27 09:56 71阅读 0赞

![在这里插入图片描述][078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]✨**博客主页:**[ **XIN-XIANG荣**][_XIN-XIANG]  
✨**系列专栏:**[**【LeetCode/牛客刷题】**][LeetCode]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

#### 文章目录 ####

*  一. NC107寻找峰值
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：
 *  二. HJ31单词倒排
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：

## 一. 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的山峰，如下图所示：

![img][]

**链接：** [点这里][Link 1]  
**来源：** 牛客网

### 解题思路： ###

**方法一：二分法**

时间复杂度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;
        }*/
    }

### 提交结果： ###

![img][img 1]

## 二. 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

**链接：** [点这里][Link 2]  
**来源：** 牛客网

### 解题思路： ###

先将整个字符串整体逆序，再将字符串中的每个单词进行进行逆序即可，要注意字符串中的间隔符不止有空格，而输出结果中间隔符只能有空格，所以要将非空格的间隔符替换为空格

### 代码实现： ###

#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;
    }

### 提交结果： ###

![img][img 2]

[078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]: https://img-blog.csdnimg.cn/078b66f87e3c4e309d7f34d79c5776c4.gif#pic_center
[_XIN-XIANG]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[LeetCode]: https://blog.csdn.net/trong_/category_11990219.html?spm=1001.2014.3001.5482
[img]: https://img-blog.csdnimg.cn/img_convert/f47a51e2d81c954568f6a333fb3545ef.png
[Link 1]: https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=188&&tqId=38666&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
[img 1]: https://img-blog.csdnimg.cn/img_convert/d85aad9bfd0d5bec759ae4f1f650cec6.png
[Link 2]: https://www.nowcoder.com/practice/81544a4989df4109b33c2d65037c5836?tpId=37&&tqId=38366&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking
[img 2]: https://img-blog.csdnimg.cn/img_convert/bce8ff29bcf62cd8311ea20ba62f2c28.png