31. Next Permutation
分三步:
https://leetcode.com/problems/next-permutation/solution/
1、首先找到相邻的两个元素，前面一个元素值小于后面一个元素值，即nums[i] < nums[i+1] 因为数组是按逆序排序的话，直接倒置就可以了
2、此时i的位置确定了，接下来就是找到跟i元素交换的元素j，j元素应该是从后面开始第一个大于i元素的，此时交换i位置的元素和j位置的元素
3、第三步，此时i位置后面的元素是按逆序排序的，我们需要将其倒置
class Solution {
public void nextPermutation(int[] nums) {
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
动态规划
class Solution {
public int longestValidParentheses(String s) {
int maxans = 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 if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
}
使用栈
class Solution {
public int longestValidParentheses(String s) {
int maxres =0;
Stack<Integer> stack = new Stack<Integer>();
stack.push(-1);
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='(')
stack.push(i);
else{
stack.pop();
if(stack.empty())
stack.push(i);
else
maxres = Math.max(maxres,i-stack.peek());
}
}
return maxres;
}
}
33. Search in Rotated Sorted Array
二分查找的思路，要想清楚各种情况
class Solution {
public int search(int[] nums, int target) {
if(nums.length==0)
return -1;
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (right-left) / 2 + left;
if(nums[mid]==target)
return mid;
else{
if(mid==left){
left ++;
}
else if(nums[mid] > nums[left]){
if(target>nums[mid])
left++;
else if(target>=nums[left])
right--;
else
left ++;
}
else{
if(target < nums[mid])
right--;
else if(target <= nums[right])
left ++;
else
right--;
}
}
}
return -1;
}
}
34. Search for a Range
用两次二分查找分别找到最左边和最右边的索引。
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1,-1};
if(nums.length==0)
return res;
int left = 0;int right=nums.length-1;
while(left<=right){
int mid = (right-left) / 2 + left;
if(nums[mid]>=target)
right--;
else
left++;
}
if(left<nums.length && nums[left]==target)
res[0]=left;
else
return res;
left = 0;right=nums.length-1;
while(left<=right){
int mid = (right-left) / 2 + left;
if(nums[mid]<=target)
left++;
else
right--;
}
if(right>=0 && nums[right]==target)
res[1]=right;
return res;
}
}
35. Search Insert Position
即二分查找
class Solution {
public int searchInsert(int[] nums, int target) {
if(nums.length==0)
return 0;
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = (right-left)/2 + left;
if(nums[mid]==target)
return mid;
else if(nums[mid]>target)
right = mid - 1 ;
else
left = mid + 1;
}
return left;
}
}
36. Valid Sudoku
一个合法的九宫格要满足每行每列以及每个3*3的小正方形中都有1-9这9个数字。
我们循环九次，在每次循环中利用HashSet判断每列每行以及每个正方形中有没有重复数字即可：
class Solution {
public boolean isValidSudoku(char[][] board) {
for(int i = 0; i<9; i++){
HashSet<Character> rows = new HashSet<Character>();
HashSet<Character> columns = new HashSet<Character>();
HashSet<Character> cube = new HashSet<Character>();
for (int j = 0; j < 9;j++){
if(board[i][j]!='.' && !rows.add(board[i][j]))
return false;
if(board[j][i]!='.' && !columns.add(board[j][I]))
return false;
int RowIndex = 3*(i/3);
int ColIndex = 3*(i%3);
if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
return false;
}
}
return true;
}
}
37. Sudoku Solver
回溯法
public class Solution {
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0)
return;
solve(board);
}
public boolean solve(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
if(isValid(board, i, j, c)){
board[i][j] = c; //Put c for this cell
if(solve(board))
return true; //If it's the solution return true
else
board[i][j] = '.'; //Otherwise go back
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char c){
for(int i = 0; i < 9; i++) {
if(board[i][col] != '.' && board[i][col] == c) return false; //check row
if(board[row][i] != '.' && board[row][i] == c) return false; //check column
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
}
return true;
}
}
39. Combination Sum
回溯法，注意直接add arr是不行的。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new LinkedList<>();
if(candidates==null || candidates.length==0 || target<=0)
return res;
Arrays.sort(candidates);
slove(res,candidates,0,new ArrayList<Integer>(),target);
return res;
}
public static void slove(List<List<Integer>> res,int[] candidates,int start,ArrayList<Integer> arr,int target){
if(target==0){
//直接add arr是不行的
res.add(new ArrayList<>(arr));
return;
}
if(target<0)
return;
for(int i=start;i<candidates.length;i++){
arr.add(candidates[I]);
slove(res,candidates,i,arr,target-candidates[I]);
arr.remove(arr.size()-1);
}
}
}
40. Combination Sum II
仍然是回溯法，39题的一个变形
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new LinkedList<>();
if(candidates==null || candidates.length==0 || target<=0)
return res;
Arrays.sort(candidates);
slove(res,candidates,0,new ArrayList<Integer>(),target);
return res;
}
public static void slove(List<List<Integer>> res,int[] candidates,int start,ArrayList<Integer> arr,int target){
if(target==0){
//直接add arr是不行的
res.add(new ArrayList<>(arr));
return;
}
if(target<0)
return;
for(int i=start;i<candidates.length;i++){
if(i>start && candidates[i]==candidates[i-1])
continue;
arr.add(candidates[i]);
slove(res,candidates,i+1,arr,target-candidates[i]);
arr.remove(arr.size()-1);
}
}
}
