模拟比赛,1:33:00(超时3分钟),no dirty,第一名时间 0:10:40。。。猫猫疑惑,写同样的题目花人家9倍时间,酱紫慢?
rust snippet:
- 从 vec 构建 hashset:
HashSet::
,里面也可以是 .iter.clone()::from_iter(nums1.into_iter()); - reverse string:
.chars().rev().collect::
() - string 不能加 string,但可以加 &str,可以用
&
或者 .as_ref() 转 - 没找到优雅的在 vec 前面插入零的链式方法。
update:问了nb群友得到了答案,std::iter::once(0).chain(...)
就行。
链式写法相比 c++ 确实太爽了。
tips:
- 遇事不决开始 dp,先从慢的方法想起,注意题目数据范围隐含的时间复杂度要求,可能慢的也可以
- 二维 dp 可以考虑滚动数组,或者原地 dp 来节省空间。
2215 找出两数组的不同
impl Solution {
pub fn find_difference(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<Vec<i32>> {
use std::collections::HashSet;
use std::iter::FromIterator;
let nums1 = HashSet::<i32>::from_iter(nums1.into_iter());
let nums2 = HashSet::<i32>::from_iter(nums2.into_iter());
vec![
nums1.iter().filter(|&x| !nums2.contains(x)).map(|&x| x).collect(),
nums2.iter().filter(|&x| !nums1.contains(x)).map(|&x| x).collect(),
]
}
}
2216 美化数组的最少删除数
impl Solution {
pub fn min_deletion(nums: Vec<i32>) -> i32 {
/*
dp[i] = nums[0..=i] 已经被删了若干,剩下一个子序列,长度为偶数且满足要求,的最小删除数。
dp[0] = 1
dp[1] = a[0] == a[1] ? 2 : 0
dp[2] = min(dp[0] + a[1]==a[2]?2:0, dp[1]+1);
dp[i] = min(dp[i-2] + a[i-1]==a[i]?2:0, dp[i-1]+1);
*/
let mut dp = vec![0; nums.len()];
dp[0] = 1;
if nums.len() > 1 {
dp[1] = if nums[0] == nums[1] {2} else {0};
}
for i in 2..nums.len() {
dp[i] = std::cmp::min(dp[i-2] + if nums[i] == nums[i-1] {2} else {0}, dp[i-1] + 1);
}
dp[nums.len()-1]
}
}
2217 找到指定长度的回文数
impl Solution {
fn kth_palindrome_helper(query: i32, len: i32) -> i64 {
if len % 2 == 0 {
if query > 9 * i32::pow(10,len as u32 / 2 - 1) {
return -1;
}
let num = i32::pow(10, len as u32 / 2 - 1) + query - 1;
let str = num.to_string() + num.to_string().chars().rev().collect::<String>().as_ref();
return str.parse::<i64>().unwrap();
}
if query > 9 * i32::pow(10,len as u32 / 2) {
return -1;
}
let num = i32::pow(10, len as u32 / 2) + query - 1;
let str = num.to_string() + num.to_string().chars().rev().collect::<String>()[1..].as_ref();
return str.parse::<i64>().unwrap();
}
pub fn kth_palindrome(queries: Vec<i32>, int_length: i32) -> Vec<i64> {
queries.iter().map(|&x| Solution::kth_palindrome_helper(x, int_length)).collect()
}
}
2218 从栈中取出 K 个硬币的最大面值和
impl Solution {
pub fn max_value_of_coins(piles: Vec<Vec<i32>>, k: i32) -> i32 {
let k = k as usize;
/*
dp[i][j] 在 0..=i 中取 j 个硬币的最大价值
答案是 dp[n-1][k]
dp[i][j] = max_{u=0..=min(j, piles[i].len())} dp[i-1][j-u] + piles_sum[i][u]
note, sum[0] = 0.
*/
let sum = piles.iter().map(
|pile| {
let mut t = pile.iter().scan(
0, |acc, &x| {*acc += x; Some(*acc)}
).collect::<Vec<i32>>();
t.insert(0, 0);
t
}
).collect::<Vec<Vec<i32>>>();
let mut dp = vec![vec![0; k+1]; piles.len()];
for i in 0..piles.len() {
if i == 0 {
for j in 0..=k.min(piles[0].len()) {
dp[i][j] = sum[i][j];
}
continue;
}
for j in 0..=k {
for u in 0..=j.min(piles[i].len()) {
dp[i][j] = dp[i][j].max(dp[i-1][j-u] + sum[i][u]);
}
}
}
dp[piles.len() - 1][k]
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)