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