首页
关于
Search
1
2023 年保研经验贴 [计算机-末九Rank50%-入北计清深-北计直博]
704 阅读
2
Linux Kernel-THP阅读分析[Hang up]
338 阅读
3
FreeBSD Kernel-编译环境搭建
314 阅读
4
Linux Kernel-编译调试环境搭建
241 阅读
5
Linux Kernel-Zswap 1.功能、流程与原理
233 阅读
内核
源码分析
阅读笔记
Rust
语法
习题
读书笔记
深入理解计算机系统
技术之外
开发
rcore-arm
登录
Search
yyi
累计撰写
46
篇文章
累计收到
0
条评论
首页
栏目
内核
源码分析
阅读笔记
Rust
语法
习题
读书笔记
深入理解计算机系统
技术之外
开发
rcore-arm
页面
关于
搜索到
46
篇与
的结果
2024-02-22
Rust算法练习-LC600/268/316/201/1111
LC1111. Maximum Nesting Depth of Two Valid Parentheses Strings Med给定一个括号序列,让你拆成两份,使得最深的那一个深度最小。感觉是个二分答案,考虑当假设答案为 k 的时候,怎么验证开两个栈,往栈里塞左括号,正常匹配,直到:当这个栈达到 K 的时候,换个栈,继续塞。不过这好像和一个栈也没啥区别啊。。就是判断栈的深度会不会超过 2K 呗那好像不用二分答案了,找到最深的点,/2上取整就是 K,然后栈深 =< k 的是 0,>k的是 1写的有点啰嗦,但比较好理解impl Solution { pub fn max_depth_after_split(seq: String) -> Vec<i32> { let mut stack = vec![]; let mut dep = 0; for i in seq.chars() { if i == '(' { stack.push(1); dep = dep.max(stack.len()); } else { stack.pop(); } } let mut res = vec![0; seq.len()]; dep = (dep >> 1) + (dep & 1); for (i, ch) in seq.chars().enumerate() { if ch == '(' { stack.push(1); if stack.len() > dep { res[i] = 1; } } else { if stack.len() > dep { res[i] = 1; } stack.pop(); } } res } }LC201. Bitwise AND of Numbers Range Med数据范围INTMAX,很显然是要按位做了第i位为1要求[l, r]中的每一个数第i位都为1因此问题转换为了如何判定这件事假设说l的这一位为1,如果l-r这一位都没有发生进位的话,那它仍是1,只要发生了一次进位,那就肯定变0了应该就是这样了,至于怎么判断进没进位呢,对于l的第7位 l(7) = 1000111,应该只要看 (r-l) + l(6) 是否大于 1<<6就行了一遍过,看了俩题解,好像人家写的比我简单多了,惊觉我说的东西就是最长公共前缀,只要求最长公共前缀就行了。代码是原来的思路,不改了、。impl Solution { pub fn range_bitwise_and(left: i32, right: i32) -> i32 { (0..32) .filter(|&i| (left & (1 << i) != 0) && ((right - left) + (left & ((1 << i) - 1)) < 1 << i)) .fold(0, |acc, i| acc | (1 << i)) } }LC316. Remove Duplicate Letters & 1081 Med删掉重复的字母,使得字典序最小,算法应该是比较明显的贪心,考虑下咋贪。这个数据范围才1000,感觉最差情况都可以每次确定一位。考虑一个字母在什么情况下有用。我们肯定是想让最小的在最前,如果前面的都能删那自然不用说,假设说前面有一个不能删呢(假设是字母 k,所有k都在a前面)在这种情况下我肯定希望选择最后一个k前面最小的字母作为首字母。考虑按字母扫数组,从a开始首先考虑a能不能是最小的,充要条件是第一个a前面的每个字母都在a后面出现过。如果能,则选择a,否则看b,条件一致。一直到选出第一个字母为止,删掉所有该字母前面的,和后面所有的该字母。结果最长26,对于每个26,都有26*1000,复杂度应该是够的。但是写起来比较麻烦。看了下Topic,有个单调栈,考虑单调栈咋做吧。应该是个单调递增的栈,当遍历到一个新字母,且新字母没出现过,若栈顶字母大于当前字母:栈顶字母在后面还有,弹出栈顶字母后面没有了,不能弹压入新字母impl Solution { pub fn remove_duplicate_letters(s: String) -> String { let mut stack = vec![]; let mut vis = vec![0; 26]; let mut last = vec![0; 26]; for (i, ch) in s.bytes().enumerate() { last[(ch - b'a') as usize] = i; } for (i, ch) in s.bytes().enumerate() { // println!("{:?}", stack); if vis[(ch - b'a') as usize] != 0 { continue; } while let Some(&top) = stack.last() { if top > ch && last[(top - b'a') as usize] > i { stack.pop(); vis[(top - b'a') as usize] = 0; } else { break; } } stack.push(ch); vis[(ch - b'a') as usize] = 1; } String::from_utf8(stack).unwrap() } }LC268. Missing Number Easy这题方法太多了。impl Solution { pub fn missing_number(nums: Vec<i32>) -> i32 { let n = nums.len() as i32; (n+1) * (n) / 2 - nums.iter().sum::<i32>() } }LC600. Non-negative Integers without Consecutive Ones Hard是不是一个32位的dp啊...dpi 表示由i位组成的数字,最后一位是0/1共有多少个符合题意dpi+1 = dpi, dpi+1 = dpi + dpi;这个DP还能压,dp[i] = dp[i-1] + dp[i-2] (dpi + dpi) = (dpi-1 + dpi-1 + dpi-1) =(dp[i-1] + dpi-1) = (dp[i-1] + dp[i-2])Ans = dp[i]但是这样处理不了正好到n,考虑是不是能暴力或者做一个类似康拓展开的那种处理。感觉还是要做一个康拓展开那种东西随便来个n,考虑怎么加:N = 10011101 (base 2)首先包括 dp[7] : (0000000-01111111),全都比N小之后固定第一位,包括dp[5]: (10000000-10001111),全都比N小,且和上面的不重大概就这个思路, 但是有一类情况可能得特殊考虑,比如说这个dp[4] 可能就不能包括全进来,因为第五位是1发现对于这种情况,后面要考虑的:(10001000-10001011)再下一个就是 (10001100-...)了,这些后面的肯定都不满足,都不用带了impl Solution { pub fn find_integers(mut n: i32) -> i32 { let mut f = vec![0; 31]; f[0] = 1; f[1] = 1; for i in 2..31 { f[i] = f[i-1] + f[i-2]; } let mut res = 0; let mut last = 0; for i in (0..=29).rev() { let val = 1 << i; if (n & val) != 0 { n -= val; res += f[i + 1]; if last == 1 { break; } last = 1; } else { last = 0; } if i == 0 { res += 1; } } res } }
2024年02月22日
62 阅读
0 评论
0 点赞
2024-02-21
Rust算法练习-LCWeekly 385 & 一系列Ez Bits题
一系列Ez Bits题LC231. Power of Twoimpl Solution { pub fn is_power_of_two(mut n: i32) -> bool { let mut cnt = 0; if n <= 0 { return false; } while n > 0 { cnt += n & 1; n >>= 1; } return cnt == 1; } }LC191. Number of 1 Bitsimpl Solution { pub fn hammingWeight (mut n: u32) -> i32 { let mut cnt = 0; while n > 0 { cnt += n & 1; n >>= 1; } return cnt as i32; } }LC338. Counting Bits递推impl Solution { pub fn count_bits(n: i32) -> Vec<i32> { let n = n as usize; let mut dp = vec![0; n+2]; dp[1] = 1; for i in 1..=n >> 1 { let to = i << 1; dp[to] = dp[i]; dp[to + 1] = dp[i] + 1; } dp[..n+1].to_vec() } }还没直接暴力来得快impl Solution { pub fn count_bits(n: i32) -> Vec<i32> { (0..=n).map(|i| i.count_ones() as i32).collect() } }LC190. Reverse BitsRust标准里有这玩意。。impl Solution { pub fn reverse_bits(x: u32) -> u32 { x.reverse_bits() } }LCWeekly Contest 385Count Prefix and Suffix Pairs I&II Ez & Hardimpl Solution { pub fn count_prefix_suffix_pairs(words: Vec<String>) -> i32 { let mut res = 0; for i in 0..words.len() { for j in i+1..words.len() { if words[j].starts_with(&words[i]) && words[j].ends_with(&words[i]) { res += 1; } } } res } }Hard的数据比较水,用Map维护一下相同值就行。。。就算正解也比较简单,用个Trie即可,只不过子节点索引不是字符,是(ch[x], ch[len-x-1])Find the Length of the Longest Common Prefix Med感觉是个字典树,按A建树,B往里跑,跑到哪算哪struct Trie { root: TrieNode, } struct TrieNode { children: std::collections::HashMap<String, TrieNode>, count: i32, } impl Trie { fn new() -> Self { Trie { root: TrieNode { children: std::collections::HashMap::new(), count: 0, }, } } fn insert(&mut self, s: String) { let mut node = &mut self.root; for c in s.chars() { node = node.children.entry(c.to_string()).or_insert(TrieNode { children: std::collections::HashMap::new(), count: 0, }); node.count += 1; } } } impl Solution { pub fn longest_common_prefix(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 { let mut trie = Trie::new(); for i in 0..arr1.len() { trie.insert(arr1[i].to_string()); } let mut res = 0; for i in 0..arr2.len() { let mut node = &trie.root; let mut now = 0; for j in arr2[i].to_string().chars() { if let Some(n) = node.children.get(&j.to_string()) { node = n; now += 1; } else { break; } } res = res.max(now); } res as i32 } }Most Frequent Prime Med妈的,一开始在小点上T,我脑子没转过来,埃筛和线筛都还给老师了。。比赛打完也没过,不知道为啥T了Upd: 统计不用vec,用HashMap就过了。。。比赛实在来不及了use super::Solution; impl Solution { pub fn most_frequent_prime(mat: Vec<Vec<i32>>) -> i32 { let dirs = vec![ (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1), ]; let (m, n) = (mat.len(), mat[0].len()); let mut is_prime = vec![true; 1000000 + 1]; is_prime[0] = false; is_prime[1] = false; let mut p = 2; while p * p <= 1000000 { if is_prime[p] { let mut i = p * p; while i <= 1000000 { is_prime[i] = false; i += p; } } p += 1; } let mut res = vec![0; 1000001]; for i in 0..m { for j in 0..n { for dir in &dirs { let (mut x, mut y) = (i as i32, j as i32); let mut num = 0; while x >= 0 && x < m as i32 && y >= 0 && y < n as i32 { num = num * 10 + mat[x as usize][y as usize]; if is_prime[num as usize] { res[num as usize] += 1; } x += dir.0; y += dir.1; } } } } let mut max = 0; let mut ans = 0; for i in 10..=1000000 { if is_prime[i] && res[i] >= max { max = res[i]; ans = i; } } if max == 0 { return -1; } ans as i32 } }
2024年02月21日
62 阅读
0 评论
0 点赞
2024-02-20
FreeBSD Arch Handbook阅读笔记 #7 VM
https://docs.freebsd.org/en/books/arch-handbook/vm/7.1 vm_page_tvm_page_t 管理物理内存,每个vm_page_t对应一个物理页面,vm_page_t属于不同双向链表队列。主要包括活动、非活动、缓存或空闲。缓存和空闲的分页队列更加复杂,会根据L1和L2 Cache的大小分成多个队列。申请新页面的时候也会从Cache的角度来申请对齐的页面。页面通过引用计数持有,通过繁忙计数锁定。VM system通过LRU来对页面进行降级。对于Weird类型的页面,不在队列里,通常是载有一个页表。空闲链表里的页面是真正空闲的,而Cache链表里的页面随时可被重用。当进程访问一个不在页表里的页面时,如果页面在页面队列里,页错误就会导致更少的开销。否则只能从外存读入了。pageout守护进程负责:动态调整分页队列、维持各个队列页面合理比例维持脏页面和干净页面的细分(清洗脏页、升降级)VM会尝试在产生合理的页错误量级的前提下帮助决策何时换出和清洗页面。7.2 vm_object_tFreeBSD实现了一个通用内存对象,这个对象的backend可以是:TypesunbackedSwap-backedPhysical device backedFile-backedVM对象可以被遮蔽,具体可以看我的另一篇笔记https://yirannn.com/source_code/vm_sys.html比较常见的应用就是cow一个vm_page_t同时只能和一个vm_object关联。而不同实例的内存共享由遮蔽特性提供7.3 struct buf对于vnode作为back的vm对象,比如file,对脏页信息的维护和vm对脏页信息的维护是相互独立的。在写回脏页时,vm需要在写回前清除dirty标记。另外文件也需要将文件映射到KVM才能进行操作,这种结构被称为文件系统缓冲区,一般是struct buf,文件系统需要对VM进行操作时,把这个vm对象转换为一个buf,然后把buf中的页面映射在KVM里。同理,磁盘IO也是先把vm_object映射到buf,再在buf上发出IO。7.4 vm_map_t, vm_entry_tFreeBSD通过vm_map_t结构把object和虚拟内存范围相关联,页表通过vm_map_t/vm_entry_t/vm_object_t 直接合成。这一段我其实没太读懂,但是我感觉笔者意思是一个物理页不光是和一个vm_object联系,同时也和页表项联系。但是对于同个object的同个页面,对应的vm_page_t都相同7.5 KVM 内存映射FreeBSD用KVM保存内核结构,其中最大的就是7.3中提到的buf。FreeBSD不会把所有物理内存都映射到KVM,主要利用区域分配器管理KVM
2024年02月20日
73 阅读
0 评论
0 点赞
2024-02-18
Rust入门练习-Week9-LC1642/739/150/1074/2402
LC2402. Meeting Rooms III Hard一开始还以为是经典的排序贪心,+魔改,细读之后发现应该不是。感觉就是个模拟,因为时间范围是可枚举的最开始把所有会议按开始时间塞堆里,对于一个时间点: 遍历所有会议室,踢出已经开完会的若所有会议室都满,跳过若堆顶时间小于等于当前时间,且有空会议室,安排之,会议室k的结束时间设置为now + length考虑了下题目条件,完全不必按时间枚举,按第一维排序之后按会议枚举应该就可以,每次要找到最早结束的会议室,还是要用个堆小脑萎缩了,被倒数第二个点卡了十多分钟,最后发现爆intuse std::{cmp::Reverse, collections::BinaryHeap}; impl Solution { pub fn most_booked(n: i32, mut meetings: Vec<Vec<i32>>) -> i32 { let mut visits = vec![0; n as usize]; let mut heap = BinaryHeap::new(); let n = n as usize; meetings.sort_unstable(); for i in 0..n { heap.push(Reverse((0 as i64, i))); } for i in meetings { while let Some(Reverse((time, idx))) = heap.peek() { let (time, idx) = (*time, *idx); if time < i[0] as i64{ heap.pop(); heap.push(Reverse((i[0] as i64, idx))); } else { break; } } if let Some(Reverse((time, idx))) = heap.pop() { let end_time = time + (i[1] - i[0]) as i64; visits[idx] += 1; heap.push(Reverse((end_time, idx))) // println!("meeting {:?} held in {}, to {}", i, idx, end_time); } } visits.iter().enumerate().max_by_key(|x| (x.1, -(x.0 as i32))).unwrap().0 as i32 } }LC1074. Number of Submatrices That Sum to Target Hard虽然是Hard,但是我感觉 N^4 + 矩阵前缀和就能做,常数应该不大的。考虑sumx 是 (0, 0) 到 (x, y) 的前缀和,求 (a, b) 到 (x, y) 的前缀和是sumx + suma-1 - sumx - suma-1怎么说呢。。这还打败96%impl Solution { pub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, target: i32) -> i32 { let mut sum = vec![vec![0; matrix[0].len() + 1]; matrix.len() + 1]; for i in 1..=matrix.len() { for j in 1..=matrix[0].len() { sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; } } let mut res = 0; for i in 0..=matrix.len() { for j in 0..=matrix[0].len() { for k in 0..i { for l in 0..j { if sum[i][j] - sum[k][j] - sum[i][l] + sum[k][l] == target { res += 1; } } } } } res } }LC150. Evaluate Reverse Polish Notation Med给个后缀表达式,算值impl Solution { pub fn eval_rpn(tokens: Vec<String>) -> i32 { let mut stack = vec![]; for i in tokens { let val = i.parse().unwrap_or(-300); if val == -300 { let (rval, lval) = (stack.pop().unwrap(), stack.pop().unwrap()); let res = match i.as_str() { "+" => lval + rval, "-" => lval - rval, "*" => lval * rval, "/" => lval / rval, _ => panic!("Invalid operator"), }; stack.push(res); } else { stack.push(val); } } stack.last().cloned().unwrap() } }LC739. Daily Temperatures MedFind all j for i s.t. temp[j] > temp[i], 感觉是个单调数据结构从右往左,如果有 temp[i] temp[j], 如果 i < j && temp[i] > temp[j] ,那j就一定没用了,所有i之前的答案最长是i,不会到j倒过来想比较不那么顺畅,有个基本的思路之后我们可以考虑正过来。维护一个单调递减的单调栈对于当前扫到的i,如果栈顶低于i,pop栈顶,维护pop的结果,如果高于i,push进去impl Solution { pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> { use std::collections::VecDeque; let mut res = vec![0; temperatures.len()]; let mut stack = VecDeque::new(); for i in 0..temperatures.len() { while !stack.is_empty() && temperatures[i] > temperatures[*stack.back().unwrap()] { let idx = stack.pop_back().unwrap(); res[idx] = (i - idx) as i32; } stack.push_back(i); } res } }LC1642. Furthest Building You Can Reach Med感觉挺明显是个贪心,我们肯定是要在高度差更大的楼上用梯子,少的地方用砖,只不过不能简单的排序,因为不一定能达到某个位置我的策略是全用砖,并把用砖的数量扔堆里,当砖不够的时候,就从堆顶取出一些砖,然后放上一个梯子死活被卡一个点,leetcode数据太水了,考虑我这个策略是不是有问题假设说我们在之前把梯子都用光了,会不会出现应该把梯子拿到现在这块的情况呢?应该是不会的,因为如果用了梯子,一定是砖不够了,就算把梯子放在新位置,原来也会断。日,被脑瘫GPT3.5骗了,它骗我BinHeap是小根堆这些个if-else不太优雅,合并下同类项use std::collections::BinaryHeap; impl Solution { pub fn furthest_building(heights: Vec<i32>, mut bricks: i32, mut ladders: i32) -> i32 { let mut heap = BinaryHeap::new(); for i in 1..heights.len() { if heights[i] > heights[i-1] { let diff = heights[i] - heights[i-1]; if diff <= bricks { bricks -= diff; heap.push(diff); println!("{} use {} bricks, {} left", i, diff, bricks); } else if let Some(&val) = heap.peek() { if val > diff && ladders > 0 { bricks += heap.pop().unwrap(); bricks -= diff; heap.push(diff); ladders -= 1; // println!("{} use {} bricks + 1 ladder, bring {} {} left", i, diff, val, bricks); } else if ladders > 0 { // println!("diff is {}, {} use 1 ladder, {} left", diff, i, ladders); ladders -= 1; } else { return (i-1) as i32 } } else if ladders > 0 { // println!("diff is {}, {} use 1 ladder, {} left", diff, i, ladders); ladders -= 1; } else { // println!("bricks : {}, ladder {} need {}", bricks, ladders, diff); return (i-1) as i32; } } } (heights.len()-1) as i32 } }
2024年02月18日
61 阅读
0 评论
0 点赞
2024-02-16
Rust入门练习-Week8-LC392/1048/389/1481/799
LC799. Champagne Tower Med看了下数据范围,只能是从行列上来入手了,感觉是个递推impl Solution { pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 { let mut dp = vec![vec![0.0; 100]; 100]; let (query_row, query_glass) = (query_row as usize, query_glass as usize); dp[0][0] = poured as f64; for i in 0..query_row { for j in 0..=i { if dp[i][j] > 1.0 { let q: f64 = (dp[i][j] - 1.0) / 2.0; dp[i + 1][j] += q; dp[i + 1][j + 1] += q; } } } dp[query_row][query_glass].min(1.0) } }LC1481. Least Number of Unique Integers after K Removals Med贪心,按出现个数排序,从最少的删impl Solution { pub fn find_least_num_of_unique_ints(arr: Vec<i32>, k: i32) -> i32 { use std::collections::HashMap; let cnt = arr.iter().fold(HashMap::new(), |mut m, x| { *m.entry(x).or_insert(0) += 1; m }); let mut cnts = cnt.iter().map(|(_, &v)| v).collect::<Vec<_>>(); cnts.sort_unstable(); let mut k = k; for i in 0..cnts.len() { if k >= cnts[i] { k -= cnts[i]; cnts[i] = 0; } else { cnts[i] -= k; return cnts[i..].len() as i32; } } 0 } }LC389. Find the Difference Ezuse std::collections::HashMap; impl Solution { pub fn find_the_difference(s: String, t: String) -> char { let (mut m1, mut m2) = (HashMap::new(), HashMap::new()); for i in s.bytes() { *m1.entry(i).or_insert(0) += 1; } for i in t.bytes() { *m2.entry(i).or_insert(0) += 1; } for i in m2.keys() { if m1.get(i).unwrap_or(&0) != m2.get(i).unwrap() { return *i as char; } } ' ' } } use std::collections::HashMap; impl Solution { pub fn find_the_difference(s: String, t: String) -> char { let m1 = s.bytes().fold(HashMap::new(), |mut acc, b| { *acc.entry(b).or_insert(0) += 1; acc }); let m2 = t.bytes().fold(HashMap::new(), |mut acc, b| { *acc.entry(b).or_insert(0) += 1; acc }); m2.iter() .find(|&(k, v)| m1.get(k).unwrap_or(&0) != v) .map(|(&k, _)| k as char) .unwrap() } }LC1048. Longest String Chain Med最多1000个词,答案最多16项,考虑dp先按长度排个序,分割一下,wordsi表示第j个长度为i的单词dpi 表示目前长度为i,使用了第j个单词的可达性dpi -> dpi+1 if j -> k最后倒序看dp[i] 是否存在true复杂度N^2乘个常数可过,这常数均摊应该不大的惭愧,这代码基本上都是Copilot写的,我就写了点注释,改了改bugimpl Solution { pub fn longest_str_chain(words: Vec<String>) -> i32 { // a closure to check if a word is a predecessor of another word let is_predecessor = |a: &str, b: &str| -> bool { if a.len() + 1 != b.len() { return false; } let mut i = 0; let mut j = 0; let mut diff = 0; while i < a.len() { if a.chars().nth(i).unwrap() != b.chars().nth(j).unwrap() { diff += 1; if diff > 1 { return false; } j += 1; } else { i += 1; j += 1; } } true }; // separate words by length let mut words_by_length: Vec<Vec<String>> = vec![vec![]; 17]; for word in words.iter() { words_by_length[word.len()].push(word.clone()); } // dp[i][j] is the if length i string can ending with words_by_length[i][j] let mut dp: Vec<Vec<i32>> = vec![vec![1; 1000]; 17]; let mut max_chain = 1; for i in 1..17 { for j in 0..words_by_length[i].len() { for k in 0..i { for l in 0..words_by_length[k].len() { if is_predecessor(&words_by_length[k][l], &words_by_length[i][j]) { dp[i][j] = dp[i][j].max(dp[k][l] + 1); max_chain = max_chain.max(dp[i][j]); } } } } } max_chain } }LC392. Is Subsequence Ezimpl Solution { pub fn is_subsequence(s: String, t: String) -> bool { let (mut p1, mut p2) = (0, 0); let (s, t) = (s.as_bytes(), t.as_bytes()); while p1 < s.len() && p2 < t.len() { if s[p1] == t[p2] { p1 += 1; } p2 += 1; } p1 == s.len() } }
2024年02月16日
65 阅读
0 评论
0 点赞
1
2
3
4
...
10