88. 合并两个有序数组 Merge Sorted Array
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-10^9 <= nums1[i], nums2[j] <= 10^9
进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
代码1： 双指针正向遍历
fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &Vec<i32>, n: i32) { let nums: Vec<i32> = nums1[..m as usize].to_vec(); // 复制nums1中的前m个元素到新数组中 let (mut p1, mut p2) = (0, 0); // 双指针遍历nums1和nums2，将较小的元素放入nums1中 for i in 0..(m + n) as usize { if p1 >= m as usize { nums1[i] = nums2[p2]; p2 += 1; } else if p2 >= n as usize { nums1[i] = nums[p1]; p1 += 1; } else if nums[p1] <= nums2[p2] { nums1[i] = nums[p1]; p1 += 1; } else { nums1[i] = nums2[p2]; p2 += 1; } } } fn main() { let mut nums1 = vec![1, 2, 3, 0, 0, 0]; let nums2 = vec![2, 5, 6]; let m = 3; let n = 3; merge(&mut nums1, m, &nums2, n); println!("{:?}", nums1); }
输出：
[1, 2, 2, 3, 5, 6]
代码2： 双指针逆向遍历
fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &Vec<i32>, n: i32) { let mut p1 = m - 1; let mut p2 = n - 1; let mut i = m + n - 1; while i >= 0 { if p1 < 0 { nums1[i as usize] = nums2[p2 as usize]; p2 -= 1; } else if p2 < 0 { nums1[i as usize] = nums1[p1 as usize]; p1 -= 1; } else if nums1[p1 as usize] >= nums2[p2 as usize] { nums1[i as usize] = nums1[p1 as usize]; p1 -= 1; } else { nums1[i as usize] = nums2[p2 as usize]; p2 -= 1; } i -= 1; } } fn main() { let mut nums1 = vec![1, 2, 3, 0, 0, 0]; let nums2 = vec![2, 5, 6]; let m = 3; let n = 3; merge(&mut nums1, m, &nums2, n); println!("{:?}", nums1); // [1, 2, 2, 3, 5, 6] }
89. 格雷编码 Gray Code
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
- 每个整数都在范围
[0, 2n - 1]内（含0和2n - 1） - 第一个整数是
0 - 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ，且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
示例 1：
输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同
示例 2：
输入：n = 1
输出：[0,1]
提示：
1 <= n <= 16
代码：
fn gray_code(n: u32) -> Vec<i32> { let l = 1 << n; let mut res: Vec<i32> = vec![0; l as usize]; for i in 0..l { res[i as usize] = ((i >> 1) ^ i) as i32; } res } fn main() { println!("{:?}", gray_code(2)); println!("{:?}", gray_code(1));
输出：
[0, 1, 3, 2]
[0, 1]
90. 子集 II Subsets II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
代码：
fn subsets_with_dup(nums: &mut Vec<i32>) -> Vec<Vec<i32>> { nums.sort(); let mut res: Vec<Vec<i32>> = vec![]; for k in 0..=nums.len() { let mut c: Vec<i32> = vec![]; generate_subsets_with_dup(nums, k, 0, &mut c, &mut res); } res } fn generate_subsets_with_dup(nums: &Vec<i32>, k: usize, start: usize, c: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) { if c.len() == k { let b: Vec<i32> = c.to_vec(); res.push(b); return; } for i in start..(nums.len() - (k - c.len()) + 1) { if i > start && nums[i] == nums[i - 1] { continue; } c.push(nums[i]); generate_subsets_with_dup(nums, k, i + 1, c, res); c.pop(); } } fn main() { let mut nums: Vec<i32> = vec![1, 2, 2]; let res = subsets_with_dup(&mut nums); println!("{:?}", res); }
输出：
[[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]
🌟每日一练刷题专栏🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：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）暂停更 |
