题目描述

给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下：

1.在一秒内，青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点（如果它们直接相连）。 2.青蛙无法跳回已经访问过的顶点。 3.如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。 4.如果青蛙不能跳到任何未访问过的顶点上，那么它每次跳跃都会停留在原地。 5.无向树的边用数组 edges 描述，其中 edges[i] = [fromi, toi] 意味着存在一条直接连通 fromi 和 toi 两个顶点的边。

返回青蛙在 t 秒后位于目标顶点 target 上的概率。

 

示例 1：

输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4 输出：0.16666666666666666  解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，第 1 秒 有 1/3 的概率跳到顶点 2 ，然后第 2 秒 有 1/2 的概率跳到顶点 4，因此青蛙在 2 秒后位于顶点 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。 

示例 2：

输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7 输出：0.3333333333333333 解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，有 1/3 = 0.3333333333333333 的概率能够 1 秒 后跳到顶点 7 。

 

示例 3：

输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6 输出：0.16666666666666666

提示：

1 <= n <= 100 edges.length == n-1 edges[i].length == 2 1 <= edges[i][0], edges[i][1] <= n 1 <= t <= 50 1 <= target <= n 与准确值误差在 10^-5 之内的结果将被判定为正确。

 

解题思路:

根据已知的规则，我们可以得出的结论有，青蛙每跳一次花一个时间单位，并且青蛙如果有能跳的位置，青蛙必须继续跳直到不能跳停在那里。我们判断是否能到达目的地的基准有两种，一种是青蛙到达目的地所花费的时间刚刚好与最大能花费的时间相等；第二种就是青蛙到达目的地花费的时间小于最大能花费的时间，并且无路可以继续走了。上述两种情况都可以返回计算得到的概率，否则返回的概率为0。

 

代码:

class Solution { public double frogPosition(int n, int[][] edges, int t, int target) { int preTarget = target; //数据预处理，将图存储下来 HashMap<Integer,List<Integer>> map = new HashMap<>(); //特殊情况 if(edges.length == 0)return 1d; //无向图，所以两边都要存储 for(int i=0;i<edges.length;i++){ if(map.get(edges[i][0]) == null){ map.put(edges[i][0],new ArrayList<Integer>()); } if(map.get(edges[i][1]) == null){ map.put(edges[i][1],new ArrayList<Integer>()); } map.get(edges[i][0]).add(edges[i][1]); map.get(edges[i][1]).add(edges[i][0]); } boolean[] flag = new boolean[n]; return findPath(map,target,1,flag,0,1,t); } public double findPath(HashMap<Integer,List<Integer>> map ,int target ,int source //flag 数组用来标记当前节点是否已经被使用 ,boolean[] flag //res是走的步数，也就是要花的时间 //point 就是概率 //t就是最大能花的时间 ,int res,double point,int t){ if(source == target){ //1.如果最终到达目标，并且花的时间和最大能花的时间相等就直接返回概率 //2.否则，如果到达了目的地，并且后续再无节点可去，也直接返回概率 if(res == t || (res < t && containPath(flag,map.get(source)) == 0)) return point; //3.否则就是花的时间超过了最大时间，或者是虽然到达了目的地，但是后续还有能跳的节点，所以越过了目的地 else return 0d; } flag[source-1] = true; //获取当前节点连通的所有节点 List<Integer> nodes = map.get(source); //遍历连通的节点 for(int i=0;i<nodes.size();i++){ if(!flag[nodes.get(i)-1]){ double ret = findPath(map,target ,nodes.get(i) ,flag,res+1,point * (1d/(double)containPath(flag,nodes)),t); if(ret!=-1) return ret; } } flag[source-1] = false; return -1; } //这个函数用来计算某个节点，还有剩下多少个未被使用并且能到达的节点 public int containPath(boolean[] flag,List<Integer> nodes){ int ret = 0; for(int i=0;i<nodes.size();i++){ if(!flag[nodes.get(i)-1]){ ret++; } } return ret; } }