< 返回版块

lithbitren 发表于 2020-05-13 15:07

Tags:leetcode,语法

java、python、golang在实现需求的时候几乎没碰到过语法问题,原理清晰的情况下大概率一次bug free,唯有rust,劝退好几次了,实在不甘心。 今天leetcode的签到题是二叉树的层次遍历,即把二叉树的值按层次组成值数组来输出。 题目和我解法地址:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/comments/394128/

python的字典解法是我发明的和层次遍历是我常用的,盲打都可以打出来,rust的迭代器功能理论上应该是很完备的,编译了一百次都没写成功,太菜了,气死我了。 下面是我py的层次遍历写法。

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans, d = [], [root] if root else []
        while d:
            ans.append([t.val for t in d])
            d = [r for t in d for r in (t.left, t.right) if r]
        return ans

py的数组迭代用的是列表解析,写成函数形式也是很简单的,大概就是

d = list(filter(bool, itertools.chain(*map(lambda t: (t.left, t.right), d))))

rust我也ac了,但咋才能写成py这种形式呢,ans我写进一行了,问题不大,d迭代就苦手了。

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut d = match root {
            Some(r) => vec![r],
            None => vec![]
        };
        let mut ans = vec![];
        while !d.is_empty() {
            ans.push(d.iter().map(|r| r.borrow().val).collect());
            let mut q = vec![];
            for r in d {
                if let Some(left) = r.borrow().left.clone() {
                    q.push(left);
                }
                if let Some(right) = r.borrow().right.clone() {
                    q.push(right);
                }
            }
            d = q;
        }
        ans
    }
}

就是把d的重赋值写进一行,我filter、flatten、borrow、clone、concat、collect整了半天都编译通过不了,无法在图灵完备的语言里随心所欲真是太崩溃辣,求大佬指点。

还有,rust的向量遍历的时候,标准写法一般都是iter。

for r in d.iter() {}

也见过&这么写的,不过这样写在我这代码里面编译不通过,报错甚至没有指向这里。

for r in &d {}

我一开始把py的习惯带进去了,啥都没带。

for r in d {}

网上几乎没见过rust这么写的,但也编译通过了,实在不懂啥情况。

评论区

写评论
作者 lithbitren 2020-05-13 23:41

谢谢大佬耐心解答,学到啦 对以下内容的回复:

xjkdev 2020-05-13 22:32

当然。d.flatten()相当于d.filter(Option::is_some).map(|r| r.unwrap())

对以下内容的回复:

作者 lithbitren 2020-05-13 21:20

大佬,不好意思打扰了,继续追问一下,flatten在扁平化的过程中是否把空子树自动过滤掉了,我在py上是用filter或if来过滤,rust不用过滤所以有点疑惑。 对以下内容的回复:

作者 lithbitren 2020-05-13 17:15

对对就这个!flatten要写两次昂,又学到了,d的初始化也学到了,射射大佬! 对以下内容的回复:

xjkdev 2020-05-13 16:40
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut d :Vec<Rc<RefCell<TreeNode>>> = root.into_iter().collect();
        let mut ans = vec![];
        
        while !d.is_empty() {
            ans.push(d.iter().map(|r| r.borrow().val).collect());
            d = d.iter().map(|r| vec![r.borrow().left.clone(),  r.borrow().right.clone()]) // 得到Vec<Vec<Option<Rc<...>>,Option<Rc<...>>>>
                        .flatten()  // 将vec![left,right]这层扁平化,得到Vec<Option<Rc<...>>>
                        .flatten()  // 将Option<Rc<...>>这层扁平化,得到Vec<Rc<...>>
                        .collect();
        }
        ans
    }
}

是这个意思吗? PS. Rust有个技巧,option可以转换为迭代器,所以可以into_iter().collect(),也可以在容器里flatten

1 共 5 条评论, 1 页