美文网首页
两数相加 - Rust

两数相加 - Rust

作者: 曾大稳丶 | 来源:发表于2022-07-19 11:57 被阅读0次
image.png
image.png
题目解析
因为是逆序,可以正常的每一个位置对应相加,如果位数不一致,那么缺少的那一个位值为0即可,对应的进位数往前加。
rust 采用 Rust Pattern Matching 写法可以更直观。
https://leetcode.cn/problems/add-two-numbers/solution/rust-pattern-matching-xie-fa-by-anonyuse-kk10/
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}
/// https://leetcode.cn/problems/add-two-numbers/
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut result = None;
    let mut tail = &mut result;
    let mut t = (l1, l2, 0, 0); //(list1, list2, value, carry)
    loop {
        t = match t {
            // 到尾部,退出
            (None,None,_,0) => break, 
             // 如果两个都到底,但是相加还有余
            (None,None,_,carry) => (None,None, carry,0),
            // 如果某一个到底,并且和余数相加大于等于10
            (Some(list), None, _, carry) | (None,Some(list), _, carry) if list.val + carry>=10 => {
                (list.next, None, list.val + carry - 10, 1)
            }, 
            // 如果某一个到底,并且和余数相加小于10
            (Some(list), None, _, carry) | (None,Some(list), _, carry) => {
                (list.next, None, list.val + carry, 0)
            }, 
            // 如果两个都没到底,并且和余数相加大于等于10
            (Some(l1), Some(l2), _, carry) if l1.val + l2.val + carry >=10 => {
                (l1.next, l2.next, l1.val + l2.val + carry - 10 , 1)
            }, 
            // 如果两个都没到底,并且和余数相加小于10
            (Some(l1), Some(l2), _, carry) => {
                (l1.next, l2.next, l1.val + l2.val + carry, 0)
            }, 
        };
        // 赋值
        *tail = Some(Box::new(ListNode::new(t.2)));
        // 获取下一个节点的引用
        tail = &mut tail.as_mut().unwrap().next;
    }
    result
}

采用递归:

impl Solution {
    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        carried(l1,l2,0)
    }
}

pub fn carried(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>, mut carry: i32) -> Option<Box<ListNode>> {
    if l1.is_none() && l2.is_none() && carry == 0{
        None
    }else {
        Some(Box::new(ListNode{
            next: carried(
              l1.and_then(|x| {
                carry+=x.val; 
                x.next
              }),  
              l2.and_then(|x| {
                carry+=x.val; 
                x.next
              }), 
              carry / 10
            ),
            val: carry % 10
        }))
    }
}

复杂度分析
时间复杂度:O(max(m,n)),其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置,而处理每个位置只需要 O(1)的时间。
空间复杂度:O(1)。

相关文章

  • 两数相加 - Rust

    因为是逆序,可以正常的每一个位置对应相加,如果位数不一致,那么缺少的那一个位值为0即可,对应的进位数往前加。 ru...

  • LeetCode 两数相加 Rust

    LeetCode 两数相加 Rust 题目 给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 ...

  • 两数相加

    题目 You are given two non-empty linked lists representing ...

  • 两数相加

    给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表...

  • 两数相加

    两数相加 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一...

  • 两数相加

    两数相加: 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回...

  • 两数相加

    题目 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新...

  • 两数相加

    题目描述: 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回...

  • 两数相加

    给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表...

  • 两数相加

    问题链接:https://leetcode-cn.com/explore/interview/card/top-i...

网友评论

      本文标题:两数相加 - Rust

      本文链接:https://www.haomeiwen.com/subject/ykbjirtx.html