目錄

LeetCode 第31題：下一個排列

?LeetCode 第32題：最長有效括號

LeetCode 第33題：搜索旋轉排序數組

LeetCode 第31題：下一個排列

題目描述

整數數組的一個排列就是將所有成員以序列或線性順序排列。例如arr=[1,2,3]，以下這些都可以視作arr的排列：[1,2,3]，[1,3,2]，[3,1,2]，[2,3,1]。整數數組的下一個排列是指整數的下一個字典序更大的排列。更正式地，如果數組的所有排列根據其字典順序從小到大排列在一個容器中，那么數組的下一個排列就是在這個有序容器中排在它后面的那個排列。如果不存在下一個更大的排列，那么這個數組必須重排為字典最小的排列（即，其元素按升序排列）。

難度：中等

題目鏈接：31. 下一個排列 - 力扣（LeetCode）

示例1：

輸入：nums = [1,2,3]
輸出：[1,3,2]

?示例2：

輸入：nums = [3,2,1]
輸出：[1,2,3]

示例3：

輸入：nums = [1,1,5]
輸出：[1,5,1]

提示：

• 1<=nums.length<=100
• 0<=nums[i]<=100

解題思路：字典序
關鍵點：

• 從右向左找第一個升序對
• 從右向左找第一個大于nums[i]的數
• 交換并反轉后續數字

具體步驟：

• 從右向左找第一個升序對（i,i+1）,找到第一個nums[i]<nums[i+1]的位置，此位置就是需要改變的位置。
• 從右向左找第一個大于nums[i]的數，在i右側找第一個大于nums[i]的數，與nums[i]交換。
• 反轉i+1后的所有數字，因為i+1后的數字是降序的，反轉后得到升序。?

public class Solution
{public void NextPermutation(int[] nums){int i=nums.Length-2;//找到第一個升序對while(i>=0 && nums[i]>=nums[i+1])i--;if(i>=0){int j=nums.Length-1;//找到第一個大于nums[i]的數while(j>=0 && nums[j]<=nums[i])j--;Swap(nums,i,j);}Reverse(nums,i+1);//反轉i+1之后的數字}private void Swap(int[] nums,int i ,int j){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;}private void Reverse(int[] nums,int start){int left = start,right=nums.Length-1;while(left<right){Swap(nums,left,right);left++;right--;}}
}

• 時間復雜度：O（n）
• 空間復雜度：O（1）

?LeetCode 第32題：最長有效括號

題目描述：
給你一個只包含‘（’和‘）’的字符串，找出最長有效（格式正確且連續）括號子串的長度。

難度：困難
題目鏈接：32. 最長有效括號 - 力扣（LeetCode）

示例1：

輸入：s = "(()"
輸出：2
解釋：最長有效括號子串是 "()"

?示例2：

輸入：s = ")()())"
輸出：4
解釋：最長有效括號子串是 "()()"

示例3：

輸入：s = ""
輸出：0

提示：

• 0<=s.length<=3*104
• s[i]為‘（’或‘）’

解題思路：

方法一：動態規劃

關鍵點：

• 當s[i]為‘(’時，dp[i]=0，因為不可能以左括號結尾
• 當s[i]為‘）’時，需要考慮兩種情況：
  s[i-1]為‘（’,dp[i]=dp[i-2]+2；s[i-1]為‘）’檢查dp[i-1]前面的字符是否是‘（’

public class Solution
{public int LongestValidParentheses(string s){if(strlen(s)==0) return 0;int maxLen=0,n=strlen(s);int dp[n];for(int i=0;i<n;i++){if(s[i]==')'){if(s[i-1]=='(')  dp[i]=(i>=2 ? dp[i-2]:0)+2;else if(i-dp[i-1]>0 && s[i-dp[i-1]-1]=='(')dp[i] = dp[i-1]+2+(i-dp[i-1]>=2 ? dp[i-dp[i-1]-2]:0);maxLen = Math.Max(maxLen,dp[i]);}}return maxLen;}
}

方法二：雙向掃描法

• 從左到右掃描，統計左右括號數量
• 從右向左再次掃描，取兩次掃描的最大值

public class Solution
{public int LongestVaildParentheses(string s){int manLen=0,left=0,right=0;//從左向右掃描for(int i=0;i<s.Length;i++){if(s[i]=='(') left++;else right++;if(left==right)  maxLen=Math.Max(maxLen,2*right);else if(right>left)  left=right=0;}//從右到左掃描left=right=0;for(int i=s.Length-1;i>=0;i--){if(s[i]=='(') left++;else right++;if(left==right)  maxLen=Math.Max(maxLen,2*left)else if(left>right)  left=right=0;}return maxLen;}
}

方法三：棧

• 使用棧存儲左括號的下標
• 遇到右括號時嘗試匹配
• 通過下標差計算長度

public class Solution
{public int LongestVaildParentheses(string s){int maxLen=0,n=strlen(s);int stack[n+1];stack.Push(-1);for(int i=0;i<s.Length;i++){if(s[i]=='(')  stack.Push(i);else {stack.Pop();if(stack.Count==0)  stack.Push(i);else maxLen=fmax(maxLen,i-stack[top]);//返回棧頂的元素但不移除它}}return manLen;    
}
}

LeetCode 第33題：搜索旋轉排序數組

題目描述

整數數組nums按升序排列，數組中的值互不相同。

在傳遞給函數之前，nums在預先未知的某個下標k（0<=k<nums.length）上進行了旋轉，使數組變為【nums[k],nums[k+1],........nums[n-1],nums[0],nums[1],.......nums[k-1]】(下標從0開始計數)。例如【0，1，2，4，5，6，7】在下標3處經旋轉后可能變為【4，5，6，7，0，1，2】。

給你一個旋轉后的數組nums和一個整數target，如果nums中存在這個目標值target，則返回它的下標，否則返回-1。你必須設計一個時間復雜度為O(log n)的算法來解決此問題。

難度：中等

題目鏈接：?33. 搜索旋轉排序數組 - 力扣（LeetCode）

示例1：

輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4

?示例2：

輸入：nums = [4,5,6,7,0,1,2], target = 3
輸出：-1

示例3：

輸入：nums = [1], target = 0
輸出：-1

提示：

• 1<=nums.length<=5000
• -104<=nums[i]<=104
• nums中的每個值都獨一無二
• 題目數據保證nums在預先未知的某個下標上進行了旋轉
• -104<=target<=104

解題思路：二分查找

public class Solution
{public int Serach(int nums[],int target){if(nums==null || nums.length==0) return -1;int left=0,right=nums.length-1;while(left<=right){int mid= left+right>>1;if(nums[mid]==target)  return mid;if(nums[left]<=nums[mid])//判斷有序部分，二分查找僅限于有序數列中//判斷target是否在有序部分中，如果在縮小范圍到有序部分，否則搜索另一半{if(target>=nums[left] && target<nums[mid]) right=mid-1;else left = mid+1;}else{if(target>nums[mid] && target<=nums[right+1]) left=mid+1;else right = mid-1;}}return -1;}
}