Steven's Blog

Appearance

On this page

每天一道Rust-LeetCode(2019-01-01) ​

坚持每天一道题,刷题学习Rust.

题目描述 ​

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorder-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

因为是单向链表,所以先以收集后半部分的节点, 然后进行插入操作

解题过程 ​

rust
struct Solution {}
impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let mut stack = Vec::new();
        let mut total = 0;
        for i in 0..height.len() {
            //要把0也放进去,把0放进去,简化了很多问题
            while stack.len() > 0 && height[*stack.last().unwrap()] < height[i] {
                let pop_top = stack.pop().unwrap();
                if stack.is_empty() {
                    break;
                }
                let top = *stack.last().unwrap();
                let distance = i - top - 1;
                let height = min(height[i], height[top]) - height[pop_top];
                total += height * distance as i32
            }
            //            println!("push {}={}", i, height[i]);
            stack.push(i);
        }
        total
    }
}
#[cfg(test)]
mod test {
    use super::*;
    use crate::share::*;
    #[test]
    fn test() {
        let t = Solution::trap(vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]);
        assert_eq!(t, 6);
        let t = Solution::trap(vec![4, 2, 3]);
        assert_eq!(t, 1);
        let t = Solution::trap(vec![5, 2, 1, 2, 1, 5]);
        assert_eq!(t, 14);
    }
}

一点感悟 ​

如果不过滤0,那么碰到这种请0 1 2,这种情况,2进来的时候,很自然能够算出左侧0能够承载的雨水量就是0

其他 ​

欢迎关注我的github,本项目文章所有代码都可以找到.