2065.力扣每日一题7/1 Java(深度优先搜索DFS)
目录
思路
首先构建一个图的数据结构来表示节点之间的连接关系。然后从起始节点 0 开始进行深度优先搜索(DFS)。在 DFS 过程中,判断当前路径的耗时是否超过给定的最大时间限制,如果超过则直接返回。对于每个相邻节点,如果未访问过则将其标记为已访问,递归地进行 DFS 并累加节点价值,回溯时取消访问标记;如果已访问过则直接递归 DFS。当再次回到节点 0 时,更新最大路径价值。
解题方法
使用哈希表graph存储图的结构,用布尔数组visited记录节点的访问状态,通过递归的 DFS 遍历所有可能的路径来找到最大路径价值。
时间复杂度
𝑂(𝑛×𝑒)
空间复杂度
o(n+e)
Code
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
private int maxValue = 0;
private Map<Integer, List<Edge>> graph;
private int[] values;
private int maxTime;
public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
this.values = values;
this.maxTime = maxTime;
graph = new HashMap<>();
// 构建图
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int time = edge[2];
if (!graph.containsKey(u)) {
graph.put(u, new ArrayList<>());
}
if (!graph.containsKey(v)) {
graph.put(v, new ArrayList<>());
}
graph.get(u).add(new Edge(v, time));
graph.get(v).add(new Edge(u, time));
}
boolean[] visited = new boolean[values.length];
visited[0] = true; // 起始节点 0 已访问
dfs(0, 0, values[0], visited);
return maxValue;
}
private void dfs(int node, int time, int value, boolean[] visited) {
if (time > maxTime) {
return;
}
if (graph.containsKey(node)) { // 增加对节点是否在图中的判断
for (Edge edge : graph.get(node)) {
int nextNode = edge.node;
int nextTime = edge.time;
if (!visited[nextNode]) {
visited[nextNode] = true;
dfs(nextNode, time + nextTime, value + values[nextNode], visited);
visited[nextNode] = false;
} else {
dfs(nextNode, time + nextTime, value, visited);
}
}
}
if (node == 0) {
maxValue = Math.max(maxValue, value);
}
}
static class Edge {
int node;
int time;
Edge(int node, int time) {
this.node = node;
this.time = time;
}
}
}
Life is like a box of chocolates, you never know what you are going to get.
生活就像一盒巧克力,你永远不知道下一个是什么. ——《阿甘正传》
原文地址:https://blog.csdn.net/Rangsh/article/details/140111259
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!