目录
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]numsnums必须 原地 修改，只允许使用额外常数空间。
示例 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 <= 1000 <= 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^4s[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
numsnumsk0 <= k < nums.length[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]][0,1,2,4,5,6,7]3[4,5,6,7,0,1,2]numstargetnumstarget-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^4numsnums-10^4 <= target <= 10^4O(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))
}
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！