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
代码：
fn next_permutation(nums: &mut Vec<u32>) { let n = nums.len(); let mut i = (n - 2) as isize; while i >= 0 && nums[i as usize] >= nums[i as usize + 1] { i -= 1; } if i >= 0 { let mut j = (n - 1) as isize; while j >= 0 && nums[i as usize] >= nums[j as usize] { j -= 1; } nums.swap(i as usize, j as usize); } nums[(i + 1) as usize..].reverse(); } fn main() { let mut nums = vec![1, 2, 3]; next_permutation(&mut nums); println!("{:?}", nums); nums = vec![3, 2, 1]; next_permutation(&mut nums); println!("{:?}", nums); nums = vec![1, 1, 5]; next_permutation(&mut nums); 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] 为 '(' 或 ')'
代码：
use std::convert::TryInto; fn longest_valid_parentheses(s: &str) -> usize { let n = s.len(); let s = s.as_bytes(); let mut max_len = 0; if n == 0 { return 0; } let mut dp = vec![0; n]; for i in 1..n { if s[i] == b')' { if s[i - 1] == b'(' { if i >= 2 { dp[i] = dp[i - 2] + 2; } else { dp[i] = 2; } } else if i as i32 - dp[i - 1] as i32 - 1 >= 0 && s[i - dp[i - 1] - 1] == b'(' { if i as i32 - dp[i - 1] as i32 - 2 >= 0 { dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2; } else { dp[i] = dp[i - 1] + 2; } } max_len = max(max_len, dp[i].try_into().unwrap()); } } max_len } fn max(a: usize, b: usize) -> usize { if a > b { a } else { b } } fn main() { let s = "(()"; println!("{}", longest_valid_parentheses(s)); let s = ")()())"; println!("{}", longest_valid_parentheses(s)); let s = ""; println!("{}", longest_valid_parentheses(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) 的解决方案吗？
代码： 二分查找
fn search(nums: &[i32], target: i32) -> i32 { let n = nums.len() as i32; if n == 0 { return -1; } if n == 1 { if nums[0] == target { return 0; } return -1; } let mut left = 0; let mut right = n - 1; while left <= right { let mid = left + (right - left) / 2; if nums[mid as usize] == target { return mid; } if nums[0] <= nums[mid as usize] { if nums[0] <= target && target < nums[mid as usize] { right = mid - 1; } else { left = mid + 1; } } else { if nums[mid as usize] < target && target <= nums[n as usize - 1] { left = mid + 1; } else { right = mid - 1; } } } -1 } fn main() { let nums = vec![4, 5, 6, 7, 0, 1, 2]; println!("{}", search(&nums, 0)); println!("{}", search(&nums, 3)); let nums = vec![1]; println!("{}", search(&nums, 0)); }
输出：
4
-1
-1
