در این مطلب، ویدئو مناطق احاطه شده – نمودار – Leetcode 130 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:15:12
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,000 –> 00:00:02,000
سلام به همه خوش آمدید و بیایید
2
00:00:02,000 –> 00:00:04,560
امروز یک کد دقیق تر بنویسیم، بنابراین امروز
3
00:00:04,560 –> 00:00:06,879
بیایید مشکل مناطق احاطه شده را حل کنیم،
4
00:00:06,879 –> 00:00:09,440
این یک مشکل بسیار جالب
5
00:00:09,440 –> 00:00:10,960
است و فکر می کنم شما
6
00:00:10,960 –> 00:00:13,280
واقعاً از راه حلی که امروز ارائه کرده ایم شگفت زده خواهید
7
00:00:13,280 –> 00:00:15,360
شد و من قطعاً
8
00:00:15,360 –> 00:00:17,600
فکر می کنم این مشکل ارزش وقت شما را دارد،
9
00:00:17,600 –> 00:00:20,000
اما قبل از پرداختن به آن، اجازه دهید
10
00:00:20,000 –> 00:00:22,320
کمی در مورد آموزش io به شما بگویم.
11
00:00:22,320 –> 00:00:24,640
12
00:00:24,640 –> 00:00:27,199
13
00:00:27,199 –> 00:00:29,039
14
00:00:29,039 –> 00:00:31,039
15
00:00:31,039 –> 00:00:32,800
آنها را به زبان های مختلف داشته باشید
16
00:00:32,800 –> 00:00:35,680
پایتون جاوا جاوا اسکریپت c plus
17
00:00:35,680 –> 00:00:37,920
plus و بیشتر
18
00:00:37,920 –> 00:00:40,079
اگر می خواهید اطلاعات بیشتری کسب کنید، پیوند در توضیحات را بررسی کنید، بنابراین
19
00:00:40,079 –> 00:00:42,480
اکنون اجازه دهید در این مشکل وارد
20
00:00:42,480 –> 00:00:45,440
آن شویم.
21
00:00:45,440 –> 00:00:49,440
x و o و ما
22
00:00:49,440 –> 00:00:52,640
میخواهیم تمام مناطقی را بگیریم که چهار
23
00:00:52,640 –> 00:00:55,840
جهت توسط x احاطه شدهاند و
24
00:00:55,840 –> 00:00:58,000
به هر حال دلیلی را میگیریم که
25
00:00:58,000 –> 00:00:59,520
نمیدانم میتوانید صدای پرواز را بشنوید که
26
00:00:59,520 –> 00:01:01,359
یک هواپیما وجود دارد یا خیر. e در بالا اما بیایید
27
00:01:01,359 –> 00:01:03,920
ادامه دهیم مشکل گرفتن یک
28
00:01:03,920 –> 00:01:06,560
منطقه با چرخاندن همه o ها
29
00:01:06,560 –> 00:01:08,159
به x ها تعریف می شود
30
00:01:08,159 –> 00:01:11,280
اگر و فقط اگر آن o ها
31
00:01:11,280 –> 00:01:14,479
توسط x احاطه شده باشند و این به بهترین شکل
32
00:01:14,479 –> 00:01:16,400
با یک مثال قابل درک است، بنابراین اجازه دهید
33
00:01:16,400 –> 00:01:18,479
به این تابلوی ورودی نگاهی بیندازیم.
34
00:01:18,479 –> 00:01:20,479
تابلوی ورودی است و این نتیجه است، پس
35
00:01:20,479 –> 00:01:22,560
چگونه به نتیجه برسیم خوب
36
00:01:22,560 –> 00:01:25,759
به تابلو نگاهی بیندازید، ما دو
37
00:01:25,759 –> 00:01:29,680
ناحیه مختلف سیستم عامل داریم، این یک
38
00:01:29,680 –> 00:01:31,759
منطقه است، اجازه دهید از رنگ متفاوتی استفاده کنم،
39
00:01:31,759 –> 00:01:34,479
این یک منطقه است و این یک منطقه است.
40
00:01:34,479 –> 00:01:36,720
ناحیه دوم چرا این نواحی مجزا
41
00:01:36,720 –> 00:01:38,479
هستند، آیا به صورت مورب به خوبی به
42
00:01:38,479 –> 00:01:40,640
هم متصل نیستند، بله، آنها به صورت مورب به هم متصل هستند، اما
43
00:01:40,640 –> 00:01:43,439
به یاد داشته باشید که به بالا نگاه کنید، ما فقط می خواهیم چهار
44
00:01:43,439 –> 00:01:45,280
جهت به سمت راست احاطه شوند، بنابراین
45
00:01:45,280 –> 00:01:47,280
اساساً این مناطق نمی توانند به
46
00:01:47,280 –> 00:01:49,200
صورت مورب به هم متصل شوند، آنها باید به صورت
47
00:01:49,200 –> 00:01:51,920
افقی یا عمودی مانند این
48
00:01:51,920 –> 00:01:54,079
سه مورد متصل شوند. بنابراین این دو
49
00:01:54,079 –> 00:01:56,799
منطقه جداگانه هستند در نتیجه می توانید ببینید که
50
00:01:56,799 –> 00:01:59,280
این منطقه به سمت راست برگشته است یکی از
51
00:01:59,280 –> 00:02:02,799
مناطق به سمت راست برگشته است چرا این
52
00:02:02,799 –> 00:02:05,600
منطقه برگردانده شده است زیرا به آن نگاه کنید
53
00:02:05,600 –> 00:02:07,600
احاطه شده توسط x سمت راست وجود دارد x
54
00:02:07,600 –> 00:02:12,400
اینجا x اینجا x اینجا x اینجا x اینجا x اینجا
55
00:02:12,400 –> 00:02:13,760
اوه، در واقع ما
56
00:02:13,760 –> 00:02:16,319
به این x اهمیت نمیدهیم زیرا این x مورب است،
57
00:02:16,319 –> 00:02:18,000
ما به x افقی و عمودی اهمیت میدهیم
58
00:02:18,000 –> 00:02:22,080
، بنابراین این x این x این x
59
00:02:22,080 –> 00:02:24,879
این x و من فکر می کنم این آخرین x است
60
00:02:24,879 –> 00:02:27,120
درست توسط تمام x ها احاطه شده است،
61
00:02:27,120 –> 00:02:29,360
بنابراین ما می توانیم این منطقه را
62
00:02:29,360 –> 00:02:31,200
بگیریم وقتی می گوییم گرفتن، منظور ما تبدیل
63
00:02:31,200 –> 00:02:33,760
o به x است همانطور که در خروجی می توانید ببینید
64
00:02:33,760 –> 00:02:36,319
که در مورد منطقه دوم
65
00:02:36,319 –> 00:02:39,440
چیست این ناحیه نیز توسط x احاطه شده است،
66
00:02:39,440 –> 00:02:42,319
چرا آن را در چاه خروجی چرخاندهایم،
67
00:02:42,319 –> 00:02:44,480
بیایید نگاهی بیندازیم
68
00:02:44,480 –> 00:02:46,400
این یک x در سمت چپ آن یک x
69
00:02:46,400 –> 00:02:48,640
بالای آن یک x در سمت راست آن است، اما
70
00:02:48,640 –> 00:02:52,160
در پایین هیچ x وجود ندارد، در
71
00:02:52,160 –> 00:02:56,640
سمت راست مرز است، بنابراین چون این منطقه
72
00:02:56,640 –> 00:02:59,200
به مرز متصل است، ما
73
00:02:59,200 –> 00:03:02,400
آن را به سمت راست نمیچرخانیم، بنابراین اساساً مناطقی
74
00:03:02,400 –> 00:03:04,720
که به مرز متصل نیستند، فقط مناطقی که به مرز متصل نیستند،
75
00:03:04,720 –> 00:03:07,599
برگردانده
76
00:03:07,599 –> 00:03:09,840
میشوند. مرز، پس
77
00:03:09,840 –> 00:03:11,840
چگونه می توانیم این مشکل را حل کنیم اگر
78
00:03:11,840 –> 00:03:15,120
یک dfs را روی you know t اجرا کنیم او تمام برد
79
00:03:15,120 –> 00:03:17,599
و سپس سعی کنید به نحوی بفهمید که کدام
80
00:03:17,599 –> 00:03:20,000
مناطق به مرز متصل نیستند
81
00:03:20,000 –> 00:03:22,560
و سپس آنها را به خوبی ورق بزنید که قطعاً
82
00:03:22,560 –> 00:03:24,799
امکان پذیر است، اما بسته به نحوه انجام
83
00:03:24,799 –> 00:03:26,720
آن، این یک رویکرد پیچیده است
84
00:03:26,720 –> 00:03:28,720
در واقع راه های زیادی برای حل
85
00:03:28,720 –> 00:03:30,560
این مشکل وجود دارد. یک راه
86
00:03:30,560 –> 00:03:33,360
کمی هوشمندانه و آسان برای حل
87
00:03:33,360 –> 00:03:34,560
این مشکل به شما نشان خواهم داد، اما فکر میکنم شما
88
00:03:34,560 –> 00:03:36,319
واقعاً میتوانید از نوع
89
00:03:36,319 –> 00:03:38,400
راهحلی که به شما نشان میدهم چیزهای زیادی بیاموزید،
90
00:03:38,400 –> 00:03:41,040
این به معکوس کردن طرز فکر شما
91
00:03:41,040 –> 00:03:43,519
در مورد مشکل مربوط میشود. برخی از مردم
92
00:03:43,519 –> 00:03:46,000
دوست دارند تفکر معکوس را نام ببرند، بنابراین بیایید
93
00:03:46,000 –> 00:03:48,239
همین حالا به آن راه حل
94
00:03:48,239 –> 00:03:50,159
بپردازیم، بنابراین در بالا می توانید مثالی را ببینید که ما در حال
95
00:03:50,159 –> 00:03:51,840
تلاش برای حل این مشکل کلی
96
00:03:51,840 –> 00:03:53,439
هستیم که می خواهیم حلش کنیم، اما قبل از اینکه
97
00:03:53,439 –> 00:03:55,360
وارد آن شویم، اجازه دهید من فقط لطف کنم از
98
00:03:55,360 –> 00:03:58,400
شما یک سوال ساده بپرسم، فرض کنید من یک
99
00:03:58,400 –> 00:04:00,959
تکه کاغذ مثل این داشتم، بیایید بگوییم من
100
00:04:00,959 –> 00:04:03,439
آن را به این شکل برش دادم، من یک
101
00:04:03,439 –> 00:04:06,159
منطقه کوچک در اینجا دارم به نام این
102
00:04:06,159 –> 00:04:08,319
قسمتی از کاغذ است و من یک بخش دیگر دارم
103
00:04:08,319 –> 00:04:10,959
این بخش b از
104
00:04:10,959 –> 00:04:15,120
کاغذ فرض کنید من می خواهم فقط این
105
00:04:15,120 –> 00:04:17,120
قسمت را نگه دارم من فقط می خواهم
106
00:04:17,120 –> 00:04:19,839
بخشی از کاغذ را نگه دارم، بنابراین چگونه می توانم
107
00:04:19,839 –> 00:04:21,440
بخشی از کاغذ را خوب بخواهم
108
00:04:21,440 –> 00:04:25,600
می توانم بگویم فقط یک قسمت از کاغذ را به من حق بده
109
00:04:25,600 –> 00:04:28,000
این راه سادهتر
110
00:04:28,000 –> 00:04:29,759
برای صحبت کردن در مورد آن است، اما یک
111
00:04:29,759 –> 00:04:31,680
راه پیچیدهتر و بیفایدهتر برای
112
00:04:31,680 –> 00:04:33,759
صحبت کردن در مورد آن به زبان انگلیسی حداقل این
113
00:04:33,759 –> 00:04:37,120
است که بگوییم همه چیز را در مقاله به من بده
114
00:04:37,120 –> 00:04:40,320
، به جز درست بودن، تمام این مقاله را به من بده
115
00:04:40,320 –> 00:04:43,600
به جز ب. درست
116
00:04:43,600 –> 00:04:45,919
فقط b را خط بزنید فقط همه چیز را به من بدهید
117
00:04:45,919 –> 00:04:48,080
به جز b چرا می گویید وقتی
118
00:04:48,080 –> 00:04:50,240
می توانید بگویید فقط به من حق بدهید
119
00:04:50,240 –> 00:04:52,240
البته این روش ساده گفتن آن است
120
00:04:52,240 –> 00:04:54,479
اما گاهی اوقات این طرز
121
00:04:54,479 –> 00:04:56,960
تفکر معکوس می تواند به خصوص در
122
00:04:56,960 –> 00:04:58,720
برنامه نویسی مفید باشد. مطمئنم شما بچه ها قبلاً
123
00:04:58,720 –> 00:05:01,759
تجربه ای در این مورد داشته اید، بنابراین چگونه
124
00:05:01,759 –> 00:05:04,560
این موضوع در این مشکل مفید خواهد بود،
125
00:05:04,560 –> 00:05:07,919
اجازه دهید در مورد مشکلی که به
126
00:05:07,919 –> 00:05:09,840
ما گفتند برای گرفتن عکس،
127
00:05:09,840 –> 00:05:12,720
آنها به ما گفتند که مناطق اطراف
128
00:05:12,720 –> 00:05:16,320
را فقط فقط مناطق اطراف را بگیریم توضیح
129
00:05:16,320 –> 00:05:18,880
دهم. فقط این منطقه
130
00:05:18,880 –> 00:05:21,039
که به روش دیگری احاطه شده است،
131
00:05:21,039 –> 00:05:23,759
روش مخالف این است که بگوییم
132
00:05:23,759 –> 00:05:27,840
همه چیز است به جز
133
00:05:27,840 –> 00:05:30,720
مناطق غیرمحاصره درست است، من اساساً
134
00:05:30,720 –> 00:05:33,280
نقطه گلوله اول را با یک جمله طولانی تر به
135
00:05:33,280 –> 00:05:35,280
سمت راست دوباره توضیح دادم همه چیز را در
136
00:05:35,280 –> 00:05:38,240
این تخته ثبت کنید به جز مناطق غیرمحاصره
137
00:05:38,240 –> 00:05:39,919
، مناطقی که
138
00:05:39,919 –> 00:05:42,080
در مناطق دیگر احاطه نشده اند. کلمات
139
00:05:42,080 –> 00:05:45,280
کل صفحه را به جز این منطقه می گیرند
140
00:05:45,280 –> 00:05:47,759
زیرا این منطقه احاطه نشده است
141
00:05:47,759 –> 00:05:50,080
چگونه می دانیم که این منطقه
142
00:05:50,080 –> 00:05:51,919
احاطه نشده است آیا یک راه آسان برای
143
00:05:51,919 –> 00:05:54,800
فهمیدن وجود دارد که بله بسیار آسان است
144
00:05:54,800 –> 00:05:57,600
زیرا این منطقه به
145
00:05:57,600 –> 00:06:01,440
مرز هر منطقه ای در ارتباط است تخته ای
146
00:06:01,440 –> 00:06:02,960
که به مرز متصل است،
147
00:06:02,960 –> 00:06:05,600
برخی از اوها در اینجا وجود دارد، برخی از آنها
148
00:06:05,600 –> 00:06:08,880
اینجا یا در اینجا پایین، ما آنها را نمی گیریم،
149
00:06:08,880 –> 00:06:11,039
بنابراین اینجاست که
150
00:06:11,039 –> 00:06:12,560
همه چیز کمی هوشمندانه می شود، من
151
00:06:12,560 –> 00:06:14,160
انتظار ندارم که اکثر مردم چنین باشند. قادر
152
00:06:14,160 –> 00:06:15,840
به تشخیص این بخش به خصوص
153
00:06:15,840 –> 00:06:17,680
154
00:06:17,680 –> 00:06:20,160
155
00:06:20,160 –> 00:06:22,000
مبتدیان هستیم یک
156
00:06:22,000 –> 00:06:24,720
اسکن از طریق هر سلول مرزی درست
157
00:06:24,720 –> 00:06:26,720
همه چیز در خارج، ما به
158
00:06:26,720 –> 00:06:30,240
دنبال هر سیستم عاملی میگردیم که یکی o را در
159
00:06:30,240 –> 00:06:32,720
اینجا پیدا کردهایم، بنابراین منطقهای را پیدا کردیم که کاملاً احاطه نشده است،
160
00:06:32,720 –> 00:06:34,639
مطمئناً میدانیم که این
161
00:06:34,639 –> 00:06:36,400
منطقه احاطه نشده است زیرا
162
00:06:36,400 –> 00:06:37,919
اکنون به مرز متصل است. ما
163
00:06:37,919 –> 00:06:40,400
یک dfs را
164
00:06:40,400 –> 00:06:44,080
روی این منطقه اجرا می کنیم زیرا
165
00:06:44,080 –> 00:06:46,240
نمی خواهیم آن را ضبط کنیم.
166
00:06:46,240 –> 00:06:48,800
167
00:06:48,800 –> 00:06:51,360
168
00:06:51,360 –> 00:06:54,639
o در t’s است بنابراین من
169
00:06:54,639 –> 00:06:59,120
می خواهم این o را به t تغییر دهم
170
00:06:59,120 –> 00:07:01,599
این o به هیچ چیز درستی متصل
171
00:07:01,599 –> 00:07:02,639
نیست، ممکن است
172
00:07:02,639 –> 00:07:04,319
امکان پذیر باشد و شاید O دیگری
173
00:07:04,319 –> 00:07:06,800
در اینجا وجود داشته باشد و به نوعی این
174
00:07:06,800 –> 00:07:08,720
منطقه را تشکیل می دهد که به آن متصل است. لبه
175
00:07:08,720 –> 00:07:10,080
سمت راست و سپس همه
176
00:07:10,080 –> 00:07:13,599
آنها را به ts نیز تغییر میدهیم،
177
00:07:13,599 –> 00:07:15,520
اما در این مورد فقط یک منطقه با
178
00:07:15,520 –> 00:07:18,000
اندازه یک است، بنابراین این تنها کاری است که اکنون انجام میدهیم چرا
179
00:07:18,000 –> 00:07:20,560
آن را به یک متغیر موقت تغییر میدهیم
180
00:07:20,560 –> 00:07:22,880
زیرا به یاد داشته باشید که ما سعی میکنیم
181
00:07:22,880 –> 00:07:25,440
همه چیز را ضبط کنیم. به جز reg unsrounded
182
00:07:25,440 –> 00:07:28,560
بنابراین اکنون ما این را به عنوان یک
183
00:07:28,560 –> 00:07:31,199
منطقه بدون احاطه علامت گذاری کردیم، بنابراین اکنون باید
184
00:07:31,199 –> 00:07:33,360
چه کار کنیم، این تخته را داریم،
185
00:07:33,360 –> 00:07:35,919
فقط یک حلقه تودرتو دوتایی را
186
00:07:35,919 –> 00:07:39,520
در هر ردیف در این
187
00:07:39,520 –> 00:07:40,319
188
00:07:40,319 –> 00:07:43,360
شبکه ورودی UH انجام می دهیم و هر زمان که یک o را مشاهده کنیم
189
00:07:43,360 –> 00:07:44,400
مقدار
190
00:07:44,400 –> 00:07:46,560
آن را به x تبدیل می کنیم
191
00:07:46,560 –> 00:07:48,560
زیرا اکنون با اطمینان می دانیم که
192
00:07:48,560 –> 00:07:52,160
هر زمان که یک o را می بینیم قطعاً بخشی
193
00:07:52,160 –> 00:07:55,039
از یک منطقه احاطه شده است زیرا هر
194
00:07:55,039 –> 00:07:57,280
منطقه ای که احاطه نشده بود
195
00:07:57,280 –> 00:08:00,639
قبلاً آنها را به t تغییر داده ایم بنابراین هر زمان
196
00:08:00,639