31. Next Permutation
分析：
给一个数组，要求返回下一个更大的字典序排列，如果没有，则返回从小到大的排列。
举例来说，全排列{1,2,3} 按照字典序的下一个排列分别是 123、132、213、231、312 和 321。字典序就是按照左边第一个数最小，右边的数继续按字典序排列，左边第一个数第二小，右边的数继续按字典序排列......
1 2 7 4 3 1 下一个字典序是 1 3 1 2 4 7，观察倒数四个数是倒序的，说明下一个字典序需要把2换成从右往左数第一个比他大的，交换2和3得到1 3 7 4 2 1，这个时候再把倒数四个数转置一下就可以得到正确结果。
Java：
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
32. Longest Valid Parentheses
分析：
给出一个字符串s，全部由左右括号组成，求出最长合法的括号子串长度。
比如()()合法，()(()不合法。
使用dp[i]代表以i结尾的子串最长合法的子串长度，显然以'('结尾的都为0。
只用考虑以')'结尾的情况。
如果s[i] ==')' 且 s[i-1] == '('， 那么dp[i] = dp[i-2]+2。
如果s[i] ==')'，且s[i-1]==')'，先要求出可能可以与s[i]匹配的下标，这个下标index = i - dp[i - 1] - 1 ， 如果s[index] == '(' ，那么就可以与s[i]进行匹配。
此时 dp[i] = dp[i - 1] + (index - 1 >= 0 ? dp[index - 1] : 0) + 2;
Java：
public int longestValidParentheses(String s) {
int res = 0;
int dp[] = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else {
int index = i - dp[i - 1] - 1;
if (index >= 0 && s.charAt(index) == '(') {
dp[i] = dp[i - 1] + (index - 1 >= 0 ? dp[index - 1] : 0) + 2;
}
}
}
res = Math.max(res, dp[i]);
}
return res;
}
33. Search in Rotated Sorted Array
分析：
给一个数组，并不是完全有序，而是两部分有序，比如4,5,6,7,0,1,2,3，给出一个目标值target，找到它在数组中的下标，如果不存在则返回-1。
使用二分法的改进，时间复杂度降到O(n/2)，比直接遍历更优。
如果nums[lo] <= nums[mid]，那么mid左侧包含mid一定是递增的，否则mid右侧包含mid一定是递增的，再与target比较。
Java：
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (nums[mid] == target) {
return mid;
}
//此时mid左侧的都是递增的
if (nums[lo] <= nums[mid]) {
if (nums[mid] > target && nums[lo] <= target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else { //此时mid右侧都是递增的
if (nums[mid] < target && nums[hi] >= target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return -1;
}
34. Find First and Last Position of Element in Sorted Array
分析：
给一个递增数组和一个目标值target，要求找到target在数组中第一个出现的位置和最后一个出现的位置，如果没有出现则位置为-1。
写一个lower_bound()方法（注意实现的时候传参是 0 和 nums.length ），找到第一个大于等于target的位置first。
再写一个upper_bound()方法，找到第一个大于target的位置second。
如果nums[first]不等于target活着frist超过数组最大下标了，那么一定返回{-1,-1}。
如果nums[first]等于target，那么返回{first,second-1}
Java：
public class Solution {
//传入初值[0,n]
public int lower_bound(int[] nums, int lo, int hi, int x) {
int mid;
while (lo < hi) {
mid = (lo + hi) / 2;
if (nums[mid] >= x) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
//传入初值[0,n]
public int upper_bound(int[] nums, int lo, int hi, int x) {
int mid;
while (lo < hi) {
mid = (lo + hi) / 2;
if (nums[mid] > x) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) {
return new int[]{-1, -1};
}
int first = lower_bound(nums, 0, nums.length, target);
if (first >= nums.length || nums[first] != target) {
return new int[]{-1, -1};
} else {
int second = upper_bound(nums, 0, nums.length, target);
return new int[]{first, second - 1};
}
}
}
35. Search Insert Position
分析：
给一个有序的数组，和目标值target，要求找到在数组中插入的位置。
其实就是找到第一个大于等于的位置，用上一题已经实现好的lower_bound()函数即可。
Java：
public class Solution {
//传入初值[0,n]
public int lower_bound(int[] nums, int lo, int hi, int x) {
int mid;
while (lo < hi) {
mid = (lo + hi) / 2;
if (nums[mid] >= x) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
public int searchInsert(int[] nums, int target) {
return lower_bound(nums, 0, nums.length, target);
}
}
