ARTICLE DETAIL

资讯详情

深耕郑州网站建设与运营推广的一线实战洞察。

元宝 LeetCode 134. 加油站 Rust实现

元宝    LeetCode 134. 加油站 Rust实现 Rust 实现贪心O(n) / O(1)和 Python 版逻辑完全一致用 Rust 切片写法符合 LeetCode Rust 模板。impl Solution {pub fn can_complete_circuit(gas: Vec, cost: Vec) - i32 {let n gas.len();let mut total 0i32; // 全局油差累计let mut cur 0i32; // 从候选起点出发的累计油差let mut start 0usize; // 候选起点下标for i in 0..n { let diff gas[i] - cost[i]; total diff; cur diff; // 到不了当前站 i起点后移到 i1 if cur 0 { start i 1; cur 0; } } // 总油量够才返回起点否则 -1 if total 0 { (start % n) as i32 } else { -1 } }}LeetCode 提交说明函数签名固定为“pub fn can_complete_circuit(gas: Vec, cost: Vec) - i32”返回值是“i32”所以“usize” 的“start” 最后转成“i32” 即可“start % n” 是为了防止“start n”循环结束时刚好越界到末尾后一位的情况实际“total0” 时“start” 不会超过“n”写上也安全更“Rust 风格”的迭代器写法可选如果想秀一下迭代器也可以这样写逻辑等价可读性看团队习惯impl Solution {pub fn can_complete_circuit(gas: Vec, cost: Vec) - i32 {let total: i32 gas.iter().zip(cost.iter()).map(|(g, c)| g - c).sum();if total 0 {return -1;}let mut cur 0; let mut start 0; for i in 0..gas.len() { cur gas[i] - cost[i]; if cur 0 { start i 1; cur 0; } } (start % gas.len()) as i32 }}⚠️ 上面这个版本先算“total”提前返回“-1”后面不用再判一次分支更清晰。复杂度维度 值时间 O(n) 单次遍历或两次若先算 total空间 O(1) 无额外分配和 Python 版对照记忆Python Rust“total diff”“total gas[i]-cost[i]”“start i 1”“start i 1”usize“return start if total0 else -1”“(start%n) as i32” /“-1”需要我再补一个带单元测试“#[test]” 的 cargo 工程版或者对比下 Rust vs Python 在边界用例如 n1的行为吗
返回列表