给自己的目标：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一题
在做题的过程中记录下解题的思路或者重要的代码碎片以便后来翻阅。
项目源码：github上的Leetcode
31. Next Permutation
题目：给出一个序列，寻找比当前排列顺序大的下一个排列。规则如下：
1,2,3 ->next
1,3,2 ->next
2,1,3 ->next
2,3,1 ->next
3,1,2 ->next
3,2,1 ->next
1,2,3 ->loop
因为是找递增的下一个排列，所以从后往前找到第一个升序对的位置，如1,2,4,3,1， 从后向前找就是2,4,3,1，因为2比前一个数4小，所以就锁定2这个数。
之后就是在4,3,1中找到比2大的最小的那个数3，将3与2对换得到降序排列4,2,1.然后就是将4,2,1反序得到1,2,4.最终结果就是1,3,1,2,4
public class Solution {
public void nextPermutation(int[] nums) {
if (nums.length == 0 || nums.length == 1) return;
int len = nums.length;
int index = len - 1;
int value = nums[index];
for (index = index - 1; index >= 0; index--) {
if (nums[index] < value) {
value = nums[index];
break;
}
value = nums[index];
}
if (index < 0) {
reversal(nums, 0, len - 1);
} else {
for (int j = len - 1; j > index; j--) {
if (nums[j] > value) {
nums[index] = nums[j];
nums[j] = value;
reversal(nums, index + 1, len - 1);
break;
}
}
}
}
public void reversal(int[] nums, int start, int end) {
int len = end + 1 - start;
for (int i = 0; i < len / 2; i++) {
int k = nums[start + i];
nums[start + i] = nums[end - i];
nums[end - i] = k;
}
}
}
32. Longest Valid Parentheses
题目：输入一串只包含"(",")"的字符串，求合法子串的最大值。
")()())", where the longest valid parentheses substring is "()()", which has length = 4.
一道很容易TLE的题目，最优解法是使用 stack 记录字符串中"("出现时的index，当出现")"进行匹配时相减得到长度。
public class Solution {
public int longestValidParentheses(String s) {
if (s.isEmpty()) return 0;
Stack<Integer> ms = new Stack<>();
int maxlen = 0;
int last = -1; // Position of the last unmatched ')'
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') ms.push(i); //
else if (ms.empty()) last = i; // == ')' and the stack is empty, it means this is a non-matching ')'
else {
ms.pop(); // pops the matching '('.
if (ms.empty()) // If there is nothing left in the stack, it means this ')' matches a '(' after the last unmatched ')'
maxlen = Math.max(maxlen, i - last);
else // otherwise,
maxlen = Math.max(maxlen, i - ms.peek());
}
}
return maxlen;
}
}
33.Search in Rotated Sorted Array
题目：给出一组有序的数组，如 0 1 2 4 5 6 7，将其分成两段并互换，比如会成为4 5 6 7 0 1 2。给出一个 target 值，求在数组中的位置，若不存在输出-1
一种最简单的方法是直接遍历过，时间复杂度为O(n),另一种是先使用 binary search 找出旋转点（最小值）所在的位置，之后在用二分遍历一次获得 target 所在的位置。
/**
* 简单遍历
*/
public class Solution {
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
}
34. Search for a Range
题目：给出一个有序的数组和一个目标值，求该目标值在数组的范围（由于目标值在数组中存在好几个）。要求时间复杂度为O(logn)
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
一个很简单的二分查找题，要注意的是即使找到一个目标值也要继续向左右查找下去以便确定目标值在数组中的范围。
public class Solution {
public int[] searchRange(int[] nums, int target) {
int start = -1, end = -1;
int st = 0, len = nums.length - 1;
while (st <= len) {
int mid = (len + st + 1) / 2;
if (nums[mid] == target) {
start = binarySearch(nums, st, mid - 1, target, true);
end = binarySearch(nums, mid + 1, len, target, false);
if (start == -1) start = mid;
if (end == -1) end = mid;
break;
} else if (nums[mid] > target) {
len = mid - 1;
} else if (nums[mid] < target) {
st = mid + 1;
}
}
return new int[]{start, end};
}
public int binarySearch(int[] nums, int start, int end, int target, boolean left) {
if (start > end) {
return -1;
}
int mid = (start + end + 1) / 2;
int index = -1;
if (nums[mid] == target) {
if (left) {
index = binarySearch(nums, start, mid - 1, target, left);
} else {
index = binarySearch(nums, mid + 1, end, target, left);
}
if (index == -1) {
return mid;
}
return index;
} else if (nums[mid] > target) {
return binarySearch(nums, start, mid - 1, target, left);
} else if (nums[mid] < target) {
return binarySearch(nums, mid + 1, end, target, left);
} else {
return index;
}
}
}
35. Search Insert Position
题目：给出一组有序数组和一个目标数字，求目标数字在数组中的位置，没找到时则求插入数组的位置。
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
一道简单的二分查找题
public class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
int start = 0;
int end = len - 1;
int index = start;
while (start <= end) {
int mid = (start + end) / 2;
if (target > nums[mid]) {
start = mid + 1;
index = start;
} else if (target < nums[mid]) {
end = mid - 1;
index = mid;
} else {
return mid;
}
}
return index;
}
}
