首页
关于
Search
1
2023 年保研经验贴 [计算机-末九Rank50%-入北计清深-北计直博]
349 阅读
2
Linux Kernel-THP阅读分析[Hang up]
255 阅读
3
FreeBSD Kernel-编译环境搭建
223 阅读
4
Linux Kernel-编译调试环境搭建
176 阅读
5
Linux Kernel-Zswap 1.功能、流程与原理
156 阅读
内核
源码分析
阅读笔记
Rust
语法
习题
读书笔记
深入理解计算机系统
技术之外
开发
rcore-arm
登录
Search
yyi
累计撰写
46
篇文章
累计收到
0
条评论
首页
栏目
内核
源码分析
阅读笔记
Rust
语法
习题
读书笔记
深入理解计算机系统
技术之外
开发
rcore-arm
页面
关于
搜索到
12
篇与
的结果
2024-01-05
Rust入门练习-Week2-LC1359/1282/1647/135/49
LC49. Group Anagrams Med把拥有相同字母的词(eg. eat, ate)放一起返回。每个单词长度 100,10^4个考虑给每个单词中的字母排个序(eg. 都变成 aet)再做 hash,hash 相同的扔一起。排序是 100log100 10^4, 哈希总共100 * 10^4,应该刚好能跑下来。然后发现排完序就可以直接扔 HashMap 了use std::collections::HashMap; impl Solution { pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> { let mut hash_table = HashMap::new(); for i in &strs { let mut sorted_str: Vec<char> = i.chars().collect(); sorted_str.sort(); hash_table.entry(sorted_str).or_insert(Vec::new()).push(i.to_string()); } hash_table.into_values().collect() } }LC135. Candy Hard好像是经典题,资本家发糖果。一开始感觉从左边开始贪心就行了。记录一下上一个人发了多少,这个人如果分更低,直接打回 1,否则就在刚刚的基础上+1,但是稍微一想就不对,如果打回 1,但是他又比右边人更高就不好办了。那是权为 1 的差分约束?n 个点 2n 个边,有点太大了,应该也不是。不过这样让我感觉贪心是对的,不能线性扫过去贪,能不能扫两遍呢。两边分别从左右标记,在左侧和右侧去取 max(min)。考虑会不会存在取了 max(min) 之后有两个还是有冲突的情况,感觉是会有的,因为如果一个 a 取了右侧的 min,另一个b (b > a)取了左侧的 min,假设 b 的 min 正好被 a 从左侧的 min 影响,a 又取了更大的值,这个就不合理了。但是这种情况确实会发生么?b 取了被左侧 a 的 min 的影响的前提是 a->b 一直是连续增的,在这种情况下,a 不太可能会从右侧取 min,因为右侧的 min 是 1这样考虑的话,这种 max(min)的思路应该是正确的。use std::cmp::max; impl Solution { pub fn candy(ratings: Vec<i32>) -> i32 { let mut l = vec![0; ratings.len()]; let mut r = vec![0; ratings.len()]; let mut ans = 0; for i in 0..ratings.len() { if i < 1 || ratings[i] <= ratings[i-1] { l[i] = 1; } else { l[i] = l[i-1] + 1; } } for i in (0..ratings.len()).rev() { if i == ratings.len()-1 || ratings[i] <= ratings[i+1] { r[i] = 1; } else { r[i] = r[i+1] + 1; } ans += max(l[i], r[i]); } // println!(" l : {:?}, r : {:?}", l, r); ans } }2ms,但是内存不是很优秀,目测是因为 r 这个数组不必要。LC1647. Minimum Deletions to Make Character Frequencies Unique Med字符串题,一眼贪心,但是怎么贪呢。一开始是以为可以加可以减,想了一会好像不能直接贪,但是一看样例,好家伙,只能减,而且还能减到 0先排序,考虑拥有频率为 k 的序列 f[k] 大概是这样的( f[k] 的值表示有频率为 k 的字母的个数为 f[k] 个)130222000123当我们遍历到 k 的时候,如果比他小的 f[k'] 都不为 0,则它对应的n字母必须有 n-1个删光如果有 m 个 0,可以不用删光,先减到对应的 f[k']=0, k' 上,如果 0 不够再把这个字母删光。如果用模拟的话,着实是非常的不优雅啊,但是因为小写英文字母一共只有 26 个,也就是 sum(f[k]) = 26, 但是 k 的取值范围是 10^5, 速度肯定是够的。看看有没有啥优雅的办法呢好像没有,那写吧use std::collections::HashMap; impl Solution { pub fn min_deletions(s: String) -> i32 { let mut cnt = vec![0; 26]; let mut vis = HashMap::new(); let mut ans = 0; for ch in s.bytes() { cnt[ ch as usize - 'a' as usize ] += 1; } cnt.sort(); for i in &cnt { let mut visit_cnt = vis.entry(*i).or_insert(0); *visit_cnt += 1; } for i in &cnt { let mut i = *i; if i == 0 { continue; } if let mut vis_now = vis.entry(i).or_insert(0) { if *vis_now == 1 { continue; } *vis_now -= 1; i -= 1; ans += 1; loop { let mut visit_cnt = vis.entry(i).or_insert(0); if i == 0 || *visit_cnt == 0 { *visit_cnt = 1; break; } i -= 1; ans += 1; } } } ans } }上次的题虽然不够优雅,但是我还能忍,这道题中间的 for-if-continue-loop 乱套简直就是史!!!真忍不了,这个虽然以Beats100.00%of users with Rust通过,但是我要改改好看。考虑搞个 Set,就不用 Map 了,直接看是否 Contain 当前这个 cntuse std::collections::HashSet; impl Solution { pub fn min_deletions(s: String) -> i32 { let mut cnt = vec![0; 26]; let mut vis = HashSet::new(); let mut ans = 0; for ch in s.bytes() { cnt[ ch as usize - 'a' as usize ] += 1; } for i in 0..26 { while cnt[i] && vis.Contains(cnt[i]) { cnt[i] -= 1; ans += 1; } vis.insert(cnt[i]); } } }好看多了,也慢了LC1282. Group the People Given the Group Size They Belong To Med比较显然吧,对于g[i] = k的,直接扔下标为 k 的位置挂链,最后把每一个链按 k 分组输出。当然,Rust 写链表太疯狂啦,直接二维数组吧。use std::collections::HashMap; impl Solution { pub fn group_the_people(group_sizes: Vec<i32>) -> Vec<Vec<i32>> { let mut group = HashMap::new(); for (i, val) in group_sizes.iter().enumerate() { let mut v = group.entry(val).or_insert(Vec::new()); v.push(i); } // println!("{:?}", group); let mut ans = Vec::new(); for (k, v) in group.iter() { let mut now = Vec::new(); for (i, cur) in v.iter().enumerate() { if i as i32 % **k == 0 { if now.len() != 0 { ans.push(now); now = Vec::new(); } } now.push(*cur as i32); } ans.push(now) } ans } }但是最后获取结果那一块,写的非常的别楞,想想怎么能优雅一点LC1359. Count All Valid Pickup and Delivery Options Hard要模 1e9 + 7,看上去是个数学题。首先我感觉能有一个结论,我们可以假定 P 一定是从 1 到n 的,最后再乘一次 A(n, n),在最开始有序方案的基础上乘一个排列即可感觉这样可以考虑 dp 了,dpi表示 P 已经到 i,D 到 j 的方案数。怎么转移呢。D 不一定有序。但是因为 n 只有 500,我们有很大的复杂度空间,但是感觉 D 还是没法转移。考虑组合数学呢,假设已经有了一组 DP 排列,我们新插入的 DP 是和原来无关的, 已经有 K 个数的情况下,P 可以插到 K+1 个位置,D 在 P 选定的基础上,可以插入到(K+1) + (K) + ... + 1 个位置这样好像就可以算了, 懒得想公式,直接递推过去吧dp[1] = 1, dp[i+1] = dp[i] ((1 + 2i+1) (2i+1)/2)impl Solution { pub fn count_orders(n: i32) -> i32 { let p = 1e9 as i64 +7; let mut ans : i64 = 1; for i in 1..n as i64 { ans = ans * (i + 1) % p * (2 * i + 1) % p; } ans as i32 } }
2024年01月05日
22 阅读
0 评论
0 点赞
2023-12-29
Rust入门练习-Week1-LC387/1696/442/621/377
LC377. Combination Sum IV Med类似于一个完全背包方案数吧。DP给定一系列数字a[i],求用它们组合为 target 的方案数,a[i]可以重复使用状态:dp[i]表示目前已经加和到 i 的方案数转移: dp[i] = sum(dp[i-a[j]])边界条件:dp[0] = 1, ans = dp[target]impl Solution { pub fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 { let mut dp = vec![0; target as usize + 1]; dp[0] = 1; for i in 0..target { for j in &nums { if i+j > target { continue; } dp[(i+j)as usize] += dp[i as usize]; } } dp[target as usize] } }LC621. Task Scheduler Med题目一眼贪心,目的转化为使等待时间最少,考虑一种策略: 把任务 A-Z 按出现的次数排序,并从最多的任务(假设为 M,出现 m 次)开始排列排列必为 M...M...M...M 这类的情况,其中.的数量为 n只要在空缺中插入其他任务,且保证每个空缺不会出现两个相同任务,可知这类的排列必是满足题意的。考虑有任务 X、Y、Z 在这种插入后分别剩 x、y、z 次(显然,任务 X、Y、Z 的总数量都要小于 m)只需要扩充 每两个 M 之间的间隔,直到能插下即可,也必然符合题意,且不会使得等待时间更多。因此问题转化为 (m-1)n > len(tasks)-m ? (m-1)(n+1) : len(tasks)但是这个式子少考虑了如果有任务 K, k = m的情况,只要计数,并在最后累加一下即可(假设有 cnt 个任务都达到了最大值,我们先假设其中 cnt-1 个都只有最大值-1,然后按刚刚的逻辑贪心,最后补 cnt-1 即可)所以我们要做的就是统计每个字母出现的数量并进行排序。我们同过 Rust 的 HashMap 实现该能力。use std::collections::HashMap; impl Solution { pub fn least_interval(tasks: Vec<char>, n: i32) -> i32 { let mut char_count = HashMap::new(); let mut maxn = 0; let mut maxn_cnt = 0; for c in &tasks { let cnt = char_count.entry(*c).or_insert(0); *cnt += 1; maxn = std::cmp::max(*cnt, maxn) } for (_, &v) in &char_count { if v == maxn { maxn_cnt += 1; } } let lhs = (maxn-1) * n; let rhs = tasks.len() as i32 - maxn - maxn_cnt + 1; println!(" {} {} ", maxn, maxn_cnt); if lhs > rhs { return (maxn-1) * (n+1) + maxn_cnt; } else { return tasks.len() as i32; } } }LC442. Find All Duplicates in an Array Med裸的解法:直接扔进桶里,那就开个 Hashmapuse std::collections::HashMap; impl Solution { pub fn find_duplicates(nums: Vec<i32>) -> Vec<i32> { let mut num_count = HashMap::new(); let mut res = Vec::new(); for num in nums { let cnt = num_count.entry(num).or_insert(0); *cnt += 1; if *cnt == 2 { res.push(num); } } res } }但是显然这也太没意思了,就算是面试也不会考你 Map 的使用。其实给了数据范围,开个普通的桶就行,不知道这题为啥也能算中等。。LC1696. Jump Game VI Med一眼 DP,先考虑最朴素的, 状态:f[i]表示已经跳到 i 的最大价值, 转移:f[i]从f[[i-k, i-1]]里更新即可,f[i] = max{f[max(i-k, 0)....i-1]} + nums[i] 边界条件:f[0] = nums[0],ans = f[nums.len()-1]但是这东西是O(nk)的,肯定超时,考虑优化。分析不下去了,这显然是维护前 k 个里最大的,维护一个单调线性结构即可。此结构中的f 的值需要单调减(每次用最左侧的最大值,如果右侧有一个更大的,左侧的值一定没用)。左边出右边进,单调队列即可。use std::collections::VecDeque; struct Node { cur: i32, val: i32, } impl Solution { pub fn max_result(nums: Vec<i32>, k: i32) -> i32 { let mut f = vec![0; nums.len()]; let mut q = VecDeque::new(); q.push_back(Node { cur: 0, val: nums[0] }); f[0] = nums[0]; for i in 1..nums.len() { while !q.is_empty() && q.front().unwrap().cur < i as i32 - k { q.pop_front(); } f[i] = nums[i] + q.front().unwrap().val; while !q.is_empty() && q.back().unwrap().val < f[i] { q.pop_back(); } q.push_back(Node { cur: i as i32, val: f[i] }) } f[nums.len()-1] } }学语法中这块有个小点,就是 q.back() 这类的方法,返回的应该是个Option,我们直接 unwrap() 把 OK 中的值拿回来,如果拿不回来就直接 panic。Option类型是Rust的一个枚举类型,它有两个值:Some(T)和None。Option类型常常用于表示可能存在也可能不存在的值。q.back()和q.front()的返回值类型都是Option<&T>,其中T是队列中元素的类型。这是因为当队列为空时,back()和front()方法没有元素可以返回,所以它们返回的是None。当队列不为空时,back()和front()方法可以返回队列的尾部和头部元素,所以它们返回的是Some(&T)。在处理Option类型时,除了模式匹配和unwrap()方法,还有很多其他的方法,比如unwrap_or()、unwrap_or_else()、map()、and_then()等等。LC387 First Unique Character in a String Ezimpl Solution { pub fn first_uniq_char(s: String) -> i32 { let mut v = vec![0; 26]; let s_chars: Vec<char> = s.chars().collect(); for &ch in s_chars.iter() { v[(ch as i32 - 'a' as i32)as usize] += 1; } for (i, &ch) in s_chars.iter().enumerate() { if v[(ch as u32 - 'a' as u32) as usize] == 1 { return i as i32; } } -1 } }
2023年12月29日
40 阅读
0 评论
0 点赞
1
2
3