Rust算法练习-LC2092/997/787/980/2646 LC2646. Minimize the Total Price of the Trips Hard袜，这题还是挺有挑战的。给定一棵树，每个点有权值，给定M组点对 (ai, bi)，求Sum(dis[ai, bi])。如果只到这，好像还没啥，树剖LCA就能解决，别说N=50了，N=10^5也行但是多了个条件，可以把一些不相邻的点的权值减半，让我们求最小的结果我目测得把路径离线，先统计出来每个点要走多少次。树可以染色吗，所有点一定是可以分成两组的么，如果是，那就简单了，无非是选组1或者组2，但是显然不是（考虑链：1-2-3-4，我可以染1和4）考虑树形dp，一个节点能染色要求它的子节点都没有染色，那好像就好做了，我们预先确定一个根rootdpi表示到节点i，节点有半价/无半价的最小值dpfa = Sum(min(dp[son])) + price[fa] * freq[fa]dpfa = Sum(dpson) + price[fa]/2 * freq[fa]边界是叶子节点，直接处理自己的值就行，考虑这样是不是能覆盖所有状态。不相邻的话应该是恰好覆盖0ms，一遍过，讲真，现在一遍过的概率高很多，我还是蛮高兴的，证明自己下手越来越有准头了。impl Solution { pub fn minimum_total_price( n: i32, edges: Vec<Vec<i32>>, price: Vec<i32>, trips: Vec<Vec<i32>>, ) -> i32 { let n = n as usize; let mut fa = vec![0; n]; let mut freq: Vec<i32> = vec![0; n]; let mut dep: Vec<i32> = vec![0; n]; let edges: Vec<Vec<i32>> = edges.iter().fold(vec![vec![]; n], |mut acc, e| { acc[e[0] as usize].push(e[1]); acc[e[1] as usize].push(e[0]); acc }); let mut dp: Vec<Vec<i32>> = vec![vec![0; 2]; n]; let root = 0; dfs(root, &mut fa, &mut dep, &edges); for trip in trips.iter() { let mut x = trip[0] as usize; let mut y = trip[1] as usize; while x != y { if dep[x] < dep[y] { std::mem::swap(&mut x, &mut y); } freq[x] += 1; x = fa[x] as usize; } freq[x] += 1; } dfs2(root, &edges, &freq, &mut dp, -1, &price); dp[root as usize][0].min(dp[root as usize][1]) } } fn dfs(p: i32, fa: &mut Vec<i32>, dep: &mut Vec<i32>, edges: &Vec<Vec<i32>>) { for &to in edges[p as usize].iter() { if to == fa[p as usize] { continue; } fa[to as usize] = p; dep[to as usize] = dep[p as usize] + 1; dfs(to, fa, dep, edges); } } fn dfs2( p: i32, edges: &Vec<Vec<i32>>, freq: &Vec<i32>, dp: &mut Vec<Vec<i32>>, fa: i32, price: &Vec<i32>, ) { let mut res0 = 0; let mut res1 = 0; for &to in edges[p as usize].iter() { if to == fa { continue; } dfs2(to, edges, freq, dp, p, price); res0 += dp[to as usize][0]; res1 += std::cmp::min(dp[to as usize][0], dp[to as usize][1]); } dp[p as usize][0] = res1 + freq[p as usize] * price[p as usize]; dp[p as usize][1] = res0 + freq[p as usize] * (price[p as usize] >> 1); }LC62. Unique Paths/63. Unique Paths II/980. Unique Paths III Med Med Hard62是从左上走到右下的不重复路径数，63是带障碍的，980是从起点到终点，且走过全部空格子的路径数，难度陡增啊62、63都是比较简单的dp，dpi表示走到(i, j)的方案数，dp[unreachable] = -1, ans = dpm, dpi = dpi-1 + dpi; 常规到我不打算贴代码了，主要关注980数据范围 20*20, 这个能直接搜么，搜的复杂度是多少？最讨厌算搜索的复杂度了。不过看上去400个格子，4^400肯定不可做的。但是应该也不是dp，状态太多了，也压不了。我还是倾向于搜索+剪枝，先搜一发试试有个小插曲：你觉得这好看么，我望着这排迭代器沉思了几秒，决定还是乖乖遍历impl Solution { pub fn unique_paths_iii(grid: Vec<Vec<i32>>) -> i32 { let target = grid .iter() .map(|row| row.iter().filter(|&&x| x == 0).count()) .sum::<usize>(); let (x, y) = grid .iter() .enumerate() .flat_map(|(i, row)| { row.iter() .enumerate() .find(|&(_, &x)| x == 1) .map(|(j, _)| (i, j)) }) .next() .unwrap(); } }没想到0ms是真的。。impl Solution { fn dfs(grid: &mut Vec<Vec<i32>>, x: usize, y: usize, now_step: i32, target_step: i32) -> i32 { if grid[x][y] == 2 { return match now_step == target_step { true => 1, false => 0, }; } let mut res = 0; grid[x][y] = -1; let dx = [0, 0, 1, -1]; let dy = [1, -1, 0, 0]; for i in 0..4 { let nx = x as i32 + dx[i]; let ny = y as i32 + dy[i]; if nx >= 0 && nx < grid.len() as i32 && ny >= 0 && ny < grid[0].len() as i32 { let nx = nx as usize; let ny = ny as usize; if grid[nx][ny] == 0 || grid[nx][ny] == 2 { res += Self::dfs(grid, nx, ny, now_step + 1, target_step); } } } grid[x][y] = 0; res } pub fn unique_paths_iii(mut grid: Vec<Vec<i32>>) -> i32 { let mut target_steps = 1; let (mut sx, mut sy) = (0, 0); for i in 0..grid.len() { for j in 0..grid[0].len() { if grid[i][j] == 0 { target_steps += 1; } else if grid[i][j] == 1 { sx = i; sy = j; } } } Self::dfs(&mut grid, sx, sy, 0, target_steps) } }LC787. Cheapest Flights Within K Stops Med求两点之间最短路，但是有个限制，最多走K条边，感觉挺难的，一看N范围100。EMM是不是BFS K层就可以了。这个复杂度是啥样的，应该就是KM能搞，好像也能用类似Dij的思路堆优化，但是优化起来考虑的更多。先写个BFS试试，就是贝尔曼福德吧impl Solution { pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 { let mut dis = vec![0x3f3f3f3f; n as usize]; dis[src as usize] = 0; let mut now_dis = Vec::with_capacity(n as usize); for _ in 0..=k { now_dis.clear(); now_dis = dis.clone(); for flight in &flights { let u = flight[0] as usize; let v = flight[1] as usize; let w = flight[2]; if now_dis[u] != 0x3f3f3f3f { now_dis[v] = now_dis[v].min(dis[u] + w); } } std::mem::swap(&mut dis, &mut now_dis); } match dis[dst as usize] { 0x3f3f3f3f => -1, _ => dis[dst as usize], } } }LC997. Find the Town Judge Ez找到一个入度n-1，没有出度的点，都懒得开IDE本期每日一题将在今天开始变成每日一题+一道Hard我发现每日一题总刷Ez，一点用没有，Ez等级能用到的语法我基本上已经熟悉了。并将会在近期开rust kernel的impl Solution { pub fn find_judge(n: i32, trust: Vec<Vec<i32>>) -> i32 { let n = n as usize; let (mut ind, mut oud) = (vec![0;n+1], vec![0;n+1]); trust.iter().for_each(|t| { oud[t[0] as usize] += 1; ind[t[1] as usize] += 1; }); (1..=n as i32).find(|&x| oud[x as usize] == 0 && ind[x as usize] == n-1).unwrap_or(-1) } }LC2092. Find All People With Secret Hard10^5个人，10^5的时间，最多10^5的会，N^2是没戏了，应该是哪一维要log这东西要我想的话肯定是一个并查集，按时间就把人塞到并查集里了。哎好像能直接做奥，主要就是同一时间的传播怎么处理这个问题。先不考虑同时开会传播的问题。把会议按时间排个序。对每对x、y，看看是不是有一边持有Secret，如果是，把没有那边并进firstPerson这个集合里。好像考虑的话也没问题。。对同一时间的遍历两遍就行了。既然不能只遍历两遍，考虑这块怎么优化。一个比较显然的优化是，如果能把当前时间的人也划分联通块，就不会是链式传播了。但是这样要写一个离散化并查集，好麻烦。。。（不然初始化是N的，如果离散化，应该是均摊N）但是我考虑一个暴力，在sys里也常用。我不扫两遍，我扫到没有更新为止。这样复杂度肯定是不对的，但是没准能骗struct Union { parent: Vec<i32>, } impl Union { fn new(n: usize) -> Self { Union { parent: (0..n as i32).collect(), } } fn find(&mut self, x: i32) -> i32 { if self.parent[x as usize] != x { self.parent[x as usize] = self.find(self.parent[x as usize]); } self.parent[x as usize] } fn union(&mut self, x: i32, y: i32) { // println!("merge {} {}", x, y); let x = self.find(x); let y = self.find(y); if x != y { self.parent[x as usize] = y; } } } impl Solution { pub fn find_all_people(n: i32, mut meetings: Vec<Vec<i32>>, first_person: i32) -> Vec<i32> { let mut union = Union::new(n as usize); union.union(0, first_person); let mut meetings_by_time = vec![vec![]; 100001]; for i in 0..meetings.len() { let m = &meetings[i]; meetings_by_time[m[2] as usize].push((m[0], m[1])); } // println!("{:?} {:?} {:?}", meetings_by_time[5], meetings_by_time[8], meetings_by_time[10] ); for i in 0..meetings_by_time.len() { let mut changed = true; while changed { changed = false; for j in 0..meetings_by_time[i].len() { let m = meetings_by_time[i][j]; let root = union.find(first_person); let (dx, dy) = (union.find(m.0), union.find(m.1)); if dx == dy || (dx != root && dy != root) { continue; } union.union(m.0, m.1); changed = true; } } } let mut ans = vec![]; let root = union.find(first_person); for i in 0..n { if union.find(i) == root { ans.push(i); } } ans } }

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 } }

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 } }

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 } }

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() } }