针对图问题“重构行程"的功能/流编程. [英] Functional/Stream programming for the graph problem "Reconstruct Itinerary"

问题描述

我正在尝试解决重建行程问题( https://leetcode.com/problems/使用功能性方法在Scala中重建().Java解决方案有效，但Scala无效.我发现的一个原因是哈希表正在更新，并且每次迭代都具有最新的哈希表(即使从递归中弹出)，这很奇怪.

I am trying to solve the reconstruct itinerary problem (https://leetcode.com/problems/reconstruct-itinerary/) in Scala using functional approach. Java solution works but Scala doesn't. One reason I found out was the hashmap is being updated and every iteration has the latest hashmap (even when popping from recursion) which is weird.

这是Java中的解决方案:

Here is the solution in Java:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution1 {

private void dfg(Map<String, PriorityQueue<String>> adj, LinkedList<String> result, String vertex){
  PriorityQueue<String> pq = adj.get(vertex);
  while (pq!=null && !pq.isEmpty()){
    System.out.println("Before :"+adj.get(vertex));
    String v = pq.poll();
    System.out.println("After :"+ adj.get(vertex));
    dfg(adj,result,v);
  }
  result.addFirst(vertex);
}

public List<String> findItinerary(List<List<String>> tickets){
  Map<String,PriorityQueue<String>> adj = new HashMap<>();
  for(List<String> ticket:  tickets){
    adj.putIfAbsent(ticket.get(0),new PriorityQueue<>());
    adj.get(ticket.get(0)).add(ticket.get(1));
  }
  LinkedList<String> result = new LinkedList<>();
  dfg(adj,result,"JFK");
  //not reverse yet
  return result;
}

public static void main(String[] args){

  List<List<String>> tickets = new ArrayList<>();
  List t1= new ArrayList();
  t1.add("JFK");
  t1.add("SFO");
  tickets.add(t1);
  List t2= new ArrayList();
  t2.add("JFK");
  t2.add("ATL");
  tickets.add(t2);
  List t3= new ArrayList();
  t3.add("SFO");
  t3.add("ATL");
  tickets.add(t3);
  List t4= new ArrayList();
  t4.add("ATL");
  t4.add("JFK");
  tickets.add(t4);
  List t5= new ArrayList();
  t5.add("ATL");
  t5.add("SFO");
  tickets.add(t5);


  System.out.println();
  Solution1 s1 = new Solution1();
  List<String> finalRes  = s1.findItinerary(tickets);

  for(String model : finalRes) {
    System.out.print(model + " ");
  }
}

}

这是我在Scala中无法使用的解决方案:

Here is my solution in Scala which is not working:

package graph

class Itinerary {

}

case class Step(g: Map[String,List[String]],sort: List[String]=List())
object Solution {
  def main(arr: Array[String]) = {
    val tickets = List(List("JFK","SFO"),List("JFK","ATL"),List("SFO","ATL"),List("ATL","JFK"),List("ATL","SFO"))
    println(findItinerary(tickets))
  }
  def findItinerary(tickets: List[List[String]]): List[String] = {
    val g = tickets.foldLeft(Map[String,List[String]]())((m,t)=>{
      val key=t(0)
      val value= t(1)
      m + (key->(m.getOrElse(key,Nil) :+ value).sorted)
    })
    println(g)
    // g.keys.foldLeft(Step())((s,n)=> dfs(n,g,s)).sort.toList
    dfs("JFK",Step(g)).sort.toList
  }

  def dfs(vertex: String,step: Step): Step = {
    println("Input vertex " + vertex)
    println("Input map "+ step.g)
    val updatedStep= step.g.getOrElse(vertex,Nil).foldLeft(step) ((s,n)=>{
      //println("Processing "+n+" of vertex "+vertex)
      //delete link
      val newG = step.g + (vertex->step.g.getOrElse(vertex,Nil).filter(v=>v!=n))
      // println(newG)
      dfs(n,step.copy(g=newG))
    })
    println("adding vertex to result "+vertex)
    updatedStep.copy(sort = updatedStep.sort:+vertex)
  }
}

推荐答案

Scala有时被认为是更好"的解决方案.Java，但这确实是非常有限的.如果您可以进入FP思维方式并学习标准库，就会发现它是一个全新的世界.

Scala is sometimes approached as a "better" Java, but that's really very limiting. If you can get into the FP mindset, and study the Standard Library, you'll find that it's a whole new world.

def findItinerary(tickets: List[List[String]]): List[String] = {
  def loop(from : String
          ,jump : Map[String,List[String]]
          ,acc  : List[String]) : List[String] = jump.get(from) match {
    case None => if (jump.isEmpty) from::acc else Nil
    case Some(next::Nil) => loop(next, jump - from, from::acc)
    case Some(nLst) =>
      nLst.view.map{ next =>
        loop(next, jump+(from->(nLst diff next::Nil)), from::acc)
      }.find(_.lengthIs > 0).getOrElse(Nil)
  }
  loop("JFK"
      ,tickets.groupMap(_(0))(_(1)).map(kv => kv._1 -> kv._2.sorted)
      ,Nil).reverse
}

这篇关于针对图问题“重构行程"的功能/流编程.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！