Leetcode究极刷题笔记（31~35）
（31）下一个排列（中等）
实现思路：
从题目中，我们可以看出本题的意思就是让你选一个比当前序列大的最小的那个解，比如132，哪么比它大的最小解就是213（先从第一位开始比，接着是第二位，最后是第三位），如果是最大的，哪么重新排列为最小的。我们首先尽量保持前面的数字保持不变，所以我们从后面开始进行遍历，接着我们找到一个不是降序排列的点（可以理解为找一个点（定义为a），它后面的数字（定位为b）比它大），此时我们从b的后面找一个大于a的最小的点来替代它就可以了，所以我们首先要找到第一个非降序的位置，所以我们利用一个指针从后往前遍历即可，找到a，然后找到b后面比a大的最小值（注意b也是可以的）即可，注意交换完之后我们还要将a后面的数进行翻转，因为此时对应的首位已经是最大的，根据题意我们要找的是最小的，所以要进行翻转。
代码实现如下：
class Solution {
public:void nextPermutation(vector<int>& nums) {int k=nums.size()-1;while(k && nums[k-1]>=nums[k]) k--;//对应的就是找到第一个非降序的点if(k<=0)//对应的就是此时已经是最大排列了{reverse(nums.begin(),nums.end());//此时我们就返回它的最小序列就可以了}else{int t=k;//因为我们已经找到了不是降序的位置(k-1)，所以我们要从k开始往后找到一个大于nums[k-1]而且是最小的（在大于nums[k-1]这个集合中最小的那个数）while(t<nums.size() &&nums[t]>nums[k-1]) t++;//注意，因为k后面的数都是降序的，所以我们一直往后遍历，知道找到那个我们希望的数，此时nums[t]对应得就是第一个小于等于当前数的数（这里要注意一个误区，也就是当我们找到目标数的时候，此时还会执行一遍循环，所以此时nums[t]并不是我们要找的数，我们要找的数应该是nums[t-1]）,因为是往后找数，所以我们要进行++swap(nums[t-1],nums[k-1]);//这里就是贾环的步骤reverse(nums.begin()+k,nums.end());//此时就是将k后面的数进行翻转}}
};（32）最长有效括号（困难）
实现思路：
首先对于这种问题，我们首先要知道什么是有效的括号序列，即只有当左括号的数量大于等于右括号的数量时此时就是有效括号序列，首先我们可以将对应的括号序列分为若干段，每一段的分界点就是当前无法匹配的右括号的坐标的下一个位置。
接下来就是对应的思路实现，首先我们创建一个栈，将对应的左括号的下标入栈，如果此时循环字符串是右括号的话，就删除栈顶元素（因为此时已经匹配了），删除了还不是栈还不是空的话，就说明当前合法序列的长度可以增加了（长度就是对应的右括号的位置减去左括号的位置），但是如果栈是空的话，说明此时右括号的就是我们的分界点，这时我们就更新分界点即可。
代码实现如下：
class Solution {
public:int longestValidParentheses(string s) {//合法括号序列的前提就是左括号的数量大于右括号的数量//找到不合法的位置，在其右边画一条线，任何一个合法序列是不可能跨越这条线的//通过推断是可以推测出是不合法的stack<int> st;int res=0;for(int i=0,start=-1;i<s.size();i++){//start记录的是当前每一段的前一个位置，0的前一个为-1，所以先这样记录if(s[i]=='('){st.push(i);}else{if(st.size()){st.pop();if(st.size())//删除了之后如果此时还不是空的话，就说明此时合法序列的长度为//此时右括号的位置减去栈顶元素的位置{res=max(res,i-st.top());//}else{res=max(res,i-start);//}}else{start=i;//如果有括号入栈的时候左括号已经没有了，说明此时对应的右括号的位置就是我们的分界点}}}return res;}
};（33）搜索旋转排序数组（中等）
实现思路：
一般我们在一个数组中找一个数的思路就是遍历一遍找对应的数的下标即可，但是那样的话时间复杂度就是o(n)，但是本题要求的是o(logn)，因此我们考虑使用二分进行查找，具体实现看代码即可。
代码实现如下：
class Solution {
public:int search(vector<int>& nums, int target) {//（1）找出两段，其中一般满足一个性质，后一段不满住这个性质，这样就可以分成两段//（2）找第一段的第一个元素，第一段都是大于第一个元素的，而第二段都是小于第一个元素的，这样就区分开了性质/*本题的意思就是让你在一个不是升序数组中查找一个数字的下表，一般都是直接遍历即可但是这里要求时间复杂度为o(logn)，所以这里我们考虑使用二分查找的做法，首先找到一个性质来区别两段的分界点，然后再确定我们要找的数在那一段并对其进行二分*/if(!nums.size()) return -1;int l=0,r=nums.size()-1;while(l<r){int mid=(l+r+1)>>1;if(nums[mid]>nums[0]){l=mid;}else{r=mid-1;}}//以上是找分界点的代码if(target>=nums[0]){l=0;}else{l=r+1,r=nums.size()-1;}//以上就是找对应的要进行二分数组的代码while(l<r){int mid=(l+r)>>1;if(nums[mid]>=target){r=mid;}else{l=mid+1;}}//以上就是找对应的数字的代码if(nums[r]==target) return r;//这里如果将r改为l就会有一个例子报错/*eg.[1] 0因为[1] 0这个数据没有进入二分循环，只会执行else {l=r+1,r=num.size()-1,这一步导致了l=1,r=0,去l=1就会报错（因为只有一个元素）}*/return -1;}
};（34）在排序数组中查找元素的第一个位置和最后一个位置（中等）
实现思路：
本题是一个经典的二分查找模板，具体大家可以看这篇博客：
http://t.csdn.cn/IlgX2（转载自csdn：昂昂累世士）
代码实现如下：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(!nums.size()) return {-1,-1};int l=0,r=nums.size()-1;while(l<r){int mid=(l+r)>>1;if(nums[mid]<target) l=mid+1;else{r=mid;}}int temp=l;if(nums[l]!=target) return {-1,-1};else{l=0,r=nums.size()-1;while(l<r){int mid=(l+r+1)>>1;if(nums[mid]<=target) l=mid;else{r=mid-1;}}}return {temp,l};}
};（35）搜索插入位置（简单）
实现思路：
本题十分简单，这里使用了双指针算法，具体实现看代码
代码实现如下：
int searchInsert(int* nums, int numsSize, int target)
{int left=0;int right=numsSize-1;int ans=numsSize;while(left<=right){int mid=left+((right-left)>>1);if(target<=nums[mid]){ans=mid;right=mid-1;}else {left=mid+1;}}return ans;
}