首页
关于
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-02
Rust入门练习-Week6-LC287/1658/3033/3034&3036/2149
LC2149. Rearrange Array Elements by Sign Med好像双指针,但是它没要求常数空间,为什么不直接模拟呢。use super::Solution; impl Solution { pub fn rearrange_array(nums: Vec<i32>) -> Vec<i32> { let pos : Vec<_> = nums.iter().filter(|&&x| x > 0).collect(); let neg : Vec<_> = nums.iter().filter(|&&x| x < 0).collect(); pos.iter() .zip(neg.iter()) .flat_map(|(&a, &b)| vec![a, b]) .cloned() .collect(); } }LC3034&3036. Number of Subarrays That Match a Pattern II Hard & Med两道题区别是数据范围,3034可以n^2,3036要log有一个很明显的性质,即nums相邻两项的关系是固定的,我们可以预处理一个nums2数组, nums2[i] 的 结果和 pattern的1, 0, -1 是一样的。现在变成判断给定n个长度为m的数组,看看有多少个和给定pattern一样这不直接比较哈希值就完事了吗,但是要均摊O(n)的获取这个哈希值把字符串哈希的那种前缀哈希直接照搬过来,预处理一遍然后就可以O1的获取所有哈希了设计hash函数:hash[i+1] = hash[i]*p + nums2[i]已知 hash[r] - hash[l-1] * p^len = hash[l..r]正解:有俩地方要注意,一个是数字里有负数,要带上偏移,都偏到正一个是rust不能溢出,要自己写个快速幂最后看了最快的正解,应该是用KMP,哈希慢了点也能过use super::Solution; impl Solution { fn mod_pow(base: i64, exp: u32, modulus: i64) -> i64 { if modulus == 1 { return 0; } let mut result = 1; let mut base = base % modulus; let mut exp = exp; while exp > 0 { if exp % 2 == 1 { result = result * base % modulus; } exp >>= 1; base = base * base % modulus; } result } pub fn count_matching_subarrays(nums: Vec<i32>, pattern: Vec<i32>) -> i32 { let mut ans = 0; let (n, m) = (nums.len(), pattern.len()); let nums: Vec<i64>= nums.windows(2) .map(|window| match window { [a, b] if a < b => 1, [a, b] if a == b => 0, [a, b] if a > b => -1, _ => unreachable!(), }) .collect(); let base = 13131_i64; let p = 1_000_000_007_i64; let hash = nums.iter().fold(vec![0_i64], |mut hash, &num| { hash.push((hash.last().unwrap() * base + num + 1) % p); hash }); let target_hash = pattern.iter().fold(0_i64, |hash, &num| (hash * base + num as i64 + 1) % p); for i in 0..n { if i + m >= n { break; } let hash =( hash[i + m] - (hash[i] * Self::mod_pow(base, m as u32, p) % p ) + p) % p; if hash == target_hash { ans += 1; } } ans } }暴力:use super::Solution; impl Solution { pub fn count_matching_subarrays(nums: Vec<i32>, pattern: Vec<i32>) -> i32 { let mut ans = 0; let (n, m) = (nums.len(), pattern.len()); for i in 0..(n-m) { let sub_arr = &nums[i..=i+m]; println!("{:?}", sub_arr); let mut res = true; for j in 0..m { if pattern[j] == 1 && sub_arr[j] >= sub_arr[j + 1]{ res = false; break; } else if pattern[j] == 0 && sub_arr[j] != sub_arr[j + 1] { res = false; break; } else if pattern[j] == -1 && sub_arr[j] <= sub_arr[j + 1] { res = false; break; } } if res { ans += 1; } } ans } }LC3033. Modify the Matrix Ez2.11周赛T1impl Solution { pub fn modified_matrix(mut matrix: Vec<Vec<i32>>) -> Vec<Vec<i32>> { for i in 0..matrix.len() { for j in 0..matrix[i].len() { if matrix[i][j] == -1 { matrix[i][j] = matrix.iter() .map(|f| f[j]) .max() .unwrap(); } } } matrix } }LC1658. Minimum Operations to Reduce X to Zero Med在首尾各选一段区间,使得加和结果为x,且区间长度最小。感觉可以二分答案,二分复杂度一个Log,每次验证是滑动窗口数据范围10^5目测正解写完发现,这东西并不单调,竟然这都让我过了二三十个点感觉是双指针,但是这是面试题里我最不擅长的东西了。但是这道题好像还可以两个指针从0开始,如果当前结果太大,r往右,如果当前结果太小,l往右LC287. Find the Duplicate Number Med好像是什么经典题,和之前做过的很像impl Solution { pub fn find_duplicate(mut nums: Vec<i32>) -> i32 { for i in 0..nums.len() { let index = nums[i].abs() as usize; if nums[index] < 0 { return index as i32; } nums[index] = -nums[index]; } return 0; } }
2024年02月02日
64 阅读
0 评论
0 点赞
2024-01-26
Rust入门练习-Week5-LC169/2108/847/1043/1337
LC1337. The K Weakest Rows in a Matrix Ez无视第二条,一个Stable的Sort可以解决// use super::Solution; impl Solution { pub fn k_weakest_rows(mat: Vec<Vec<i32>>, k: i32) -> Vec<i32> { let mut data = mat.iter().enumerate().collect::<Vec<_>>(); data.sort_by_cached_key(|f| f.1.iter().sum::<i32>()); data.iter().take(k as usize).map(|f| f.0 as i32).collect::<Vec<_>>() } }LC1043. Partition Array for Maximum Sum MedN范围500,感觉可以N^2级别的一个DP考虑dp[i] 表示目前已经把i及i之前的数都分割完了,最大的价值由i更新dp[i+j] (1 < j <= k), dp[i+j] = max{dp[i] + j*max{nums[i+1..=i+j], dp[i+j]}边界条件要单独更新一遍dp[0..k];答案是dp[len];// use super::Solution; impl Solution { pub fn max_sum_after_partitioning(arr: Vec<i32>, k: i32) -> i32 { let k = k as usize; let len = arr.len(); let mut dp = vec![0; arr.len()]; for i in 0..k { dp[i] = *arr.iter().take(i+1).max().unwrap() * (i as i32 + 1); } for i in 0..len { let mut max = 0; for j in 1..=k { // dp i -> dp[i+1] .. dp[i+k] if i+j >= len { break; } max = max.max(arr[i+j]); dp[i+j] = dp[i+j].max(dp[i] + max * (j as i32)); } } dp[len-1] } }LC847. Shortest Path Visiting All Nodes Hard太遗憾了,这数据范围应该是一眼状压。。。很难想象这个为啥 Harddpi 表示当前在点 i,状态为 vis的最短路径初始状态dpi = 0, 答案是min{dpi}转移 dpi -> dpi->to + 1想完这个方程发现自己傻了,这路径长度固定为1,直接BFS就行了。impl Solution { pub fn shortest_path_length(graph: Vec<Vec<i32>>) -> i32 { let n = graph.len(); let mut dp = vec![vec![0x3f3f3f3f; 1 << n]; n]; let mut queue = std::collections::VecDeque::new(); for i in 0..n { dp[i][1 << i] = 0; queue.push_back((i, 1 << i)); } while let Some((u, vis)) = queue.pop_front() { for &to in &graph[u] { let to = to as usize; let vis_to = vis | (1 << to); if dp[to][vis_to] > dp[u][vis] + 1 { dp[to][vis_to] = dp[u][vis] + 1; queue.push_back((to, vis_to)); } } } dp.iter() .map(|d| d[(1 << n) - 1]) .min() .unwrap() } }LC2108. Find First Palindromic String in the Array Ez这两天的每日一题都是 Easy,今天打算再加一道遍历数组,找到回文串上面是一个魔怔的函数式解法impl Solution { pub fn first_palindrome(words: Vec<String>) -> String { let check_if_palindrome = |word: &String| { let word: Vec<_> = word.chars().collect(); word.iter().zip(word.iter().rev()).all(|(a, b)| a == b) }; words.iter() .find(|&word| check_if_palindrome(word)) .unwrap_or(&"".to_string()) .clone() } } impl Solution { fn check_if_palindrome(word: &String) -> bool { let word: Vec<_> = word.chars().collect(); let len = word.len(); for i in 0..len { if word[i] != word[len-i-1] { return false; } } return true; } pub fn first_palindrome(words: Vec<String>) -> String { for i in words { if Self::check_if_palindrome(&i) { return i; } } "".to_string() } }LC169. Majority Element Easy线性时间 O1 空间,超过一半的数。感觉很简单,记录当前 num 和 cnt,如果不是当前 num,cnt-1,cnt 为 0 的话换新的 num,最后剩的肯定是答案impl Solution { pub fn majority_element(mut nums: Vec<i32>) -> i32 { let (ans, cnt) = (nums[0], 1); for i in 1..nums.len() { if nums[i] == ans { cnt += 1; } else { cnt -= 1; if cnt == 0 { ans = nums[i]; cnt = 1; } } } ans } }
2024年01月26日
52 阅读
0 评论
0 点赞
2024-01-19
Rust入门练习-Week4-LC76/1463/1291/2966/647
LC76. Minimum Window Substring Hard给定原串 S 和模式 T,取S的一个最小区间,使得 T 中每个字母都在这个子串中出现过。暴力肯定是枚举起终点,考虑转化下,枚举起点和长度,这里长度可以二分答案了。考虑单次验证的复杂度,枚举起点 O(n-ans),遍历O(ans),N^2级别的肯定不行。滑动窗口的话,枚举字符串均摊 O(N),但是对比答案呢,O(alphabet),应该可以最后 60*NlogN,应该是正解了。最后做完看题解正解应该是双指针,O(n+m)impl Solution { fn count_alphabet(s: &String) -> Vec<i32>{ s.chars() .map(|ch| ch as usize - 'A' as usize) .fold(vec![0; 60], |mut count, i| { count[i] += 1; count }) } fn check(len: usize, s: &String, count_t: &Vec<i32>) -> (bool, usize, usize) { let (mut res, mut res_l, mut res_r) = (false, 0, 0); let is_greater_or_equal = |s: &Vec<i32>, t: &Vec<i32>| -> bool { s.iter().zip(t.iter()).all(|(a, b)| a >= b) }; let s: Vec<char> = s.chars().collect(); let mut count_s = Self::count_alphabet(&s[..len].iter().collect()); if is_greater_or_equal(&count_s, count_t) { return (true, 0, len-1); } for i in len..s.len() { // enum the terminal one count_s[s[i] as usize - 'A' as usize] += 1; count_s[s[i-len] as usize - 'A' as usize] -= 1; if is_greater_or_equal(&count_s, count_t) { res = true; res_l = i-len+1; res_r = i; } } (res, res_l, res_r) } pub fn min_window(s: String, t: String) -> String { let count_t = Self::count_alphabet(&t); let (mut l, mut r, mut ans_l, mut ans_r) = (1, s.len(), s.len(), 0); while l <= r { let mid = (l + r) >> 1; let (res, res_l, res_r) = Self::check(mid, &s, &count_t); println!("check {} : {} {} {}", mid, res, res_l, res_r); if res { (ans_l, ans_r) = (res_l, res_r); r = mid - 1; } else { l = mid + 1; } } // println!("result : {} {}", ans_l, ans_r); if ans_l == s.len() { return "".to_string(); } s[ans_l..=ans_r].to_string() // s } }LC1463. Cherry Pickup II Hard最大三角路径的改版,有俩起点,且一个权值只能被获得一次,考虑 DP范围 70*70,状压估计压不下来。本题核心应该就是处理权值不能重复获得。有一个性质我觉得可以利用,就是如果走到同一格,俩人一定是一起到的。考虑状态 dpx1x2,表示 1 号走到 x1y1,2 号走到 x2y2 的最大价值转移按行,dpx1x2 可以从上一行的 {y1-1, y1, y1+1} 和 {y2-1, y2, y2+1}的笛卡尔积获得。初始状态dp00 = val0 + val0按行转移的话,发现 x1 永远是等于 x2 的,可以压一维, dpx[y2],第一维也可以滚动,但是懒得滚动了实际写的时候要注意下,有些格子不可达,枚举的时候扔掉(take用在这了)这个五层循环不太优雅,不过这种 case 感觉也没啥改动空间impl Solution { pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 { let (n, m) = (grid.len(), grid[0].len()); let mut dp = vec![vec![vec![0; m]; m]; n]; dp[0][0][m-1] = grid[0][0] + grid[0][m-1]; for i in 0..n-1 { for y1 in (0..m).take(i+1) { for y2 in (0..m).rev().take(i+1) { for ty1 in y1.saturating_sub(1)..= y1 + 1 { for ty2 in y2.saturating_sub(1)..= y2 + 1 { if ty1 >= m || ty2 >= m { continue; } dp[i+1][ty1][ty2] = std::cmp::max( dp[i+1][ty1][ty2], dp[i][y1][y2] + if ty1 == ty2 {grid[i+1][ty1]} else {grid[i+1][ty1] + grid[i+1][ty2]} ); } } } } } dp[n-1].iter() .flat_map(|row| row.into_iter().copied()) .max() .unwrap() } }LC1291. Sequential Digits Med本来没范围限制,数字分割就好了。但是范围10 ^ 9,考虑其他的枚举方法对于第一个数位是 k,只需拼个 kk+1k+2k+3 (k+l < 10) 即可最后排个序impl Solution { pub fn sequential_digits(low: i32, high: i32) -> Vec<i32> { let mut res = Vec::new(); for i in 1..=9 { for l in i+1..=9 { let mut now = 0; for cur in i..=l { now = now * 10 + cur; } if now >= low && now <= high { res.push(now); } } } res.sort(); res } }一个更函数式的写法impl Solution { pub fn sequential_digits(low: i32, high: i32) -> Vec<i32> { let mut res: Vec<_> = (1..=9) .flat_map(|i| (i+1..=9).map(move |l| (i, l))) .filter_map(|(i, l)| { let now = (i..=l).fold(0, |now, cur| now * 10 + cur); if now >= low && now <= high { Some(now) } else { None } }) .collect(); res.sort(); res } }LC2966. Divide Array Into Arrays With Max Difference Med额,感觉排个序贪心就行了,看看能不能锻炼下函数式编程技巧impl Solution { pub fn divide_array(mut nums: Vec<i32>, k: i32) -> Vec<Vec<i32>> { nums.sort(); let res: Vec<Vec<i32>> = nums.chunks(3).map(|chunk| chunk.to_vec()).collect(); if res.iter().any(|sub_vec| sub_vec.len() == 3 && sub_vec[2] - sub_vec[0] > k) { vec![] } else {res} } }LC647. Palindromic Substrings Med找到所有的回文子串,感觉比较常规的题数据范围是 1000 。考虑枚举子串+哈希,预处理正反串哈希,枚举之后看相同区间的正反串哈希是否一样即可。应该是肯定能做,但是题目标签是 DP,想想能不能用 DP 做。如果是 DP,肯定是从短到长,第一维枚举长度,第二维枚举起点,这样已经 n^2了,转移得考虑 O1 的考虑 dpi 为 起点为 i,终点为 j 的串是否为回文,转移似乎应该是dpi+1 == 1 && s[i] == s[j]考虑偶数的情况,初始值dpi = 1 if s[i] == s[i+1]应该没啥不对的,两种方法都写下。状态:dpi 表示从 i 到 j 的子串是否为回文串边界条件:dpi = 1, dpi = 1 if s[i] == s[i+1]答案:s[i..j] s.t. dpi == 1转移:dpi = dpi+1 == 1 && s[i] == s[j]impl Solution { pub fn count_substrings(s: String) -> i32 { let n = s.len(); let s = s.into_bytes(); let mut dp = vec![vec![false;n];n]; for i in 0..n { dp[i][i] = true; if i < n-1 && s[i] == s[i+1] { dp[i][i+1] = true; } } for len in (3..=n) { for l in (0..n-len+1) { dp[l][l+len-1] |= dp[l+1][l+len-2] && s[l] == s[l+len-1]; } } dp.iter() .flat_map(|row| row.iter()) .filter(|&&value| value) .count() as i32 // let mut res = 0; // for (i, arr1) in dp.iter().enumerate() { // for (j, cur) in arr1.iter().enumerate() { // if *cur { // res += 1; // } // } // } // res } }
2024年01月19日
64 阅读
0 评论
0 点赞
2024-01-12
Rust入门练习-Week3-LC368/279/1584/451/332
LC368. Largest Divisible Subset Med返回一个最长子序列,保证 a[i]和a[j] 是可整除的。感觉像一个 dp,要先排个序dp[i] 代表以 i 为结尾的最长子序列长度初始状态 dp[i] = 1转移 dp[i] = max(dp[j] + 1, dp[i]) (a[i] % a[j] == 0)同时记录从哪转移的,最后输出impl Solution { pub fn largest_divisible_subset(mut nums: Vec<i32>) -> Vec<i32> { let len = nums.len(); if len == 1 { return nums; } nums.sort(); let mut dp = vec![(None, 1); len]; let mut mxn = 1; for i in 1..len { for j in 0..i { if nums[i] % nums[j] == 0 && dp[i].1 < dp[j].1 + 1 { dp[i] = (Some(j), dp[j].1 + 1); if dp[i].1 > dp[mxn].1 { mxn = i; } } } } println!("dp : {:?}, mxn : {}", dp, mxn); let mut res = Vec::new(); res.push(nums[mxn]); while let Some(i) = dp[mxn].0 { res.push(nums[i]); mxn = i; } res } }LC279. Perfect Squares Med给定一个数,找到它的完全平方数分拆中数字最少的,n 范围 10^4这个范围内一共就一百个完全平方数,最多 10^4 层(全 1),感觉怎么都能做。直接宽搜按层肯定是能做出来。然后发现只要层数不要方案,直接背包吧。impl Solution { pub fn num_squares(n: i32) -> i32 { let n = n as usize; let square_numbers = || (1..=100).map(|x| x * x); let mut dp = vec![0x3f3f3f3f; n as usize + 1]; dp[0] = 0; for i in 1..=n { dp[i] = square_numbers() .filter(|&j| j <= i) .map(|j| dp[i-j] + 1) .min() .unwrap_or(0x3f3f3f3f); } dp[n] } }这里算是把 lambda 和链式用爽了,我来一行一行解释一下 10-14 行首先说意义,背包嘛,我们的转移方程 dp[i] = min(dp[i-w[j]] + 1), 其中 w[j] 是第 j 个完全平方数square_numbers 是一个闭包,1..=100 是一个 Range,也实现了 Iterator,因此可以使用 map,我们没有对这个 map 迭代器进行 collect,而是作为闭包函数在未来的时候使用square_numbers()返回了一个迭代器,然后下一行,filter 通过传入的闭包,把刚刚返回的迭代器的每个值填充进作为它参数的闭包|&j| j <= i 返回一个迭代器,留下所有符合 j<i的值,再调用 map 函数,把刚刚迭代器里所有的 j 变为 dp[i-j] + 1,再取这个迭代器里的最小值。评价是迭代器和闭包真神奇,但是实际应用感觉会降低代码可读性上面的代码用了 32ms,不是很优秀,感觉是每次都生成一个迭代器比较慢?尝试把 square_numbers collect 下,每次 iter(),好吧,更慢了。LC1584. Min Cost to Connect All Points Med裸 Kruscal,当练练并查集Rust 咋写了struct Edge { u: usize, v:usize, w: i32 } struct UnionFind { fa: Vec<usize>, } impl UnionFind { pub fn new(n: usize) -> Self { UnionFind { fa: (0..n).collect(), } } pub fn find(&mut self, x: usize) -> usize { if self.fa[x] != x { self.fa[x] = self.find(self.fa[x]); } self.fa[x] } pub fn union(&mut self, x: usize, y: usize) -> bool { let (dx, dy) = (self.find(x), self.find(y)); if dx != dy { self.fa[dx] = dy; return true; } return false; } } impl Solution { pub fn min_cost_connect_points(points: Vec<Vec<i32>>) -> i32 { let mut dist: Vec<Edge> = points.iter().enumerate() .flat_map(|(i, p1)| { points[i+1..].iter().enumerate().map(move |(j, p2)| { let (dx, dy) = (p1[0] - p2[0], p1[1] - p2[1]); let dis = dx.abs() + dy.abs(); Edge { u: i, v: i+j+1, w: dis} }) }).collect(); dist.sort_by_key(|a| a.w); let mut dsu = UnionFind::new(points.len()); let mut res = 0; for e in dist { if dsu.union(e.u, e.v) { res += e.w; } } res } }LC451. Sort Characters By Frequency Med比较简单,不想优雅的方法,直接给出一个暴力先 HashMap 统计每个字母出现的频率,扫 26+26+10 遍频率,每次记录一下哪个最多,然后删掉对应频率,在结果后面加上频率*字符,一直到频率都为 0,返回想想怎么优雅点。可以先统计字符出现次数,再按此为 key 调用 sortimpl Solution { pub fn frequency_sort(s: String) -> String { let mut counts = vec![(0, 0); 75]; s.chars().for_each(|c| { counts[c as usize - '0' as usize].0 = c as u8; counts[c as usize - '0' as usize].1 += 1; }); counts.sort_by(|a, b| (b.1).cmp(&a.1)); let mut res = Vec::new(); for pair in &counts { res.extend(vec![pair.0; pair.1 as usize]); } String::from_utf8(res).unwrap() } }LC332. Reconstruct Itinerary Hard还没用 Rust 写过图题,不过问题不大,不用前向星用 Vec 存边就好了,一个裸的求欧拉路问题,算法我已经差不多忘了,就记得是 DFS 。看看能不能自己想出来。欧拉路的起点终点都是确定的,而且起点已经给定了,且保证存在这样的路径,在这种前提下,是只要保证起终点对,随便走都能走到吗?我想是的,除了起点度数为 1,终点度数为-1,其他节点度数都为 0,也就是只要我走进来,我就一定有一条路能走出去。这样看我们只要正确识别到终点,就能找到这样的路径了,而终点识别并不困难。考虑怎么找到题目要求的最小字典序路径如果每次都贪心的走一个最小的,显然是不行的,极端情况就是 A->B, A->C, C->A,一次就死了,没走到所有的路径。所以应该要先走遍所有的环,如果当前节点没环了,再往下走一步。什么情况下没环?如果当前节点有两个出度,那就一定还有环。所以当“往下走一步”的时候,这个点的使命已经结束了,可以被加到路径里了。这样可以保证终点是最后被加的。怎么保证这种有环先走呢。除非我们标记出所有的环,Tarjan?应该没这么麻烦。应该就是朴素的 DFS。考虑访问的时候我们并不能识别出来,程序会先进到这个点,走环,再走到终点的路,再走一些环,最后出DFS 的栈,它出栈的时候它的所有路都被访问过了。这样把它放到队列里。在它被放到队列里时,它到终点路径上的那些点一定已经在队列里了,因为它们在它之后被 dfs,在它之前出栈。这个队列最后就应该是结果那怎么保证字典序呢。好像贪心的先走字典序小的就可以了。
2024年01月12日
82 阅读
0 评论
0 点赞
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日
50 阅读
0 评论
0 点赞
1
...
4
5
6
...
10