Rust每日一练(Leetday0011) 下一排列、有效括号、搜索旋转数组

目录

31. 下一个排列 Next Permutation  🌟🌟

32. 最长有效括号 Longest Valid Parentheses  🌟🌟🌟

33. 搜索旋转排序数组 Search-in-rotated-sorted-array  🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

---

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

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/

	Rust每日一练 专栏 （2023.5.16~）更新中...
	Golang每日一练 专栏 （2023.3.11~）更新中...
	Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更
	C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更
	Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更