..

通过算法学习rust之链表中倒数第K个节点

题目地址

// Definition for singly-linked list.
// #[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
//     }
//   }
// }
impl Solution {
    pub fn get_kth_from_end(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {

    }
}

知识点列举

  • as_ref()方法
  • is_some()方法
  • cloned()方法

解题思路

双指针通过设置两个指针的间距，和给定的k相同，当前面的指针到达底部时，后面的指针所拥有的节点就是题目中所要找到的节点

impl Solution {
  pub fn get_kth_from_end(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
    let mut start = head.as_ref();
    for i in 0..k {
      match start.take() {
        Some(node) => start = node.next.as_ref(),
        None => {
          return None;
        }
      }
    }
    let mut end = head.as_ref();
    while let Some(node) = start.take() {
      start = node.next.as_ref();
      end = end.unwrap().next.as_ref();
    }
    end.cloned()
  }
}

as_ref() 是什么 为什么需要使用as_ref()

一开始start和end两个可变变量并没有使用head.as_ref()来设置变量指向的节点值，而是使用clone()方法。

clone()方法拷贝了两个相同的head链表，第一次提交时发现内存占比较高只超过16%的用户.

执行用时：0 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗：2.2 MB, 在所有 Rust 提交中击败了16.67%的用户

通过查询题解发现，大部分人使用的是as_ref()方法,当我讲clone()替换为as_ref()时，数据如下所示，看起来还是非常可观的。

执行用时：0 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗：1.9 MB, 在所有 Rust 提交中击败了93.33%的用户

as_ref()是转引用函数，将具有所有权对象转换成引用对象，在不改变被转换对象的基础上产生一个引用对象。 目前有：Option, Box，Result这三种类型默认提供支持as_ref

Brrow允许owner把自已的拥用权“借出”，borrow实际上创建了到原始资源的reference.

Borrow可以直接在int, &str, String, vec, [], struct, enum 类型上直接指定&来引用。

as_ref()则不行，它需要声明泛型 T：AsRef<int>, T: AsRef<str>, T:AsRef<struct name> 来支持。

实现AsRef trait1

由于String和&str都实现了AsRef<str>，所有我们可以接受String和&str作为参数,可以调用as_ref()方法转化为&str

fn is_hello<T: AsRef<str>>(s: T) {
  assert_eq!("hello", s.as_ref());
}

fn main() {
  // s1是&str类型, str类型实现了AsRef<str>，&str也实现了AsRef<str>
  let s1 = "hello";
  is_hello(s1);
  // s2是String类型, 实现了AsRef<str>, &String也实现了AsRef<str>
  let s2 = "hello".to_string();
  is_hello(s2);
}

上面is_hello方法的泛型定义是trait bound语法，因为例子场景比较直观，也可以使用trait bound的语法糖

fn is_hello(s: impl AsRef<str>) {
  assert_eq!("hello", s.as_ref());
}

为未实现的类型实现AsRef<T>，因为AsRef<T>是trait我们要实现其中定义的方法AsRef<T> trait 定义如下：

pub trait AsRef<T>
where
    T: ?Sized,
{
    fn as_ref(&self) -> &T;
}

enum Msg {
  Hello,
  World,
}

impl AsRef<str> for Msg {
  fn as_ref(&self) -> &str {
    match self {
      Msg::Hello => "hello",
      Msg::World => "world",
    }
  }
}

fn main() {
  let msg = Msg::Hello;
  assert_eq!("hello", msg.as_ref());
}

is_some() 是什么

如果想知道一个Option是否含有值，但不会使用到值的时候，可以用is_some()来进行判断is_some() 返回的是Boolean

let has_item = if let Some(_value) = option { true } else { false };
// becomes
let has_item = option.is_some();

下面这段描述了什么场景下可以使用is_some()以及如何使用，下面的使用场景比较单一因为场景只针对于本题不做额外的扩展

下面使用is_some()也不是最优场景，只是介绍这里可以使用is_some()；

impl Solution {
  pub fn get_kth_from_end(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
    ...
    while let Some(node) = start.take() {
      ...
      // 修改前
      end = end.unwrap().next.as_ref();
      // 修改后
      if end.is_some() {
        end = end.next.as_ref();
      }
    }
    ...
  }
}

cloned()

pub fn cloned(self) -> Option<T>
where
    T: Clone,

通过clone Option 中的内容将Option<&T>映射到Option<T>

let x = 12;
let opt_x = Some(&x);
assert_eq!(opt_x, Some(&12)); //ok
let cloned = opt_x.cloned();
assert_eq!(cloned, Some(12)); //ok

下面是Rust源码中Option cloned的实现，可以看到cloned内部是帮开发人员处理Some和None的情况，其中Some中调用了clone()方法

impl<T> Option<&mut T> {
  #[must_use = "`self` will be dropped if the result is not used"]
  #[stable(feature = "rust1", since = "1.0.0")]
  #[rustc_const_unstable(feature = "const_option_cloned", issue = "91582")]
  pub const fn cloned(self) -> Option<T>
  where
    T: ~const Clone,
  {
    match self {
      Some(t) => Some(t.clone()),
      None => None,
    }
  }
}

clone()方法是Rust内置traitClone中的方法,derive 属性会在使用 derive 语法标记的类型上生成对应 trait 的默认实现的代码。在上面结构体中已经添加了Clone

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

clone()方法大概如下所示:

pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}
impl<T> Clone for ListNode {
  fn clone(&self) -> Self {
    *self
  }
}

到此处我们应该可以理解cloned()到底做什么事情，怎么做的，在哪里用。探究的过程也让我加深了对Rust内置trait的理解，学会如何查询Rust内置trait的实现。

总结

as_ref()、is_some()、cloned() 属于基础方法，在Rust中使用频率非常高，希望这篇文章可以加深对Rust基础方法的理解，在世纪开发过程中能运用自如。

参考链接

  1. rust语言基础学习: 使用AsRef和AsMut trait实现不同引用之间的转换
Tags: [ rust  ]