。找到最终的安全状态
802。查找最终的安全状态
难度:中等
>主题:深度优先搜索,广度优先搜索,图形,拓扑排序
有一个定向的n个节点图,每个节点从0到n -1标记。该图由a 0- indexed
终端节点。节点是a安全节点如果从该节点开始的每个可能的路径都会导致>终端节点(或另一个安全节点)。
返回一个包含图形的所有安全节点的数组。答案应以上升顺序排序。
>>示例1:
>输入:
graph = [[1,2,3,4],[1,2],[3,4],[0,4],[0,4],[]] >输出:
[4]- >说明:只有节点4是一个终端节点,从节点4开始的每个路径都会导致节点4。 >
- >约束:
- > n == graph.length
- 0< = graph [i] [j]< = n -1
- 图[i]以严格增加的顺序进行排序。 该图可能包含自宽。 >
- 图中的边数将在[1,4 * 10 4
- ]范围内。
- 解决方案:
- 我们需要识别图表中的所有安全节点。这涉及检查是否从给定节点开始,每个路径最终都到达终端节点或其他安全节点。该解决方案使用深度优先搜索(DFS)来检测周期并将节点分类为安全或不安全。
关键见解:
-
>终端节点:一个没有传出边缘的节点是终端节点。
- >安全节点:一个节点是安全的,如果从该节点开始,所有路径最终都会导致终端节点或其他安全节点。 循环检测
- :如果节点是周期的一部分,则不是一个安全的节点,因为从其开始的路径不会导致终端节点。
方法:
我们使用DFS探索每个节点并确定它是否是周期的一部分。循环或导致周期的一部分的节点标记不安全。
>最终导致终端节点或其他安全节点的节点被标记为安全。 - 我们使用一个访问的数组,带有三个状态:
- 0:尚未访问该节点。
1:该节点当前正在访问(即,在递归堆栈中)。
>-
2:该节点已完全处理并且是安全的。
- 步骤:
- >为每个节点执行DFS。
使用访问的状态标记安全/不安全的节点。
收集所有安全的节点。 - >让我们在PHP中实现此解决方案:
802。查找最终的安全状态 - 解释:
dfs函数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
<?php
/**
* @param Integer[][] $graph
* @return Integer[]
*/
function
eventualSafeNodes(
$graph
) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* DFS helper function
*
* @param $node
* @param $graph
* @param $visited
* @return int|mixed
*/
function
dfs(
$node
,
$graph
, &
$visited
) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
$graph1
= [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2
= [[1,2,3,4],[1,2],[3,4],[0,4],[]];
print_r(eventualSafeNodes(
$graph1
)) .
"\n"
;
// Output: [2,4,5,6]
print_r(eventualSafeNodes(
$graph2
)) .
"\n"
;
// Output: [4]
?>
登录后复制登录后复制- 如果其任何邻居都导致一个周期(由DFS($ neighbor)== 1表示),则该节点标记为不安全(1)。
- 如果所有邻居都导致终端节点或安全节点,则标记为安全(2)。
- 主函数
- :
- 我们迭代所有节点,并使用DFS检查每个节点是否安全。
- > >所有安全节点均收集在$ Safenodes数组中并返回。
> -
示例演练: 示例1:
- 在此示例中,节点5和6是终端节点(无外部边缘)。
- >节点4导致节点5,因此也是安全的。
>节点2导致节点5,因此它是安全的。 >
输出:
1
2
$graph
= [[1,2],[2,3],[5],[0],[5],[],[]];
print_r(eventualSafeNodes(
$graph
));
登录后复制-
示例2:
- 在此示例中,只有节点4是终端节点,从节点4开始的所有路径引向节点4。
- 所有其他节点最终导致周期或不安全的节点。
- 输出:
> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
<strong><?php
/**
* @param Integer[][] $graph
* @return Integer[]
*/
function
eventualSafeNodes(
$graph
) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* DFS helper function
*
* @param $node
* @param $graph
* @param $visited
* @return int|mixed
*/
function
dfs(
$node
,
$graph
, &
$visited
) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
$graph1
= [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2
= [[1,2,3,4],[1,2],[3,4],[0,4],[]];
print_r(eventualSafeNodes(
$graph1
)) .
"\n"
;
// Output: [2,4,5,6]
print_r(eventualSafeNodes(
$graph2
)) .
"\n"
;
// Output: [4]
?>
</strong>
登录后复制登录后复制时间和空间复杂度:
- 时间复杂度:O(n e),其中n是节点数,e 是边数。我们访问每个节点一次并处理每条边一次。
- 空间复杂度:O(n) 用于访问的数组和递归堆栈。
该解决方案使用 DFS 有效地确定安全节点,确保满足问题约束。
联系链接
如果您发现本系列有帮助,请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!
如果您想要更多类似的有用内容,请随时关注我:
- 领英
- GitHub
-
>终端节点:一个没有传出边缘的节点是终端节点。
以上是。找到最终的安全状态的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

在PHP中,应使用password_hash和password_verify函数实现安全的密码哈希处理,不应使用MD5或SHA1。1)password_hash生成包含盐值的哈希,增强安全性。2)password_verify验证密码,通过比较哈希值确保安全。3)MD5和SHA1易受攻击且缺乏盐值,不适合现代密码安全。

PHP类型提示提升代码质量和可读性。1)标量类型提示:自PHP7.0起,允许在函数参数中指定基本数据类型,如int、float等。2)返回类型提示:确保函数返回值类型的一致性。3)联合类型提示:自PHP8.0起,允许在函数参数或返回值中指定多个类型。4)可空类型提示:允许包含null值,处理可能返回空值的函数。

PHP主要是过程式编程,但也支持面向对象编程(OOP);Python支持多种范式,包括OOP、函数式和过程式编程。PHP适合web开发,Python适用于多种应用,如数据分析和机器学习。

PHP适合网页开发和快速原型开发,Python适用于数据科学和机器学习。1.PHP用于动态网页开发,语法简单,适合快速开发。2.Python语法简洁,适用于多领域,库生态系统强大。

PHP起源于1994年,由RasmusLerdorf开发,最初用于跟踪网站访问者,逐渐演变为服务器端脚本语言,广泛应用于网页开发。Python由GuidovanRossum于1980年代末开发,1991年首次发布,强调代码可读性和简洁性,适用于科学计算、数据分析等领域。

PHP在现代化进程中仍然重要,因为它支持大量网站和应用,并通过框架适应开发需求。1.PHP7提升了性能并引入了新功能。2.现代框架如Laravel、Symfony和CodeIgniter简化开发,提高代码质量。3.性能优化和最佳实践进一步提升应用效率。

PHP的核心优势包括易于学习、强大的web开发支持、丰富的库和框架、高性能和可扩展性、跨平台兼容性以及成本效益高。1)易于学习和使用,适合初学者;2)与web服务器集成好,支持多种数据库;3)拥有如Laravel等强大框架;4)通过优化可实现高性能;5)支持多种操作系统;6)开源,降低开发成本。

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip
