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