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