< 返回版块

lithbitren 发表于 2020-06-25 13:18

Tags:leetcode,语法,字符串,生命周期

大致就是给出行程,规划路径,然后按字典序输出。 https://leetcode-cn.com/problems/reconstruct-itinerary/solution/332-zhong-xin-an-pai-xing-cheng-shen-sou-hui-su-by/ 这个之前写过这题的题解,python的主要代码如下

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        d = collections.defaultdict(list)   #邻接表
        for f, t in tickets:
            d[f] += [t]             #路径存进邻接表
        for f in d:
            d[f].sort(reverse=True) #逆序排序
        ans = []
        def dfs(f):
            while d[f]:
                dfs(d[f].pop())     #路径检索
            ans.append(f)           #回溯输出
        dfs('JFK')
        return ans[:: -1]           
        #逆序排序,所以再次逆序输出,考虑这种逆序方法是尽可能避免了list头部增减这种O(N)级别的操作

翻译成rust卡在字符处理上,递归直接用string递归会报生命周期问题,不过可能也不是生命周期问题,反正加了标记也会报其他错,HashMap的存储不知道用string还是str,还是存引用,国际版leetcode的这题只有一个rust评论,代码巨长看都看不下去,实在不知道咋继续下手了。。

use std::collections::HashMap;
impl Solution {
    pub fn find_itinerary(tickets: Vec<Vec<String>>) -> Vec<String> {
        let mut d: HashMap<_, Vec<_>> = HashMap::new();
        for t in &tickets {
            d.entry(&t[0]).or_default().push(&t[1]);
        }
        for (_, f) in d.iter_mut() {
            f.sort_by(|a, b| b.cmp(a));
        }
        let mut ans = vec![];
        /* 深搜递归这里应该怎么改呢?
        fn dfs(f: String, d: ..., ans: &mut Vec<String>) {
            ...
        }
        dfs("JFK".to_string(), &mut d, &mut ans);
        */
        ans.reverse();
        ans
    }
}

向大佬们求助

评论区

写评论
Neutron3529 2020-06-26 11:44

等有空我再刷一遍Option<Rc<RefCell<T>>>的题目

总感觉take是个好函数

--
👇
lithbitren: 今天的每日一题rust版我要坑了,写了一个多小时都写不出来,二叉树那种rc/refcell已经可以无障碍刷题了,链表的box处理还是整不明白。。

--

Neutron3529 2020-06-26 11:27

学会了。

关键是take

(然而新程序再也刷不出0ms了……)

impl Solution {
    pub fn remove_duplicate_nodes(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        if let Some(mut head)=head{
            //let mut a=std::collections::HashSet::with_capacity(20000);
            let mut w=[0;20001];
            let mut curr=&mut head;
            //a.insert(curr.val);
            w[curr.val as usize]=1;
            while let Some(nxt)=&curr.next{
                //if a.insert(nxt.val){
                if w[nxt.val as usize]==0{
                    w[nxt.val as usize]=1;
                    curr=curr.next.as_mut().unwrap();
                }else{
                    curr.next=curr.next.take().unwrap().next
                }
            }
            Some(head)
        }else{None}
    }
}

--
👇
lithbitren: 今天的每日一题rust版我要坑了,写了一个多小时都写不出来,二叉树那种rc/refcell已经可以无障碍刷题了,链表的box处理还是整不明白。。

--

作者 lithbitren 2020-06-26 10:12

今天的每日一题rust版我要坑了,写了一个多小时都写不出来,二叉树那种rc/refcell已经可以无障碍刷题了,链表的box处理还是整不明白。。

--

Neutron3529 2020-06-26 03:04

话说你要不要试试今天的每日一题?

我试了三个小时

最后手工实现了clone……

果然clone是最好的方法

--
👇
lithbitren: 对的into_iter也试过了,确实也不行,取下标遍历的方法其实在别的地方也用过,并查集最后规整集合的时候就得取下标来调用递归查找,这题一开始就总想着是递归函数的问题,所以就没想到这茬,学习了,蟹蟹大佬解惑。

--
Neutron3529: 用下标的原理应该是,self.iter()自带一个更短的生命周期(必须这样,否则会影响之后对self的可变借用),而self.into_iter()会消费掉self

为了绕过这两个,只好强行用下标然后借用了

作者 lithbitren 2020-06-25 19:31

对的into_iter也试过了,确实也不行,取下标遍历的方法其实在别的地方也用过,并查集最后规整集合的时候就得取下标来调用递归查找,这题一开始就总想着是递归函数的问题,所以就没想到这茬,学习了,蟹蟹大佬解惑。

--
Neutron3529: 用下标的原理应该是,self.iter()自带一个更短的生命周期(必须这样,否则会影响之后对self的可变借用),而self.into_iter()会消费掉self

