陌陌笔试-Java研发工程师（商业化）

1.构建图使用递归和回溯实现最长路径
通过100%
public class Solution {
    public String LongestBehaviorPath (String[] paths) {
    
        Map<String,List<String>> graph = new HashMap<>();
        Map<String,Integer> indegree = new HashMap<>();
        for(String path : paths){
            String []steps = path.split(&quot;->&quot;);
            for(int i = 0;i<steps.length-1;i++){
                graph.putIfAbsent(steps[i],new ArrayList<>());
                graph.get(steps[i]).add(steps[i+1]);
                indegree.put(steps[i+1],indegree.getOrDefault(steps[i+1],0)+1);
                indegree.putIfAbsent(steps[i],0);
            }
        }

        List<String> startNodes = new ArrayList<>();
        for(String node:indegree.keySet()){
            if(indegree.get(node) == 0){
                startNodes.add(node);
            }
        }

        List<String> longestPath = new ArrayList<>();

        for(String start : startNodes){
            dfs(start,new ArrayList<>(),graph,longestPath);
        }

       return String.join(&quot;->&quot;,longestPath); 
    }

    private static void dfs(String node,List<String> path,Map<String,List<String>> graph,List<String> longestPath){
        path.add(node);
        if(path.size()> longestPath.size()){
            longestPath.clear();
            longestPath.addAll(new ArrayList<>(path));
        }

        if(graph.containsKey(node)){
            for(String neighbor: graph.get(node)){
                dfs(neighbor,path,graph,longestPath);
            }
        }

        path.remove(path.size() - 1);

    }
}

2.求逆值对
双重for循环遍历比较
通过100%