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