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