31. 下一个排列 Next Permutation
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 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
代码：
package main import "fmt" func nextPermutation(nums []int) { n := len(nums) i := n - 2 for i >= 0 && nums[i] >= nums[i+1] { i-- } if i >= 0 { j := n - 1 for j >= 0 && nums[i] >= nums[j] { j-- } nums[i], nums[j] = nums[j], nums[i] } reverse(nums[i+1:]) } func reverse(nums []int) { n := len(nums) for i := 0; i < n/2; i++ { nums[i], nums[n-i-1] = nums[n-i-1], nums[i] } } func main() { nums := []int{1, 2, 3} nextPermutation(nums) fmt.Println(nums) nums = []int{3, 2, 1} nextPermutation(nums) fmt.Println(nums) nums = []int{1, 1, 5} nextPermutation(nums) fmt.Println(nums) }
输出：
[1 3 2]
[1 2 3]
[1 5 1]
32. 最长有效括号 Longest Valid Parentheses
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
0 <= s.length <= 3 * 10^4
s[i] 为 '(' 或 ')'
代码：
package main import "fmt" func longestValidParentheses(s string) int { maxLen := 0 n := len(s) if n == 0 { return 0 } dp := make([]int, n) for i := 1; i < n; i++ { if s[i] == ')' { if s[i-1] == '(' { if i-2 >= 0 { dp[i] = dp[i-2] + 2 } else { dp[i] = 2 } } else if i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(' { if i-dp[i-1]-2 >= 0 { dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2 } else { dp[i] = dp[i-1] + 2 } } maxLen = max(maxLen, dp[i]) } } return maxLen } func max(a, b int) int { if a > b { return a } return b } func main() { s := "(()" fmt.Println(longestValidParentheses(s)) s = ")()())" fmt.Println(longestValidParentheses(s)) s = "" fmt.Println(longestValidParentheses(s)) }
输出：
2
4
0
33. 搜索旋转排序数组 Search-in-rotated-sorted-array
整数数组 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 。
示例 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
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
代码： 二分查找
package main import "fmt" func search(nums []int, target int) int { n := len(nums) if n == 0 { return -1 } if n == 1 { if nums[0] == target { return 0 } return -1 } left, right := 0, n-1 for left <= right { mid := (left + right) / 2 if nums[mid] == target { return mid } if nums[0] <= nums[mid] { if nums[0] <= target && target < nums[mid] { right = mid - 1 } else { left = mid + 1 } } else { if nums[mid] < target && target <= nums[n-1] { left = mid + 1 } else { right = mid - 1 } } } return -1 } func main() { nums := []int{4, 5, 6, 7, 0, 1, 2} fmt.Println(search(nums, 0)) fmt.Println(search(nums, 3)) nums = []int{1} fmt.Println(search(nums, 0)) }
输出：
4
-1
-1
另一种写法：
其中： mid := left + (right-left)>>1 <==> mid := (left + right) / 2
package main import "fmt" func search(nums []int, target int) int { if len(nums) == 0 { return -1 } left, right := 0, len(nums)-1 for left <= right { mid := left + (right-left)>>1 if nums[mid] == target { return mid } else if nums[mid] > nums[left] { if nums[left] <= target && target < nums[mid] { right = mid - 1 } else { left = mid + 1 } } else if nums[mid] < nums[right] { if nums[mid] < target && target <= nums[right] { left = mid + 1 } else { right = mid - 1 } } else { if nums[left] == nums[mid] { left++ } if nums[right] == nums[mid] { right-- } } } return -1 } func main() { nums := []int{4, 5, 6, 7, 0, 1, 2} fmt.Println(search(nums, 0)) fmt.Println(search(nums, 3)) nums = []int{1} fmt.Println(search(nums, 0)) }