为了绕过这两个,只好强行用下标然后借用了

Neutron3529 2020-06-25 18:59

用下标的原理应该是,self.iter()自带一个更短的生命周期(必须这样,否则会影响之后对self的可变借用),而self.into_iter()会消费掉self

为了绕过这两个,只好强行用下标然后借用了


push那里我忘记改了

毕竟代码不是我写的,改代码的过程中漏了什么挺正常的……

(BTW,按Rust ZCA的说法,总感觉对String执行.to_string()会被编译器省略掉)

--
👇
lithbitren: 确实,用下标引用生命周期就够长了,这个啥原理啊,刷题碰到字符串处理总是得直面生命周期问题[扶额]。

另外pushans的时候应该不用再to_string,所有递归得到的路径都会被pop掉,所以最终路径f的是可以直接消费进最终输出了。

作者 lithbitren 2020-06-25 18:46

确实,用下标引用生命周期就够长了,这个啥原理啊,刷题碰到字符串处理总是得直面生命周期问题[扶额]。

另外pushans的时候应该不用再to_string,所有递归得到的路径都会被pop掉,所以最终路径f的是可以直接消费进最终输出了。

Neutron3529 2020-06-25 17:17

蟹蟹大佬的代码

题目我还没看懂

我只会优化……

现在优化出0ms 2.2MB的代码了

use std::collections::HashMap;
impl Solution {
    pub fn dfs(f: String, d: &mut HashMap<&String, Vec<&String>>, ans: &mut Vec<String>) {
        while let Some(ff)=d.get_mut(&f).unwrap_or(&mut vec![]).pop(){//这里不能保存d.get_mut(&f),否则会出现两次d的可变借用。
            Self::dfs(ff.to_string(),d,ans)
        }
        ans.push(f.to_string());
    }
    pub fn find_itinerary(tickets: Vec<Vec<String>>) -> Vec<String> {
        let mut d: HashMap<&String, Vec<&String>> = HashMap::new();
        for t in 0..tickets.len() {
            d.entry(&tickets[t][0]).or_default().push(&tickets[t][1]);//如果这里写ticket的iter,iter的借用不够长,改成直接借用每一个元素可以保证生命周期足够。
//一个更好的方法可能是定义一个在算得ans之后drop的生命周期,但我不会
//如果在函数那里定义<'a>,由于在函数结束时我们会先drop掉tickets而后drop掉<'a>这个生命周期,于是编译不通过。
//不确定有没有更好的写法
        }
        for (_, f) in d.iter_mut() {
            f.sort_by(|a, b| b.cmp(a));
        }
        let mut ans = vec![];
        Self::dfs("JFK".to_string(), &mut d, &mut ans);
        ans.reverse();
        ans
    }
}
作者 lithbitren 2020-06-25 14:59

蟹蟹大佬,用clone就都跑通了

--
👇
Neutron3529: 遇事不决用.clone()

别的我就不会了

use std::collections::HashMap;
impl Solution {
    pub fn find_itinerary(tickets: Vec<Vec<String>>) -> Vec<String> {
        let mut d: HashMap<String, Vec<String>> = HashMap::new();
        for t in tickets {
            d.entry(t[0].clone()).or_default().push(t[1].clone());
        }
        for (_, f) in d.iter_mut() {
            f.sort_by(|a, b| b.cmp(a));
        }
        let mut ans = vec![];
        fn dfs(f: String, d: &mut HashMap<String, Vec<String>>, ans: &mut Vec<String>) {
            while let Some(ff)=d.get_mut(dbg!(&f)){
                if let Some(fff)=ff.pop(){ 
                    dfs(fff,d,ans)
                }else{break}
            }
            ans.push(f.to_string());
        }
        dfs("JFK".to_string(), &mut d, &mut ans);
        ans.reverse();
        ans
    }
}
Neutron3529 2020-06-25 14:09

遇事不决用.clone()

别的我就不会了

use std::collections::HashMap;
impl Solution {
    pub fn find_itinerary(tickets: Vec<Vec<String>>) -> Vec<String> {
        let mut d: HashMap<String, Vec<String>> = HashMap::new();
        for t in tickets {
            d.entry(t[0].clone()).or_default().push(t[1].clone());
        }
        for (_, f) in d.iter_mut() {
            f.sort_by(|a, b| b.cmp(a));
        }
        let mut ans = vec![];
        fn dfs(f: String, d: &mut HashMap<String, Vec<String>>, ans: &mut Vec<String>) {
            while let Some(ff)=d.get_mut(dbg!(&f)){
                if let Some(fff)=ff.pop(){ 
                    dfs(fff,d,ans)
                }else{break}
            }
            ans.push(f.to_string());
        }
        dfs("JFK".to_string(), &mut d, &mut ans);
        ans.reverse();
        ans
    }
}
1 共 10 条评论, 1 页