Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.1,2,3→1,3,23,2,1→1,2,31,1,5→1,5,1
给出一串数字序列，将其改变成字典序中下一个序列
在当前序列中，，从尾端往前寻找两个相邻元素，前一个记为*i，后一个记为*ii，并且满足*i < *ii。然后再从尾端寻找另一个元素*j，如果满足*i < *j，即将第i个元素与第j个元素对调，并将第ii个元素之后（包括ii）的所有元素颠倒排序，即求出下一个序列了。
class Solution {public:void nextPermutation(vector<int>& nums){int len=nums.size();int mark;if (len<=1) return ;int i;for (i=len-1;i>0;i–){if (nums[i]>nums[i-1]){mark=i;break;}}if (i==0){for (i=0;i<len/2;i++)swap(nums[i],nums[len-i-1]);return ;}for (i=len-1;i>mark;i–)if (nums[i]>nums[mark-1]) break;swap(nums[i],nums[mark-1]);for (i=mark;i<len && i<(mark+len)/2;i++)swap(nums[i],nums[len-1+mark-i]);}};Longest Valid Parentheses
Given a string containing just the characters'(‘and’)’, find the length of the longest valid (well-formed) parentheses substring.
For"(()", the longest valid parentheses substring is"()", which has length = 2.
Another example is")()())", where the longest valid parentheses substring is"()()", which has length = 4.
输出最长连续完全匹配括号的字符串长度
首先对字符串进行预处理，标记所有可以进行匹配的字符，然后找最长的可匹配子序列即可
class Solution {public:int longestValidParentheses(string s){int len=s.length();bool *a=new bool[len];memset(a,false,len);stack<int>st;for (int i=0;i<len;i++)if (s[i]=='(')st.push(i);else{if (!st.empty()){a[st.top()]=true;a[i]=true;st.pop();}}int ans=0,cnt=0;;for (int i=0;i<len;i++){if (a[i]==true) cnt++;else cnt=0;ans=max(ans,cnt);}return ans;}};
Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
在一串有循环递增数组中找到指定值
在二分中间判断一下target属于左区间还是右区间即可
class Solution {public:int search(vector<int>& nums, int target){int len=nums.size();if (len==0) return -1;int l,r,mid;l=0; r=len-1;while (l<=r){mid=(l+r)/2;if (nums[mid]==target)return mid;elseif (nums[mid]<target){if (nums[r]>=target || nums[r]<nums[mid]) l=mid+1;else r=mid-1;}else{if (nums[l]<=target || nums[l]>nums[mid]) r=mid-1;else l=mid+1;}}return -1;}};Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order ofO(logn).
If the target is not found in the array, return[-1, -1].
For example,Given[5, 7, 7, 8, 8, 10]and target value 8,return[3, 4].
输出查找数字所在范围
两个二分分别查找数字出现的最左端和最右端即可
class Solution {public:vector<int> searchRange(vector<int>& nums, int target){vector<int>ans;int len=nums.size();if (len==0){ans.push_back(-1);ans.push_back(-1);return ans;}int l,r,mid;l=0; r=len-1;while (l<=r){mid=(l+r)/2;if (nums[mid]==target){if (l+1==r || l==r) break;elseif (nums[mid-1]==target) r=mid-1;else{l=r=mid;break;}}elseif (nums[mid]>target)r=mid-1;elsel=mid+1;}if (nums[l]!=target){ans.push_back(-1);ans.push_back(-1);return ans;}ans.push_back(l);l=0; r=len-1;while (l<=r){mid=(l+r+1)/2;if (nums[mid]==target){if (l+1==r || l==r) break;elseif (mid+1<len && nums[mid+1]==target) l=mid+1;else{l=r=mid;break;}}elseif (nums[mid]>target)r=mid-1;elsel=mid+1;}ans.push_back(r);return ans;}};
Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0
返回将target按序插入数列中的所在位置
简单二分
巨龟千岁，却也平淡无奇;昙花瞬间，却能绚丽无比。
