字符串递归问题，leetcode 332. 重新安排行程

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 2021-04-23 22:03

rust对临时变量管理非常松散：rust会在if let语句执行完之后才释放if let生成的临时变量

于是if let Some(x)=xx.get_mut(xxx).pop(){...}里面，临时变量xx.get_mut(xxx)会活很久

这导致dfs的时候，临时变量xx.get_mut(xxx)不能被释放，也就是两次可变借用

解法是if let Some(x)={xxxx=xx.get_mut(xxx).pop();xxxx}{...}

--
👇
123dou: 能稍微解释一下--“//这里不能保存d.get_mut(&f)，否则会出现两次d的可变借用。”d.get_mut(&f)保存与不保存的区别吗

--
👇
lithbitren: 蟹蟹大佬，用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
    }
}

123dou 2021-04-21 01:39

能稍微解释一下--“//这里不能保存d.get_mut(&f)，否则会出现两次d的可变借用。”d.get_mut(&f)保存与不保存的区别吗

--
👇
lithbitren: 蟹蟹大佬，用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-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 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: 确实，用下标引用生命周期就够长了，这个啥原理啊，刷题碰到字符串处理总是得直面生命周期问题[扶额]。

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

作者 lithbitren 2020-06-25 18:46

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

另外push进ans的时候应该不用再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 共 12 条评论, 1 页