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