09-06 20:16 门头沟学院 后端 发布于浙江
关注
陌陌笔试-Java研发工程师（商业化）
1.构建图使用递归和回溯实现最长路径
通过100%
public class Solution {
public String LongestBehaviorPath (String[] paths) {
Map> graph = new HashMap<>();
Map indegree = new HashMap<>();
for(String path : paths){
String []steps = path.split("->");
for(int i = 0;i
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 startNodes = new ArrayList<>();
for(String node:indegree.keySet()){
if(indegree.get(node) == 0){
startNodes.add(node);
}
}
List longestPath = new ArrayList<>();
for(String start : startNodes){
dfs(start,new ArrayList<>(),graph,longestPath);
}
return String.join("->",longestPath);
}
private static void dfs(String node,List path,Map> graph,List 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%
通过100%
public class Solution {
public String LongestBehaviorPath (String[] paths) {
Map
Map
for(String path : paths){
String []steps = path.split("->");
for(int i = 0;i
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
for(String node:indegree.keySet()){
if(indegree.get(node) == 0){
startNodes.add(node);
}
}
List
for(String start : startNodes){
dfs(start,new ArrayList<>(),graph,longestPath);
}
return String.join("->",longestPath);
}
private static void dfs(String node,List
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%
全部评论
灰太狼4
门头沟学院 golang
我也这题，感觉好简单😅
offerO一下吧
门头沟学院 Java
双重for都能解决吗
相关推荐
查看6道真题和解析 点赞 评论 收藏
分享
