در این مطلب، ویدئو وضعیت های امن احتمالی را پیدا کنید – Leetcode 802 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:13:17
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,000 –> 00:00:01,680
سلام به همه خوش آمدید و بیایید
2
00:00:01,680 –> 00:00:03,600
امروز یک کد دقیق تر بنویسیم، بنابراین امروز
3
00:00:03,600 –> 00:00:06,160
بیایید این مشکل را حل
4
00:00:06,160 –> 00:00:09,280
کنیم، حالت های ایمن نهایی را پیدا کنیم به ما یک نمودار هدایت شده
5
00:00:09,280 –> 00:00:12,160
از n گره داده می شود که در آن هر گره
6
00:00:12,160 –> 00:00:15,200
بین 0 تا n منهای 1 برچسب گذاری شده است. اکنون در
7
00:00:15,200 –> 00:00:17,680
واقع به ما داده می شود. گراف به عنوان یک
8
00:00:17,680 –> 00:00:21,359
آرایه دو بعدی است، بنابراین اساسا نمودار در
9
00:00:21,359 –> 00:00:25,279
شاخص i نشان دهنده تمام
10
00:00:25,279 –> 00:00:28,640
همسایگان گره i خواهد بود، به عنوان مثال اگر i
11
00:00:28,640 –> 00:00:31,119
برابر با 0 باشد، همه
12
00:00:31,119 –> 00:00:33,680
همسایه های گره صفر را دریافت می کنیم، بنابراین
13
00:00:33,680 –> 00:00:36,480
اساسا نمودار در شاخص i یک لیست است.
14
00:00:36,480 –> 00:00:39,200
اما به یاد داشته باشید که یال ها جهت دار هستند،
15
00:00:39,200 –> 00:00:41,600
بنابراین به این معنی است که اجازه دهید
16
00:00:41,600 –> 00:00:44,640
به اولین مثال زیر در شاخص 0 نگاهی بیندازیم،
17
00:00:44,640 –> 00:00:46,719
می توانیم ببینیم که این لیست فرعی است که
18
00:00:46,719 –> 00:00:50,559
ما 1 داریم و 2 به این معنی است که از گره 0
19
00:00:50,559 –> 00:00:54,399
یک یال وجود دارد. به سمت خارج از
20
00:00:54,399 –> 00:00:58,399
0 به گره اول و یک یال که
21
00:00:58,399 –> 00:01:01,520
به سمت بیرون به گره دوم می رود به طور مشابه
22
00:01:01,520 –> 00:01:02,640
یکی بعدی
23
00:01:02,640 –> 00:01:04,319
دو و سه است، یعنی دو
24
00:01:04,319 –> 00:01:07,680
یال از این گره به دو می رود
25
00:01:07,680 –> 00:01:10,640
و به سه نیز به ما گفته می شود که یک
26
00:01:10,640 –> 00:01:12,560
گره پایانی یک گره ای که
27
00:01:12,560 –> 00:01:16,159
ندارد هر یال خروجی بنابراین 6
28
00:01:16,159 –> 00:01:18,080
البته یک گره ترمینال است،
29
00:01:18,080 –> 00:01:21,280
لبه های خروجی
30
00:01:21,280 –> 00:01:25,280
وجود ندارد.
31
00:01:25,280 –> 00:01:28,880
32
00:01:28,880 –> 00:01:31,280
33
00:01:31,280 –> 00:01:33,040
می توانید ببینید سه دارای یک
34
00:01:33,040 –> 00:01:35,280
لبه است که بیرون می رود دو دارای یک لبه است
35
00:01:35,280 –> 00:01:37,040
و شما بقیه را نیز می دانید، اما ما
36
00:01:37,040 –> 00:01:38,720
چندان به گره های پایانه علاقه مند
37
00:01:38,720 –> 00:01:40,960
نیستیم، در واقع بیشتر به گره های ایمن علاقه مندیم
38
00:01:40,960 –> 00:01:44,000
و گره ایمن به عنوان گرهی تعریف می
39
00:01:44,000 –> 00:01:47,360
شود که اگر تمام
40
00:01:47,360 –> 00:01:49,040
مسیرهای ممکن را از
41
00:01:49,040 –> 00:01:51,439
این گره، هر لبه خروجی را انتخاب می کردید و سپس
42
00:01:51,439 –> 00:01:55,200
به
43
00:01:55,200 –> 00:01:57,759
راه خود ادامه می
44
00:01:57,759 –> 00:02:01,360
دادید، در نهایت همه مسیرها به گره های پایانه منتهی می شدند، اگر باهوش باشید، آنچه
45
00:02:01,360 –> 00:02:03,920
می خواهید متوجه شوید این است
46
00:02:03,920 –> 00:02:06,320
که معنای واقعی آن این است که هیچ
47
00:02:06,320 –> 00:02:09,440
چرخه ای در نمودار وجود ندارد زیرا به آن فکر
48
00:02:09,440 –> 00:02:12,720
کنید که اگر به یک
49
00:02:12,720 –> 00:02:15,360
گره پایانه نرسیدیم، چطور ممکن
50
00:02:15,360 –> 00:02:18,400
است به صفر از صفر نگاه کنیم، می توانیم
51
00:02:18,400 –> 00:02:22,640
به یک از یک برویم، می توانیم به سه از
52
00:02:22,640 –> 00:02:26,640
سه برویم و در نهایت به آن برگردیم. صفر است بنابراین
53
00:02:26,640 –> 00:02:29,120
حتی مات نمی شود مسیرهای دیگر
54
00:02:29,120 –> 00:02:32,400
از صفر چیست زیرا ما یک
55
00:02:32,400 –> 00:02:36,000
مسیر را پیدا کردیم که هرگز به یک
56
00:02:36,000 –> 00:02:38,319
گره ترمینال منتهی نمی شود، اما فقط برای اینکه نگاهی
57
00:02:38,319 –> 00:02:40,000
بیندازیم ببینیم اگر مسیر دیگری را انتخاب می کردیم چه اتفاقی می افتاد،
58
00:02:40,000 –> 00:02:43,040
فرض کنید به یک رسیدیم و
59
00:02:43,040 –> 00:02:45,440
به جای اینکه به سه برویم. فرض کنید ما
60
00:02:45,440 –> 00:02:50,000
به دو رفتیم، سپس دو فقط یک
61
00:02:50,000 –> 00:02:53,360
یال خروجی دیگر دارد که ما را به پنج یال خروجی می رساند که ما را به پنج می
62
00:02:53,360 –> 00:02:56,319
رساند.
63
00:02:56,319 –> 00:03:00,000
64
00:03:00,000 –> 00:03:02,640
65
00:03:02,640 –> 00:03:04,480
از آنجایی که یکی از مسیرهایی
66
00:03:04,480 –> 00:03:07,200
که قبلا دیدیم به چرخه منتهی می شود، بنابراین
67
00:03:07,200 –> 00:03:10,640
صفر گره ایمن نیست، اما با انجام همه این موارد
68
00:03:10,640 –> 00:03:13,760
متوجه شدید
69
00:03:13,760 –> 00:03:16,319
که آیا صفر گره ایمن است یا نه،
70
00:03:16,319 –> 00:03:20,000
ما به چند چیز دیگر پی بردیم.
71
00:03:20,000 –> 00:03:24,560
نشان می دهد که یکی نیز گره ایمن
72
00:03:24,560 –> 00:03:27,280
نیست زیرا یکی بخشی از چرخه اصلی
73
00:03:27,280 –> 00:03:30,640
بود که از صفر تا یک تا سه
74
00:03:30,640 –> 00:03:33,360
به 0 برگشته بود. بنابراین آن نیز بخشی از
75
00:03:33,360 –> 00:03:36,959
چرخه بود بنابراین 1 نیز گره ایمن نیست و
76
00:03:36,959 –> 00:03:40,959
ما نیز پیدا کردیم که 2 یک گره امن است
77
00:03:40,959 –> 00:03:43,599
زیرا ما از تمام
78
00:03:43,599 –> 00:03:46,560
مسیرهای خروجی ممکن عبور کردیم از 2 فقط ما را به
79
00:03:46,560 –> 00:03:48,799
5 رساند و بعد نمی توانستیم کار دیگری انجام دهیم
80
00:03:48,799 –> 00:03:52,159
بنابراین 2 یک یادداشت امن است همه مسیرها از
81
00:03:52,159 –> 00:03:54,799
2 به یک گره ترمینال منتهی می شوند همچنین البته
82
00:03:54,799 –> 00:03:56,799
متوجه شدیم که 5 یک گره امن است
83
00:03:56,799 –> 00:03:59,439
زیرا یک ترمینال است. نود چرا
84
00:03:59,439 –> 00:04:02,400
این مهم است به این دلیل است که ما مجبور نخواهیم بود
85
00:04:02,400 –> 00:04:05,360
کارهای تکراری زیادی انجام دهیم زیرا با
86
00:04:05,360 –> 00:04:08,159
پرسیدن این سوال که آیا 0 یک گره ایمن است یا خیر،
87
00:04:08,159 –> 00:04:10,799
متوجه شدیم که دسته ای از
88
00:04:10,799 –> 00:04:13,599
گره ها گره های ایمن هستند یا نیستند و برنده شدیم.
89
00:04:13,599 –> 00:04:16,399
اکنون باید دوباره آنها را بررسی کنیم، این
90
00:04:16,399 –> 00:04:20,720
بدان معناست که ما میتوانیم این الگوریتم را در o بزرگ در
91
00:04:20,720 –> 00:04:24,960
o بزرگ انجام دهیم، فرض کنید زمان e به علاوه v این
92
00:04:24,960 –> 00:04:27,040
یک نوع روش استاندارد برای نوشتن آن است.
93
00:04:27,040 –> 00:04:29,360
این به این معنی است که پیچیدگی زمانی
94
00:04:29,360 –> 00:04:32,800
تعداد کل لبههای
95
00:04:32,800 –> 00:04:36,320
نمودار به اضافه تعداد کل رئوس
96
00:04:36,320 –> 00:04:39,440
یا گرهها در نمودار، زیرا ما
97
00:04:39,440 –> 00:04:42,240
این کار را به صورت بازگشتی با
98
00:04:42,240 –> 00:04:44,160
الگوریتم جستجوی اول عمق
99
00:04:44,160 –> 00:04:46,240
100
00:04:46,240 –> 00:04:48,479
انجام
101
00:04:48,479 –> 00:04:50,479
میدهیم. ما این کار را انجام می دهیم و از
102
00:04:50,479 –> 00:04:52,160
استدلالی که قبلاً در مورد آن صحبت کردم استفاده
103
00:04:52,160 –> 00:04:54,720
نمی کنیم همیشه یک گره یا
104
00:04:54,720 –> 00:04:57,600
یک لبه را مجدداً مشاهده کنید، به همین دلیل است که این
105
00:04:57,600 –> 00:04:59,919
پیچیدگی زمانی خواهد بود و قبل از اینکه آن را کدنویسی کنیم،
106
00:04:59,919 –> 00:05:02,240
تقریباً تا آنجایی که می توانید برای این مشکل خوب به دست آورید
107
00:05:02,240 –> 00:05:04,400
، اجازه دهید فقط
108
00:05:04,400 –> 00:05:06,320
چند تکنیک را به شما نشان دهم که
109
00:05:06,320 –> 00:05:09,360
از آنها استفاده می کنیم. به این پیچیدگی زمانی دست یابیم، بنابراین
110
00:05:09,360 –> 00:05:12,639
از یک نقشه هشم برای ترسیم هر
111
00:05:12,639 –> 00:05:15,440
گره به وضعیت
112
00:05:15,440 –> 00:05:17,360
ایمن بودن یا نبودن آن استفاده می کنیم و در واقع فکر نمی
113
00:05:17,360 –> 00:05:18,880
کنم حتی اشاره کرده باشم که
114
00:05:18,880 –> 00:05:21,520
در این مشکل چه چیزی را برمی گردانیم.
115
00:05:21,520 –> 00:05:23,520
اساساً برای هر گره ای که می
116
00:05:23,520 –> 00:05:25,680
خواهیم بدانیم ایمن است یا نه و می خواهیم
117
00:05:25,680 –> 00:05:27,520
آن را به ترتیب صعودی برگردانیم که
118
00:05:27,520 –> 00:05:29,199
کاملاً ساده است، فقط به این معنی است که برای
119
00:05:29,199 –> 00:05:31,120
هر گره ای که در اینجا داریم
120
00:05:31,120 –> 00:05:34,160
به آرایه ای نگاشت می شود که اساساً
121
00:05:34,160 –> 00:05:36,800
می خواهیم لیستی از تمام
122
00:05:36,800 –> 00:05:40,000
گره های ایمن را برگردانید، بنابراین اگر بتوانیم متوجه شویم که آیا
123
00:05:40,000 –> 00:05:42,479
یک گره ایمن است یا نه، سپس
124
00:05:42,479 –> 00:05:45,600
آن را به خروجی اضافه می کنیم، بنابراین از آنجایی
125
00:05:45,600 –> 00:05:47,520
که می خواهیم آن را به ترتیب صعودی برگردانیم،
126
00:05:47,520 –> 00:05:49,680
اگرچه احتمالاً باید به صورت صعودی برویم.
127
00:05:49,680 –> 00:05:51,600
سفارشی که باید بپرسیم xero
128
00:05:51,600 –> 00:05:54,479
safe یا n است یکی ایمن است یا نه و غیره
129
00:05:54,479 –> 00:05:56,800
ما آن نقشه برداری را می سازیم و در همان
130
00:05:56,800 –> 00:06:00,080
زمان آرایه خروجی خود را می سازیم، اما
131
00:06:00,080 –> 00:06:01,680
اجازه دهید به شما نشان دهم که چرا این نقشه هش
132
00:06:01,680 –> 00:06:03,680
برای کارآمد کردن راه حل مهم است،
133
00:06:03,680 –> 00:06:05,440
بنابراین ابتدا باید داشته باشیم. یک
134
00:06:05,440 –> 00:06:07,520
حلقه for که از صفر تا شش می گذرد،
135
00:06:07,520 –> 00:06:08,880
ما از اول شروع می کنیم و
136
00:06:08,880 –> 00:06:10,160
همانطور که قبلا نشان دادم
137
00:06:10,160 –> 00:06:13,600
یک dfs روی آن انجام می دهیم، بنابراین به
138
00:06:13,600 –> 00:06:16,319
یکی از گره های خروجی می رویم که به یک می رسیم
139
00:06:16,319 –> 00:06:18,960
و سپس از یکی از آنها به
140
00:06:18,960 –> 00:06:21,840
گره خروجی دیگری می رویم که به
141
00:06:21,840 –> 00:06:24,400
2 می رسیم و سپس از 2 به
142
00:06:24,400 –> 00:06:26,800
تنها گره خروجی می رویم
143
00:06:26,800 –> 00:06:29,759
که 5 است. اکنون نمی توانیم به جای دیگری برویم.
144
00:06:29,759 –> 00:06:33,120
چیزی که ما تعیین کردیم این است که 5 یک گره ایمن است،
145
00:06:33,120 –> 00:06:35,680
بنابراین به یاد داشته باشید که بیایید جلو برویم
146
00:06:35,680 –> 00:06:38,800
و آن را به هشمپ خود اضافه کنیم، بنابراین برای پنج
147
00:06:38,800 –> 00:06:41,680
مورد، درست میگوییم که ایمن است و سپس به
148
00:06:41,680 –> 00:06:43,919
صورت بازگشتی در نهایت
149
00:06:43,919 –> 00:06:46,479
به دو برمیگردیم و چه چیزی میخواهیم بگوییم
150
00:06:46,479 –> 00:06:50,080
که همه همسایههای 2 که
151
00:06:50,080 –> 00:06:52,560
فقط شامل 5 میشود، همه همسایههای
152
00:06:52,560 –> 00:06:55,680
آن امن بودند، بنابراین باید به این معنی باشد که 2
153
00:06:55,680 –> 00:06:58,160
نیز یک گره امن، بنابراین ما می خواهیم
154
00:06:58,160 –> 00:07:02,160
آن را به