数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中 T 秒后青蛙的位置
假设我们有一个由 n 个顶点组成的无向树。顶点编号从 1 到 n。现在一只青蛙从顶点 1 开始跳跃。如果青蛙当前的顶点和另一个未访问的顶点相邻，它可以在一秒钟内跳到该顶点。青蛙不能跳回已访问的顶点。如果青蛙可以跳到多个顶点，它会随机跳到其中一个顶点
概率相同，否则，当青蛙无法跳到任何未访问的顶点时，它会永远停留在同一个顶点上。
树以边的数组形式给出。我们必须找到青蛙在 t 秒后位于顶点 target 的概率。
因此，如果输入类似于 n 为 7，t 为 2，target 为 4，树类似于 -
那么输出将为 0.1666，从图中可以看出。青蛙从顶点 1 开始，以 0.3333 的概率在第 1 秒跳到顶点 2，然后以 0.5 的概率在第 2 秒跳到顶点 4。因此，青蛙在 2 秒后位于顶点 4 的概率为 0.3333 * 0.5 = 1.6665。
为了解决这个问题，我们将遵循以下步骤 -
ret := 1
定义一个集合 visited
定义一个函数 dfs()，它将接收节点、起点、边列表 g、时间、t、一个栈 st，
如果节点是 visited 的成员，则 -
返回 false
将节点插入 visited
如果节点与 1 相同，则 -
tt := time，ok := true
返回 true
对于初始化 i := 0，当 i < g[node] 的大小，更新（将 i 增加 1），执行 -
将 g[node, i] 插入 st
如果 dfs(g[node, i], start, g, time + 1, t, st) 为 true，则 -
返回 true
从 st 中删除元素
返回 false
从主方法执行以下操作 -
ret := 1
ok := false
定义一个大小为 n + 1 的列表数组 graph
定义一个大小为 n + 1 的列表数组 graph2
对于初始化 i := 0，当 i < edges 的大小，更新（将 i 增加 1），执行 -
将 edges[i, 1] 插入 graph[edges[i, 0]] 的末尾
将 edges[i, 0] 插入 graph[edges[i, 1]] 的末尾
定义一个栈 st
dfs(target, target, graph, 0, t, st)
当 (st 不为空) 时，执行 -
node := st 的顶部元素
sz := graph[node] 的大小
如果 node 不等于 1，则 -
(将 sz 减 1)
ret := ret * (1.0 / sz)
从 st 中删除元素
如果 tt > t，则 -
返回 0
如果 tt 与 t 相同，则 -
返回 ret
如果 tt < t 且 target 与 1 相同且 graph[target] 的大小 >= 1，则 -
返回 0
返回（如果 tt < t 且 graph[target] 的大小 > 1，则为 0，否则为 ret）
让我们看看以下实现以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
double ret = 1;
bool ok;
set<int> visited;
int tt;
bool dfs(int node, int start, vector<int> g[], int time, int t,
stack<int>& st){
if (visited.count(node))
return false;
visited.insert(node);
if (node == 1) {
tt = time;
ok = true;
return true;
}
for (int i = 0; i < g[node].size(); i++) {
st.push(g[node][i]);
if (dfs(g[node][i], start, g, time + 1, t, st))
return true;
;
st.pop();
}
return false;
}
double frogPosition(int n, vector<vector<int> >& edges, int t,
int target){
ret = 1;
ok = false;
vector<int> graph[n + 1];
vector<int> graph2[n + 1];
for (int i = 0; i < edges.size(); i++) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
stack<int> st;
dfs(target, target, graph, 0, t, st);
while (!st.empty()) {
int node = st.top();
double sz = (double)graph[node].size();
if (node != 1)
sz--;
ret *= (1.0 / sz);
st.pop();
}
if (tt > t)
return 0;
if (tt == t)
return ret;
if (tt < t && target == 1 && graph[target].size() >= 1)
return 0;
return tt < t && graph[target].size() > 1 ? 0 : ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};
cout << (ob.frogPosition(7,v,2,4));
}输入
7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4输出
0.166667
273 次查看
