首页
关于
Search
1
2023 年保研经验贴 [计算机-末九Rank50%-入北计清深-北计直博]
1,114 阅读
2
FreeBSD Kernel-编译环境搭建
424 阅读
3
Linux Kernel-THP阅读分析[Hang up]
407 阅读
4
Linux Kernel-编译调试环境搭建
326 阅读
5
Linux Kernel-源码阅读环境搭建
311 阅读
内核
源码分析
阅读笔记
Rust
语法
习题
读书笔记
深入理解计算机系统
论文
技术之外
开发
rcore-arm
登录
Search
yyi
累计撰写
49
篇文章
累计收到
2
条评论
首页
栏目
内核
源码分析
阅读笔记
Rust
语法
习题
读书笔记
深入理解计算机系统
论文
技术之外
开发
rcore-arm
页面
关于
搜索到
49
篇与
的结果
2024-02-23
rCore-Tutorial #0 实验环境配置
当你看到这个标题,是的,我要开个大坑了,而且难度很高,貌似没有什么现成的资料。ipads著名的chcore是基于arm架构的,但是是C开发的,清华著名的rcore是RISCV架构的,但是是Rust开发的。我想搞一个Rust+AArch64的Kernel,显然,我既不怎么会Rust,又不怎么会ARM,我也就只剩一颗想做的心了。当然,如果最后真的搞不下去,我也想至少把rCore-RISCV这个Lab做完做好。我不知道是迁移chcore更难,还是迁移rcore更难,先选一个吧,迁移chcore面对的是Rust的大量特质要重构,迁移rcore面对的是架构差异,从引导、中断到分页都要重构。但是毕竟是给人写的嘛。这个环境配置Chapter我可能还会慢慢的更新,也可能更的不全,有的小依赖可能随手就安了忘记更新,只能说尽量做吧。希望真的能把这个项目做到最后。0 环境配置 参考链接Rust开发环境配置export RUSTUP_DIST_SERVER=https://mirrors.ustc.edu.cn/rust-static export RUSTUP_UPDATE_ROOT=https://mirrors.ustc.edu.cn/rust-static/rustup curl https://sh.rustup.rs -sSf | sh source "$HOME/.cargo/env" > rustc 1.76.0 (07dca489a 2024-02-04)文档中说必须要nightly版本,关于Nightly版本是什么:Rust版本说明我们也切换到nightlyrustup install nightly rustup default nightly这里出现了个小插曲,VM空间不够了,稍稍扩容一下,没想到扩容也没那么简单插曲这里df -h可以看到sda3已经满了fdisk -l在VMWare的图形化界面操作后运行fdisk /dev/sda 并跟着输入n,然后一路回车,最后p一下n是新建分区,p是打印如果正确新建了一个Linux filesystem分区,按w写入分区表,然后reboot下我发现这么搞太麻烦了,反正我有快照,如果直接干掉sda3的分区表,新建分区,能行么,大胆操作一下fdisk里生效了,df里没生效,根据我搞FreeBSD的经验,要growfs一下resize2fs /dev/sda3插曲结束,大功告成。安装完nightly之后,应该有如下输出(版本号不对无所谓)❯ rustc --version rustc 1.78.0-nightly (3406ada96 2024-02-21)crates换源,不赘述安装rust软件包的时候,原文档只给了 riscv64gc-unknown-none-elf 作为交叉编译的target,我们还要加一个aarch64-unknown-nonerustup target add riscv64gc-unknown-none-elf rustup target add aarch64-unknown-none cargo install cargo-binutils # 后面这俩我这时候不能用清华源 rustup component add llvm-tools-preview rustup component add rust-src这俩都是Tier2的Support,应该不会有太大问题 Platform SupportQEMU环境这东西对我来说比较熟悉,可能会简略一点sudo apt-get install autoconf automake autotools-dev curl libmpc-dev libmpfr-dev libgmp-dev \ gawk build-essential bison flex texinfo gperf libtool patchutils bc \ zlib1g-dev libexpat-dev pkg-config libglib2.0-dev libpixman-1-dev libsdl2-dev \ git tmux python3 python3-pip ninja-build别管有没有了安装一把梭其实纠结了一下,Tutoial给定的是qemu 7.0.0 实验,但是本文撰写时qemu已经是这个状态了:搜了一下,看到了这个:我超,可能是要硬着头皮上Qemu8了,一步到位!(虽然我知道这大概率不是一个明智的选择,比起很低概率会用上的新支持,更大概率是会遇到和教程版本不一致导致的问题,但是谁管呢?真的有人不喜欢用新的东西么?)wget https://download.qemu.org/qemu-8.2.1.tar.xz # 可能会有点慢,有条件上proxy吧 tar xJvf qemu-8.2.1.tar.xz 此时要参考一下qemu的官方文档,看看我们选择啥targets,当然不嫌费劲可以直接全部编译可能不用参考了,就选这四个吧./configure --target-list=riscv64-softmmu,riscv64-linux-user,aarch64-linux-user,aarch64-softmmu make -j16在编译目录的./build目录下即可看到编译完的qemu,添加到PATH中跑起来!git clone git@github.com:rcore-os/rCore-Tutorial-v3.git cd os make run
2024年02月23日
149 阅读
0 评论
0 点赞
2024-02-22
Rust难点笔记 1. 生命周期 [UPD2. 24.2.24]
Rust难点笔记 1. 生命周期说在最前面:这是一篇笔记,而不是教程,难免有不周到的、比较主观的想法,敬请大家批评指正和理解这个系列是支撑我写rCore学习时边写边学产生的笔记,周期会比较长远期计划会包括[生命周期, 宏, 异步, 智能指针, 链表]01 生命周期为什么要有生命周期? Rust的内存机制我们已经很熟悉了。生命周期和引用是强绑定的,就一句话:引用还在的时候,不能让引用的对象消失,从而造成悬垂指针问题因此,我们在编译的时候如果出现一个被引用的对象在其引用前被销毁,就会报 xxx does not live so long的错误,这就是对象存活时间小于引用的生命周期,Rust不允许02 生命周期标注编译器有的时候没办法推断生命周期,需要我们手动标注元素的存活周期。在了解生命周期标注的刚开始,最困扰我的问题就是:我标注的东西,只是一个标注,真的能保证程序安全么带着这个问题开始学看一下最常见的生命周期例子fn max(a: &i32, b: &i32) -> &i32 { if *a > * b { a } else { b } }看到这个函数的第一个结论是:返回值的&i32必须来自于a或b,否则,任何max函数体内创建的变量都会在离开函数时销毁。问题是编译器在编译时无法确定到底来自a还是b(程序员应该预期的是a和b都有可能),此时我们要声明a、b的返回值都是一样的(其实是,至少活的一样长,换句话说,我理解a是三者之间最短的那个的生命周期)在函数后声明生命周期fn max<'a>(a: &'a i32, b: &'a i32) -> &'a i32 { if *a > * b { a } else { b } }此时,我们声明了该函数的两个参数应当和返回值生命周期一样长。考虑如果不是max,是firstfn call_max(a: &i32) -> &i32 { let b = 2; max(a, &b) } fn max<'a>(a: &'a i32, b: &'a i32) -> &'a i32 { a }此时我们只需要要求a的生命周期和返回值一样长了,但是因为标注了a、b都要符合生命周期,导致call_max报错如果改为:fn max<'a, 'b>(a: &'a i32, b: &'b i32) -> &'a i32 { a }call_max就不再会报错了回到报错的case,我们看看为什么因为call_max中,原则上是不能返回b的引用的,b会在call_max退出时销毁。由于调用的时候,a、&b和max的返回值遵循同一个生命周期,rust会取其中最小的,(也就是&b)作为我们标注的生命周期而作为call_max的返回值,其在caller处还可能会被用,但是由于标注最短的原则,它的生命周期只覆盖到call_max函数结尾,这肯定是不行的。而把生命周期改为'b的时候,和'a解绑了,'a和传入call_max的a的生命周期一致,和call_max的返回值一致,而不依赖'b。所以可以通过03 生命周期的函数省略生命周期本来标的就乱七八糟的,编译器会在能推导的情况下生成默认的生命周期https://doc.rust-lang.org/reference/lifetime-elision.html文档里其实介绍了结构和特征的生命周期,但是目测是一法通万法通,先从函数开始可省略的函数参数都有独立生命周期所有参数共用生命后期,生命周期会被直接作用到返回值如果是方法,返回值会和&self的生命周期一致来看看例子第一个例子里是第一条规则,没填就分配独立的第二个例子同理,lvl不是引用,没有生命周期第三个例子,用到了一二两条,给输入参数放了个'a,而入参只有'a 一个生命周期第四个例子还是第一条规则这个用到了一三,如果有&Self,会和&Self的生命周期一致第一个例子无法为输出推断生命周期,因为没有输入第二个例子无法推断生命周期,因为s和t的生命周期默认独立,不能推断返回值的04 结构体生命周期类比函数生命周期,给出一个例子就好懂了struct ImportantExcerpt<'a> { part: &'a str, } fn main() { let novel = String::from("Call me Ishmael. Some years ago..."); let first_sentence = novel.split('.').next().expect("Could not find a '.'"); let i = ImportantExcerpt { part: first_sentence, }; }这个例子说明part必须和持有它的结构体活的至少一样久而这个代码就过不了#[derive(Debug)] struct ImportantExcerpt<'a> { part: &'a str, } fn main() { let i; { let novel = String::from("Call me Ishmael. Some years ago..."); let first_sentence = novel.split('.').next().expect("Could not find a '.'"); i = ImportantExcerpt { part: first_sentence, }; } println!("{:?}",i); }因为结构体本身活到了println处,而part引用只能活到前一个作用域05 方法生命周期struct ImportantExcerpt<'a> { part: &'a str, } impl<'a> ImportantExcerpt<'a> { fn level(&self) -> i32 { 3 } }注意,这里ImportantExcerpt的完整签名是ImportantExcerpt<'a>,生命周期声明也是结构体的一部分所以这里语法类似泛型06 几个不太聪明的例子例子来自course.rsRust的生命周期面对某些特定情况,可能不够聪明,比如:#[derive(Debug)] struct Foo; impl Foo { fn mutate_and_share(&mut self) -> &Self { &*self } fn share(&self) {} } fn main() { let mut foo = Foo; let loan = foo.mutate_and_share(); foo.share(); println!("{:?}", loan); }传入的虽然是可变借用,但是返回时实际上是一个不可变借用,所以理论上来说最终是不可变的share处又进行了一次不可变借用,语义上说,两个不可变借用是没问题的,但是显然编译器不会那么听我的话mut函数的生命周期标注实际上是这样的: fn mutate_and_share<'a>(&'a mut self) -> &'a Self { &'a *self }代表返回值loan和foo的可变借用 &mut self 生命周期相同,所以loan存续期间, &mut self也一直存续虽然本身是个安全的东西,但是现在还没有机制支持,只能按我们标注的情况判定为不合法了。再来看一个#![allow(unused)] fn main() { use std::collections::HashMap; use std::hash::Hash; fn get_default<'m, K, V>(map: &'m mut HashMap<K, V>, key: K) -> &'m mut V where K: Clone + Eq + Hash, V: Default, { match map.get_mut(&key) { Some(value) => value, None => { map.insert(key.clone(), V::default()); map.get_mut(&key).unwrap() } } } } 第一个map.get_mut(&key) 调用完成后,map的可变借用就可以结束了,但是因为我们的声明,这个借用一直存续到函数结束因此map.insert() 会报错,因为产生了另一个可变借用。
2024年02月22日
88 阅读
0 评论
0 点赞
2024-02-22
Rust入门笔记 6. 迭代器方法
在这段时间练习Rust过程中,大量的简单易用的迭代器方法让我觉得非常优美(尽管这么写起来可能一点都不好读),决定单开一篇整理一下迭代器的方法迭代器是什么所有实现了特征Iterator的类型都算迭代器,即使还没用过迭代器,但是只要用过for循环,就隐式的使用过迭代器了。Rust的for循环是一个语法糖,in后面的对象需要是一个迭代器,for循环反复调用迭代器的next,直到Next返回一个None。为什么要用迭代器而不直接用下标?其实Cpp的STL也大量的使用迭代器,在Rust里,我觉得主要原因是迭代器保证了不会出现越界问题。Rust保证安全性问题是有开销的,Vec每次下标访问都会检查边界,如果超出边界则panic我们平时常用的 a..b, a..=b 也都是迭代器,或者说,它们都是Range,同时实现了Iterator迭代器迭代器方法进入正题,以下列举迭代器方法首先是取元素以及遍历方法nextnext方法是迭代器最基本的功能,让迭代器指向第一个对象,返回一个 Option,它不需要参数,只需要一个Selflet a = vec![1, 2]; let mut iter = a.iter(); assert_eq!(Some(&1), iter.next()); assert_eq!(Some(&2), iter.next()); assert_eq!(None, iter.next());enumerate常用python的话对这个也不会陌生,enumerate同时返回迭代次数和对象,返回值为Option<(usize, Self::Item)>(的一个迭代器),相当于同时帮我们记录了迭代次数。比较常用的情况就是同时需要数组值和下标。fn main() { let vec = vec![222, 546, 231, 666, 10]; for (i, val) in vec.iter().enumerate() { println!("{} : {}", i, val); } } 0 : 222 1 : 546 2 : 231 3 : 666 4 : 10for_each()for_each实际上调用的是fold,它接受一个闭包作为参数,并把每次迭代出的值传递给闭包,作为闭包的参数,它没有返回值(或者说返回值是单元Unit())fn main() { (1..=3).for_each(|x| { print!("{}, ", x); }); } // 1, 2, 3, take()take接受一个参数k,表示取迭代器的前k个元素,返回的是一个被截断过的迭代器这个方法会获取所有权fn main() { (1..=10).take(4).for_each(|x| { print!("{}, ", x); }); } // 1, 2, 3, 4, nth()、nth_back()返回的是剩余元素中第k个(倒数第k)位置的元素,并跳到(k的)下一个位置,中间所有的元素都会被消费fn main() { let vec = vec![222, 546, 231, 666, 10]; let mut iter = vec.iter(); println!("{:?}", iter.nth(2)); println!("{:?}", iter.nth(0)); assert_eq!(iter.nth(0), Some(&10)); assert_eq!(iter.nth(0), None); } // Some(231) // Some(666)fn main() { let vec = vec![222, 546, 231, 666, 10]; let mut iter = vec.iter(); println!("{:?}", iter.nth_back(2)); println!("{:?}", iter.nth(1)); assert_eq!(iter.nth(0), None); } // Some(231) , 此时231, 666, 10都被消费了,iter还在开头 // Some(546)last()只取迭代器的最后一个元素,会消费整个迭代器。当然,返回的也是Option\<Self::Item\>以下是变换方法rev()翻转整个迭代器vec![0, 1, 2, 3, 4].iter().rev().for_each(|x|print!("{x}, ")); // 4, 3, 2, 1, 0, skip(k)跳过k个元素,相当于take的补assert_eq!(vec![2,3], (0..4).skip(2).collect::<Vec<_>>());step_by(k)调整迭代器步长//0, 2, 4, 6, 8, 10, (0..=10).step_by(2).for_each(|x| print!("{x}, "));zip()把两个迭代器合并为一个元组的迭代器let it = [1,3,5].iter().zip([2,4,6].iter()); it : vec![(&1,&2),(&3,&4),(&5,&6)]filter()接受一个闭包,把元素一个个传给闭包,该闭包返回一个个bool,留下所有闭包返回true的元素,组成一个迭代器(0..=10).filter(|x| x % 3 == 0) // 还是个迭代器,[0, 3, 9]collect()我意识到我要先说collect,不然只能用for说明结果还是迭代器collect把一个迭代器的元素组成一个新的集合,具体组合成啥由程序员指定或者由编译器推导(Rust的推导能力我觉得还是很强大的)let vec = (0..=100).collect::<Vec<_>>(); // 默认i32,0-100的一个vecmax()、sum()、min()、count()找到迭代元素里的最大值和求和(最小值、元素个数),sum需要指定结果类型let vec = vec![1, 5, 3, 4, 2]; let max = vec.iter().max().unwrap(); // 5 let sum = vec.iter().sum()::<i32>(); // 15all()、any()接受一个闭包,和filter一样的,区别是这两个是返回一个bool而不是一个迭代器,分别代表是否所有元素都满足闭包、是否由元素满足闭包find()接受一个和filter一样的闭包,区别是filter返回全部的迭代器,find返回第一个满足条件的元素map()、filter_map()map()接受一个闭包,把元素逐个传进闭包,把闭包的返回值组成一个迭代器。对于filter_map()来说,不会把None的东西压进迭代器,实现filter的能力fn main() { let numbers = vec![1, 2, 3, 4, 5]; // 使用 filter_map 方法将所有偶数映射为它们的平方根 let results: Vec<_> = numbers.iter().filter_map(|&x| { if x % 2 == 0 { Some((x, (x as f64).sqrt())) } else { None } }).collect(); println!("Filtered and mapped: {:?}", results); }flat_map()flat_map也是接受一个闭包,不过返回的是一系列迭代器,并把他们拍扁成一个迭代器fn main() { let words = vec!["hello", "world", "rust"]; let chars: Vec<_> = words.iter().flat_map(|&word| word.chars()).collect(); println!("{:?}", chars); // ['h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd', 'r', 'u', 's', 't'] }partition()根据闭包的布尔条件分拆成两个集合fn main() { let numbers = vec![1, 2, 3, 4, 5]; // 使用 partition 方法将奇数和偶数分开 let (even, odd): (Vec<_>, Vec<_>) = numbers .into_iter() .partition(|&x| x % 2 == 0); println!("Even numbers: {:?}", even); // [2, 4] println!("Odd numbers: {:?}", odd); // [1, 3, 5] } scan()、fold()scan和fold都接受两个参数,分别是初始值和一个闭包,传入闭包两个参数:累加值和当前元素区别是scan会把每次闭包返回的结果放一起,最后生成一个迭代器,而fold返回最终的结果fn main() { let numbers = vec![1, 2, 3, 4, 5]; // 使用 scan 方法计算累加和 let cumulative_sum: Vec<_> = numbers.iter().scan(0, |acc, &x| { *acc += x; Some(*acc) }).collect(); println!("{:?}", cumulative_sum); // [1, 3, 6, 10, 15] } fn main() { let numbers = vec![1, 2, 3, 4, 5]; let sum = numbers.iter().fold(0, |acc, &x| acc + x); println!("Sum: {}", sum); // 输出 15 }
2024年02月22日
69 阅读
0 评论
0 点赞
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日
71 阅读
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日
80 阅读
0 评论
0 点赞
1
2
3
4
...
10