-
Notifications
You must be signed in to change notification settings - Fork 2
/
index.html
606 lines (582 loc) · 60.7 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
<!DOCTYPE html><html lang="en" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>Double Pointer and Binary Search Algorithm | 一直进步 做喜欢的</title><meta name="keywords" content="Data Structures and Algorithms,LeetCode"><meta name="author" content="贪钱算法还我头发"><meta name="copyright" content="贪钱算法还我头发"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="算法——双指针、滑动窗口、二分查找">
<meta property="og:type" content="article">
<meta property="og:title" content="Double Pointer and Binary Search Algorithm">
<meta property="og:url" content="https://xfliu1998.github.io/2023/03/19/Double-Pointer-and-Binary-Search-Algorithm/index.html">
<meta property="og:site_name" content="一直进步 做喜欢的">
<meta property="og:description" content="算法——双指针、滑动窗口、二分查找">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://www.wds58.com/uploads/allimg/160906/1_160906192000_1.jpg">
<meta property="article:published_time" content="2023-03-19T04:00:00.000Z">
<meta property="article:modified_time" content="2023-12-02T14:03:38.158Z">
<meta property="article:author" content="贪钱算法还我头发">
<meta property="article:tag" content="Data Structures and Algorithms">
<meta property="article:tag" content="LeetCode">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://www.wds58.com/uploads/allimg/160906/1_160906192000_1.jpg"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="https://xfliu1998.github.io/2023/03/19/Double-Pointer-and-Binary-Search-Algorithm/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: {"path":"search.xml","languages":{"hits_empty":"We didn't find any results for the search: ${query}"}},
translate: undefined,
noticeOutdate: undefined,
highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
copy: {
success: 'Copy successfully',
error: 'Copy error',
noSupport: 'The browser does not support'
},
relativeDate: {
homepage: false,
post: false
},
runtime: 'days',
date_suffix: {
just: 'Just',
min: 'minutes ago',
hour: 'hours ago',
day: 'days ago',
month: 'months ago'
},
copyright: undefined,
lightbox: 'fancybox',
Snackbar: undefined,
source: {
jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
justifiedGallery: {
js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
},
fancybox: {
js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
}
},
isPhotoFigcaption: false,
islazyload: false,
isanchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: 'Double Pointer and Binary Search Algorithm',
isPost: true,
isHome: false,
isHighlightShrink: false,
isToc: true,
postUpdate: '2023-12-02 22:03:38'
}</script><noscript><style type="text/css">
#nav {
opacity: 1
}
.justified-gallery img {
opacity: 1
}
#recent-posts time,
#post-meta time {
display: inline !important
}
</style></noscript><script>(win=>{
win.saveToLocal = {
set: function setWithExpiry(key, value, ttl) {
if (ttl === 0) return
const now = new Date()
const expiryDay = ttl * 86400000
const item = {
value: value,
expiry: now.getTime() + expiryDay,
}
localStorage.setItem(key, JSON.stringify(item))
},
get: function getWithExpiry(key) {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = new Date()
if (now.getTime() > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = url => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
document.head.appendChild(script)
})
win.activateDarkMode = function () {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = function () {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if (GLOBAL_CONFIG_SITE.isHome && /iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/StaticFile_HEXO@latest/butterfly/css/pool.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/StaticFile_HEXO@latest/butterfly/css/iconfont.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/StaticFile_HEXO@latest/butterfly/js/pool.min.js"><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/HexoStaticFile@latest/Hexo/js/mouse_snow.min.js"><link rel="stylesheet" href="/css/custom.css?v1"><link rel="stylesheet" href="//at.alicdn.com/t/font_2264842_b004iy0kk2b.css" media="defer" onload="this.media='all'"><!-- hexo injector head_end start --><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiperstyle.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-filter-gitcalendar/lib/gitcalendar.css" media="print" onload="this.media='all'"><!-- hexo injector head_end end --><meta name="generator" content="Hexo 5.4.0"></head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="/images/head.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">Articles</div><div class="length-num">47</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">Tags</div><div class="length-num">13</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">Categories</div><div class="length-num">6</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> Home</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> Tags</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> Categories</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://www.wds58.com/uploads/allimg/160906/1_160906192000_1.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">一直进步 做喜欢的</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> Search</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> Home</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> Tags</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> Categories</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">Double Pointer and Binary Search Algorithm</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">Created</span><time class="post-meta-date-created" datetime="2023-03-19T04:00:00.000Z" title="Created 2023-03-19 12:00:00">2023-03-19</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">Updated</span><time class="post-meta-date-updated" datetime="2023-12-02T14:03:38.158Z" title="Updated 2023-12-02 22:03:38">2023-12-02</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/Data-Structures-and-Algorithms/">Data Structures and Algorithms</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">Word count:</span><span class="word-count">2.3k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">Reading time:</span><span>7min</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="Double Pointer and Binary Search Algorithm"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">Post View:</span><span id="busuanzi_value_page_pv"></span></span><span class="post-meta-separator">|</span><span class="post-meta-commentcount"><i class="far fa-comments fa-fw post-meta-icon"></i><span class="post-meta-label">Comments:</span><a href="/2023/03/19/Double-Pointer-and-Binary-Search-Algorithm/#post-comment"><span class="gitalk-comment-count"></span></a></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="双指针"><a href="#双指针" class="headerlink" title="双指针"></a>双指针</h1><ul>
<li><strong>基本思想</strong>:使用两个指针分别指向数组或链表的头部、尾部或中间位置,并移动指针,解决问题。</li>
<li><strong>类型</strong>:<ul>
<li>快慢指针:快指针每次移动两个元素,慢指针每次移动一个元素,快慢指针常用于链表的中间节点查找、链表是否有环等问题。</li>
<li>左右指针:左指针从数组或链表的左侧开始移动,右指针从数组或链表的右侧开始移动,左右指针通常用于解决数组或链表中的查找、排序等问题。</li>
<li>滑动窗口</li>
</ul>
</li>
<li><strong>复杂度</strong>:时间复杂度通常为$O(n)$,空间复杂度为$O(1)$。</li>
<li><strong>应用场景</strong>:数组或链表中元素的查找、排序、去重、合并、分割等问题。常见的问题有两数之和、三数之和、反转链表等。</li>
<li><strong>注意</strong>:注意指针的初始位置、指针移动的条件和方向、循环退出的条件等。</li>
</ul>
<h2 id="快慢指针"><a href="#快慢指针" class="headerlink" title="快慢指针"></a>快慢指针</h2><p>主要解决链表中的问题。<br>快慢指针⼀般都初始化指向链表的头结点 head,前进时快指针 fast 每次走2步在前,慢指针 slow 每次走1步在后。</p>
<h3 id="力扣指南"><a href="#力扣指南" class="headerlink" title="力扣指南"></a>力扣指南</h3><table>
<tr>
<th align='center', colspan="3">双指针——快慢指针</th>
</tr>
<tr>
<th>题目</th>
<th>技巧</th>
<th>难度</th>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description>✅19. 删除链表的倒数第 N 个结点</td>
<td>寻找链表倒数第k元素:fast先走k步,fast到尾部是slow的位置;需在初始化slow时添加一个首结点,否则删除的是倒数第n-1个结点</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/rotate-list/description>✅61. 旋转链表</td>
<td>fast先走k步找到倒数第k结点</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/linked-list-cycle/submissions/413647419>✅141. 环形链表</td>
<td></td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/linked-list-cycle-ii/description>✅142. 环形链表 II</td>
<td>已知链表有环,返回环的起始位置:相遇时slow返回head,再相遇时为环起点</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/intersection-of-two-linked-lists/description>✅160. 相交链表</td>
<td>互相走一遍,再相遇时为交点</td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/middle-of-the-linked-list>✅876. 链表的中间结点</td>
<td></td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/description>✅2095. 删除链表的中间节点</td>
<td></td>
<td>🌟🌟</td>
</tr>
</table>
<h2 id="左右指针"><a href="#左右指针" class="headerlink" title="左右指针"></a>左右指针</h2><p>主要解决数组或字符串的问题。二分查找也是典型的左右指针问题。<br>左右指针实际是两个索引值,一般初始化<code>left, right = 0, len(nums) - 1</code></p>
<h3 id="力扣指南-1"><a href="#力扣指南-1" class="headerlink" title="力扣指南"></a>力扣指南</h3><table>
<tr>
<th align='center', colspan="3">双指针——左右指针</th>
</tr>
<tr>
<th>题目</th>
<th>技巧</th>
<th>难度</th>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/longest-palindromic-substring/description>✅5. 最长回文子串</td>
<td>中心扩展法,向两边移动指针判断是否为回文</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/container-with-most-water/description>✅11. 盛最多水的容器</td>
<td>典型的左右指针</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description>✅26. 删除有序数组中的重复项</td>
<td></td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/remove-element/description>✅27. 移除元素</td>
<td></td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/trapping-rain-water>✅42. 接雨水</td>
<td>雨水=min(l, r) - height[i]</td>
<td>🌟🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/sort-colors/description>✅75. 颜色分类</td>
<td>除了左右指针还需要中间变量帮助遍历数组</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description>✅82. 删除排序链表中的重复元素 II</td>
<td>左右指针</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/partition-list/description>✅86. 分隔链表</td>
<td>注意要将链表最后的指针指向None</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/move-zeroes/description>✅283. 移动零</td>
<td></td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/reverse-string/description>✅344. 反转字符串</td>
<td></td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/trapping-rain-water-ii>❌407. 接雨水 II</td>
<td></td>
<td>🌟🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/3sum/description>✅15. 三数之和</td>
<td></td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/4sum/description>✅18. 四数之和</td>
<td></td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/advantage-shuffle/description>✅870. 优势洗牌</td>
<td>田忌赛马</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/is-subsequence/description>✅392. 判断子序列</td>
<td></td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/3sum-closest/description>✅16. 最接近的三数之和
</td>
<td>同三数之和</td>
<td>🌟🌟</td>
</tr>
</table>
<h2 id="滑动窗口"><a href="#滑动窗口" class="headerlink" title="滑动窗口"></a>滑动窗口</h2><p>滑动窗口算法是一种基于双指针的算法,通常用于解决字符串和数组相关的问题。其基本思想是维护一个固定大小的窗口,通过移动窗口的左右边界来寻找目标值。</p>
<ul>
<li>窗口的大小:窗口的大小通常是固定的,可以根据问题要求进行调整。</li>
<li>窗口的移动:窗口的移动是通过移动左右指针来实现的。左指针通常指向窗口的起始位置,右指针指向窗口的结束位置。</li>
<li>窗口的维护:在移动窗口的过程中,需要维护窗口中的元素,可以使用哈希表或者数组等数据结构来维护。</li>
<li>窗口的更新:在窗口移动的过程中,需要更新窗口内的元素以及相关的数据结构。</li>
<li>窗口的判断:在滑动窗口算法中,需要判断当前窗口是否满足题目要求,如果满足则更新结果,如果不满足则继续移动窗口。</li>
<li>应用场景:滑动窗口算法通常用于求解最长子串、最短子串、子数组等问题。</li>
</ul>
<p><strong>时间复杂度</strong>:$O(N)$。虽然滑动窗口代码框架中有一个嵌套的 while 循环,但字符串/数组中的每个元素都只会进入窗口一次,然后被移出窗口一次,不会有某些元素多次进入和离开窗口,所以算法的时间复杂度就和字符串/数组的长度成正比。</p>
<h3 id="算法框架"><a href="#算法框架" class="headerlink" title="算法框架"></a>算法框架</h3><p>初始化<code>left = right = 0</code>,把索引左闭右开区间<code>[left, right)</code>称为一个「窗口」,左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">slidingWindow</span>(<span class="params">s: <span class="built_in">str</span></span>):</span></span><br><span class="line"> window = {}</span><br><span class="line"> left, right = <span class="number">0</span>, <span class="number">0</span></span><br><span class="line"> <span class="keyword">while</span> right < <span class="built_in">len</span>(s):</span><br><span class="line"> <span class="comment"># c 是将移入窗口的字符</span></span><br><span class="line"> c = s[right]</span><br><span class="line"> <span class="comment"># 增大窗口</span></span><br><span class="line"> right += <span class="number">1</span></span><br><span class="line"> <span class="comment"># 进行窗口内数据的一系列更新</span></span><br><span class="line"> ...</span><br><span class="line"></span><br><span class="line"> <span class="comment"># debug 输出的位置</span></span><br><span class="line"> <span class="comment"># 注意在最终的解法代码中不要 print</span></span><br><span class="line"> <span class="comment"># 因为 IO 操作很耗时,可能导致超时</span></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">"window: [{}, {})"</span>.<span class="built_in">format</span>(left, right))</span><br><span class="line"> </span><br><span class="line"> <span class="comment"># 判断左侧窗口是否要收缩</span></span><br><span class="line"> <span class="keyword">while</span> window needs shrink:</span><br><span class="line"> <span class="comment"># d 是将移出窗口的字符</span></span><br><span class="line"> d = s[left]</span><br><span class="line"> <span class="comment"># 缩小窗口</span></span><br><span class="line"> left += <span class="number">1</span></span><br><span class="line"> <span class="comment"># 进行窗口内数据的一系列更新</span></span><br><span class="line"> ...</span><br></pre></td></tr></table></figure>
<h3 id="力扣指南-2"><a href="#力扣指南-2" class="headerlink" title="力扣指南"></a>力扣指南</h3><table>
<tr>
<th align='center', colspan="3">双指针——滑动窗口</th>
</tr>
<tr>
<th>题目</th>
<th>技巧</th>
<th>难度</th>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/longest-substring-without-repeating-characters/description>✅3. 无重复字符的最长子串</td>
<td>没啥好说的,直接AC</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/minimum-window-substring/description>✅76. 最小覆盖子串</td>
<td>需要用字典defaultdict(int)记录</td>
<td>🌟🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/repeated-dna-sequences/description>❌187. 重复的DNA序列</td>
<td>需要位运算,到时候在做一遍</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/minimum-size-subarray-sum/description>✅209. 长度最小的子数组</td>
<td>没啥好说的,直接AC</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/contains-duplicate-ii/description>✅219. 存在重复元素 II</td>
<td>固定一个k大小的窗口</td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/contains-duplicate-iii>❌220. 存在重复元素 III</td>
<td>需要使用有序集合</td>
<td>🌟🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/sliding-window-maximum>❌239. 滑动窗口最大值</td>
<td>仍然需要借助特殊数据结构</td>
<td>🌟🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/find-all-anagrams-in-a-string/description>✅438. 找到字符串中所有字母异位词</td>
<td>注意缩小窗口时更新valid方式</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/permutation-in-string/description>✅567. 字符串的排列</td>
<td>前面几个会了这个闭眼写</td>
<td>🌟🌟</td>
</tr>
</table>
<h1 id="二分查找"><a href="#二分查找" class="headerlink" title="二分查找"></a>二分查找</h1><ul>
<li><strong>简介</strong>:二分查找也叫折半查找,是一种在有序数组中查找目标元素的算法。该算法每次查找时将目标值与数组中间位置的元素进行比较,如果目标值小于中间元素,则在左半部分继续查找;如果目标值大于中间元素,则在右半部分继续查找;如果目标值等于中间元素,则直接返回中间位置的元素下标。通过不断地将查找范围缩小一半,最终找到目标元素或者确认目标元素不存在于数组中。</li>
<li><strong>时间复杂度</strong>:$O(logn)$,其中n表示数组的长度。因为每次查找可以将查找范围缩小一半,所以最多需要查找logn次。</li>
<li><strong>前提条件</strong>:数组必须是有序的。因为二分查找是通过比较目标元素和数组中间位置的元素来确定查找范围的,如果数组是无序的,那么就无法保证每次缩小查找范围。</li>
<li><strong>局限性</strong>:只能用于查找有序数组中的元素。如果数据不是有序的,需要先进行排序,时间复杂度会变为O(nlogn);另外,二分查找也无法处理数组中存在重复元素的情况,需要使用变体来处理。</li>
</ul>
<h3 id="题目模版"><a href="#题目模版" class="headerlink" title="题目模版"></a>题目模版</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">binary_search</span>(<span class="params">nums, target</span>):</span></span><br><span class="line"> left, right = <span class="number">0</span>, <span class="built_in">len</span>(nums) - <span class="number">1</span></span><br><span class="line"> <span class="keyword">while</span> left <= right:</span><br><span class="line"> mid = left + (right - left) // <span class="number">2</span> <span class="comment"># 防止left+right太大导致溢出,python中不会有这个问题</span></span><br><span class="line"> <span class="keyword">if</span> nums[mid] < target:</span><br><span class="line"> left = mid + <span class="number">1</span></span><br><span class="line"> <span class="keyword">elif</span> nums[mid] > target:</span><br><span class="line"> right = mid - <span class="number">1</span></span><br><span class="line"> <span class="keyword">elif</span> nums[mid] == target:</span><br><span class="line"> <span class="keyword">return</span> mid <span class="comment"># 直接返回索引</span></span><br><span class="line"> <span class="comment"># left = mid + 1 # 如果寻找target的索引右边界,缩小左边界</span></span><br><span class="line"> <span class="comment"># right = mid - 1 # 如果寻找target的索引左边界,缩小右边界</span></span><br><span class="line"> <span class="keyword">return</span> -<span class="number">1</span></span><br><span class="line"> <span class="comment"># # 如果寻找target的索引右边界,判断右边界是否越界</span></span><br><span class="line"> <span class="comment"># if right < 0 or nums[right] != target:</span></span><br><span class="line"> <span class="comment"># return -1</span></span><br><span class="line"> <span class="comment"># # 如果寻找target的索引左边界,判断左边界是否越界</span></span><br><span class="line"> <span class="comment"># if left >= len(nums) or nums[left] != target:</span></span><br><span class="line"> <span class="comment"># return -1</span></span><br></pre></td></tr></table></figure>
<h3 id="力扣指南-3"><a href="#力扣指南-3" class="headerlink" title="力扣指南"></a>力扣指南</h3><table>
<tr>
<th align='center', colspan="3">二分查找</th>
</tr>
<tr>
<th>题目</th>
<th>技巧</th>
<th>难度</th>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/median-of-two-sorted-arrays/description>❌4. 寻找两个正序数组的中位数</td>
<td></td>
<td>🌟🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/search-in-rotated-sorted-array/description>✅33. 搜索旋转排序数组</td>
<td>判断哪部分有序再二分</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array>✅34. 在排序数组中查找元素的第一个和最后一个位置</td>
<td>两次二分查找左右边界</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/search-insert-position/description>✅35. 搜索插入位置</td>
<td>典型二分</td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/sqrtx/description>✅69. x 的平方根</td>
<td>注意判断返回边界</td>
<td>🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/search-a-2d-matrix/description>✅74. 搜索二维矩阵</td>
<td>二维转换为一维进行二分</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/description>✅81. 搜索旋转排序数组 II</td>
<td>多处理一步:缩小相等边界</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description>✅153. 寻找旋转排序数组中的最小值</td>
<td>注意处理边界</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description>✅154. 寻找旋转排序数组中的最小值 II</td>
<td>多处理一步:缩小相等边界</td>
<td>🌟🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/find-peak-element/description>✅162. 寻找峰值</td>
<td>假设nums[n]=-inf</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/search-a-2d-matrix-ii/description>✅240. 搜索二维矩阵 II</td>
<td>矩阵以右上角为起点为二叉搜索树,z字查找</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description>✅1167. 两数之和 II - 输入有序数组</td>
<td>求和问题都可以转换为二分查找target-其中一个数</td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/koko-eating-bananas/description>✅875. 爱吃香蕉的珂珂
</td>
<td></td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description>✅1011. 在 D 天内送达包裹的能力</td>
<td></td>
<td>🌟🌟</td>
</tr>
<tr>
<td><a href=https://leetcode.cn/problems/number-of-matching-subsequences/description>✅792. 匹配子序列的单词数
</td>
<td></td>
<td>🌟🌟</td>
</tr>
</table></article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">Author: </span><span class="post-copyright-info"><a href="mailto:undefined">贪钱算法还我头发</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">Link: </span><span class="post-copyright-info"><a href="https://xfliu1998.github.io/2023/03/19/Double-Pointer-and-Binary-Search-Algorithm/">https://xfliu1998.github.io/2023/03/19/Double-Pointer-and-Binary-Search-Algorithm/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">Copyright Notice: </span><span class="post-copyright-info">All articles in this blog are licensed under <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a> unless stating additionally.</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/Data-Structures-and-Algorithms/">Data Structures and Algorithms</a><a class="post-meta__tags" href="/tags/LeetCode/">LeetCode</a></div><div class="post_share"><div class="social-share" data-image="https://www.wds58.com/uploads/allimg/160906/1_160906192000_1.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2023/03/22/Prefix-Sum-and-Difference-Array/"><img class="prev-cover" src="https://img.imgdb.cn/item/603dd999360785be542209fd.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">Previous Post</div><div class="prev_info">Prefix Sum and Difference Array</div></div></a></div><div class="next-post pull-right"><a href="/2023/02/07/Stack-Queue-and-Heap/"><img class="next-cover" src="http:https://img.shijue.me/646eeea03d174f84b44db6b100e6b45c_d.jpg!dp6" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">Next Post</div><div class="next_info">Stack, Queue and Heap</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>Related Articles</span></div><div class="relatedPosts-list"><div><a href="/2023/07/05/Number-Theory-and-Geometry/" title="Number Theory and Geometry"><img class="cover" src="http:https://img.shijue.me/d9a0b9ce22d44e6f9213e5ef8917385d_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-07-05</div><div class="title">Number Theory and Geometry</div></div></a></div><div><a href="/2023/06/13/Sort-Algorithm/" title="Sort Algorithm"><img class="cover" src="http:https://img.shijue.me/05adac4bd8b1447697e1053623e74d68_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-06-13</div><div class="title">Sort Algorithm</div></div></a></div><div><a href="/2023/06/04/Graph-Theory/" title="Graph Theory"><img class="cover" src="http:https://img.shijue.me/845aa0476235409e9ef646afb7c05ab7_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-06-04</div><div class="title">Graph Theory</div></div></a></div><div><a href="/2023/05/29/Divide-and-Conquer/" title="Divide and Conquer"><img class="cover" src="http:https://img.shijue.me/d5e5c8cc7dae431386f1d15c0006f217.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-05-29</div><div class="title">Divide and Conquer</div></div></a></div><div><a href="/2023/05/21/Greedy-Algorithm/" title="Greedy Algorithm"><img class="cover" src="http:https://img.shijue.me/73abae19e7ed4f279380e078361cafff_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-05-21</div><div class="title">Greedy Algorithm</div></div></a></div><div><a href="/2023/04/19/Dynamic-Programming/" title="Dynamic Programming"><img class="cover" src="http:https://img.shijue.me/eb9640e472e540b4bce2f24b9f11237d_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-04-19</div><div class="title">Dynamic Programming</div></div></a></div></div></div><hr/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i><span> Comment</span></div></div><div class="comment-wrap"><div><div id="gitalk-container"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="/images/head.jpg" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">贪钱算法还我头发</div><div class="author-info__description"></div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/archives/"><div class="headline">Articles</div><div class="length-num">47</div></a></div><div class="card-info-data-item is-center"><a href="/tags/"><div class="headline">Tags</div><div class="length-num">13</div></a></div><div class="card-info-data-item is-center"><a href="/categories/"><div class="headline">Categories</div><div class="length-num">6</div></a></div></div><a class="button--animated" id="card-info-btn" target="_blank" rel="noopener" href="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/xfliu1998"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="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/xfliu1998" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="mailto:[email protected]" target="_blank" title="Email"><i class="fas fa-envelope"></i></a><a class="social-icon" href="https://blog.csdn.net/keiven_" target="_blank" title="CSDN"><i class="fa fa-address-card"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>Announcement</span></div><div class="announcement_content">欢迎来这里掉头发</div></div><div class="card-widget" id="newYear"><div class="item-headline"><i></i><span></span></div><div class="item-content"><div id="newYear-main"><div class="mask"></div> <p class="title"></p> <div class="newYear-time"></div> <p class="today" style="text-align: right;"></p> </div></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>Catalog</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%8F%8C%E6%8C%87%E9%92%88"><span class="toc-number">1.</span> <span class="toc-text">双指针</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BF%AB%E6%85%A2%E6%8C%87%E9%92%88"><span class="toc-number">1.1.</span> <span class="toc-text">快慢指针</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8A%9B%E6%89%A3%E6%8C%87%E5%8D%97"><span class="toc-number">1.1.1.</span> <span class="toc-text">力扣指南</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%B7%A6%E5%8F%B3%E6%8C%87%E9%92%88"><span class="toc-number">1.2.</span> <span class="toc-text">左右指针</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8A%9B%E6%89%A3%E6%8C%87%E5%8D%97-1"><span class="toc-number">1.2.1.</span> <span class="toc-text">力扣指南</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3"><span class="toc-number">1.3.</span> <span class="toc-text">滑动窗口</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%A1%86%E6%9E%B6"><span class="toc-number">1.3.1.</span> <span class="toc-text">算法框架</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8A%9B%E6%89%A3%E6%8C%87%E5%8D%97-2"><span class="toc-number">1.3.2.</span> <span class="toc-text">力扣指南</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE"><span class="toc-number">2.</span> <span class="toc-text">二分查找</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE%E6%A8%A1%E7%89%88"><span class="toc-number">2.0.1.</span> <span class="toc-text">题目模版</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8A%9B%E6%89%A3%E6%8C%87%E5%8D%97-3"><span class="toc-number">2.0.2.</span> <span class="toc-text">力扣指南</span></a></li></ol></li></ol></li></ol></div></div></div></div></main><footer id="footer" style="background-image: url('https://www.wds58.com/uploads/allimg/160906/1_160906192000_1.jpg')"><div id="footer-wrap"><div class="copyright">©2020 - 2024 <i id="heartbeat" class="fa fas fa-heartbeat"></i> 贪钱算法还我头发</div><div class="framework-info"><span>Framework </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>Theme </span><a target="_blank" rel="noopener" href="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/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div><head><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/HCLonely/images@master/others/heartbeat.min.css"></head></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="Read Mode"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="Switch Between Light And Dark Mode"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="Toggle between single-column and double-column"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="Setting"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="Table Of Contents"><i class="fas fa-list-ul"></i></button><a id="to_comment" href="#post-comment" title="Scroll To Comments"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="Back To Top"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><div class="search-dialog__title" id="local-search-title">Local search</div><div id="local-input-panel"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="Search for Posts" type="text"/></div></div></div><hr/><div id="local-search-results"></div><span class="search-close-button"><i class="fas fa-times"></i></span></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/search/local-search.js"></script><div class="js-pjax"><script>if (!window.MathJax) {
window.MathJax = {
tex: {
inlineMath: [ ['$','$'], ["\\(","\\)"]],
tags: 'ams'
},
chtml: {
scale: 1.2
},
options: {
renderActions: {
findScript: [10, doc => {
for (const node of document.querySelectorAll('script[type^="math/tex"]')) {
const display = !!node.type.match(/; *mode=display/)
const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display)
const text = document.createTextNode('')
node.parentNode.replaceChild(text, node)
math.start = {node: text, delim: '', n: 0}
math.end = {node: text, delim: '', n: 0}
doc.math.push(math)
}
}, ''],
insertScript: [200, () => {
document.querySelectorAll('mjx-container:not\([display]\)').forEach(node => {
const target = node.parentNode
if (target.nodeName.toLowerCase() === 'li') {
target.parentNode.classList.add('has-jax')
} else {
target.classList.add('has-jax')
}
});
}, '', false]
}
}
}
const script = document.createElement('script')
script.src = 'https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js'
script.id = 'MathJax-script'
script.async = true
document.head.appendChild(script)
} else {
MathJax.startup.document.state(0)
MathJax.texReset()
MathJax.typeset()
}</script><script>function addGitalkSource () {
const ele = document.createElement('link')
ele.rel = 'stylesheet'
ele.href= 'https://cdn.jsdelivr.net/npm/gitalk/dist/gitalk.min.css'
document.getElementsByTagName('head')[0].appendChild(ele)
}
function loadGitalk () {
function initGitalk () {
var gitalk = new Gitalk(Object.assign({
clientID: '1b0c10ce649501ea4a72',
clientSecret: '741b5e861137e3d5a482bba272c8201b78da6cb0',
repo: 'xfliu1998.github.io',
owner: 'xfliu1998',
admin: ['xfliu1998'],
id: '41a5ffba7dca7aebf297a4e9a8c5df0e',
language: 'en',
perPage: 10,
distractionFreeMode: false,
pagerDirection: 'last',
createIssueManually: true,
updateCountCallback: commentCount
},null))
gitalk.render('gitalk-container')
}
if (typeof Gitalk === 'function') initGitalk()
else {
addGitalkSource()
getScript('https://cdn.jsdelivr.net/npm/gitalk@latest/dist/gitalk.min.js').then(initGitalk)
}
}
function commentCount(n){
let isCommentCount = document.querySelector('#post-meta .gitalk-comment-count')
if (isCommentCount) {
isCommentCount.innerHTML= n
}
}
if ('Gitalk' === 'Gitalk' || !false) {
if (false) btf.loadComment(document.getElementById('gitalk-container'), loadGitalk)
else loadGitalk()
} else {
function loadOtherComment () {
loadGitalk()
}
}</script></div><script src="/js/script.js?v1"></script><script src="https://cdn.staticfile.org/jquery/3.6.3/jquery.min.js"></script><script async data-pjax src="https://cdn.wpon.cn/2022-sucai/Gold-ingot.js"></script><script async data-pjax src="/js/newYear.js"></script><script async src="//at.alicdn.com/t/font_2264842_b004iy0kk2b.js"></script><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/activate-power-mode.min.js"></script><script>POWERMODE.colorful = true;
POWERMODE.shake = true;
POWERMODE.mobile = false;
document.body.addEventListener('input', POWERMODE);
</script><script id="click-heart" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/click-heart.min.js" async="async" mobile="false"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div><!-- hexo injector body_end start --> <script data-pjax>if(document.getElementById('recent-posts') && (location.pathname ==='all'|| 'all' ==='all')){
var parent = document.getElementById('recent-posts');
var child = '<div class="recent-post-item" style="width:100%;height: auto"><div id="catalog_magnet"><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Machine-Learning-and-Deep-Learning/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">👩💻 机器学习与深度学习 (6)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Data-Structures-and-Algorithms/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">😼 数据结构与算法 (16)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Search-Advertisement-Recommendation-Causal/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">🗂️ 搜索/广告/推荐/因果 (10)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Data-Analysis-and-Processing/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">📒 数据分析与处理 (6)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Reading-Notes/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">📚 阅读笔记 (6)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Daily/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">💡 日常随想 (3)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><a class="magnet_link_more" href="https://xfliu1998.github.io/categories" style="flex:1;text-align: center;margin-bottom: 10px;">查看更多...</a></div></div>';
console.log('已挂载magnet')
parent.insertAdjacentHTML("afterbegin",child)}
</script><style>#catalog_magnet{flex-wrap: wrap;display: flex;width:100%;justify-content:space-between;padding: 10px 10px 0 10px;align-content: flex-start;}.magnet_item{flex-basis: calc(50% - 5px);background: #f2f2f2;margin-bottom: 10px;border-radius: 8px;transition: all 0.2s ease-in-out;}.magnet_item:hover{background: #b30070}.magnet_link_more{color:#555}.magnet_link{color:black}.magnet_link:hover{color:white}@media screen and (max-width: 600px) {.magnet_item {flex-basis: 100%;}}.magnet_link_context{display:flex;padding: 10px;font-size:16px;transition: all 0.2s ease-in-out;}.magnet_link_context:hover{padding: 10px 20px;}</style>
<style></style><script data-pjax>
function butterfly_swiper_injector_config(){
var parent_div_git = document.getElementById('recent-posts');
var item_html = '<div class="recent-post-item" style="height: auto;width: 100%"><div class="blog-slider swiper-container-fade swiper-container-horizontal" id="swiper_container"><div class="blog-slider__wrp swiper-wrapper" style="transition-duration: 0ms;"><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/09/17/Papers-Reading-about-NLP/" alt=""><img width="48" height="48" src="https://tse1-mm.cn.bing.net/th/id/OIP-C.KNjcp6IetyzFaIaSc8-eKAHaE8?w=303&h=201&c=7&r=0&o=5&dpr=1.88&pid=1.7" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-09-17</span><a class="blog-slider__title" href="2022/09/17/Papers-Reading-about-NLP/" alt="">Papers Reading about NLP</a><div class="blog-slider__text">自然语言处理论文阅读笔记</div><a class="blog-slider__button" href="2022/09/17/Papers-Reading-about-NLP/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/10/01/9-3D-Construction/" alt=""><img width="48" height="48" src="https://img.zcool.cn/community/017d495d0e6a9ea801205e4b7fa13c.png@1280w_1l_2o_100sh.png" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-10-01</span><a class="blog-slider__title" href="2022/10/01/9-3D-Construction/" alt="">3D Construction</a><div class="blog-slider__text">三维重建基础</div><a class="blog-slider__button" href="2022/10/01/9-3D-Construction/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2023/01/11/SfM-SLAM/" alt=""><img width="48" height="48" src="https://tse2-mm.cn.bing.net/th/id/OIP-C.V5uTTQ6LTBHc42xoBPG8hAHaEm?pid=ImgDet&rs=1" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-01-11</span><a class="blog-slider__title" href="2023/01/11/SfM-SLAM/" alt="">SfM & SLAM</a><div class="blog-slider__text">SfM和SLAM系统</div><a class="blog-slider__button" href="2023/01/11/SfM-SLAM/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2023/03/25/Papers-Ideas/" alt=""><img width="48" height="48" src="https://tse2-mm.cn.bing.net/th/id/OIP-C.Mmv8iGEVFxSQII6QH0BG9QHaEJ?w=302&h=180&c=7&r=0&o=5&dpr=2&pid=1.7" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-03-25</span><a class="blog-slider__title" href="2023/03/25/Papers-Ideas/" alt="">Papers Ideas</a><div class="blog-slider__text">大模型时代下的科研思路</div><a class="blog-slider__button" href="2023/03/25/Papers-Ideas/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/09/17/Papers-Summary/" alt=""><img width="48" height="48" src="https://tse1-mm.cn.bing.net/th/id/OIP-C.KNjcp6IetyzFaIaSc8-eKAHaE8?w=303&h=201&c=7&r=0&o=5&dpr=1.88&pid=1.7" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-09-17</span><a class="blog-slider__title" href="2022/09/17/Papers-Summary/" alt="">Papers Summary</a><div class="blog-slider__text">论文总结笔记</div><a class="blog-slider__button" href="2022/09/17/Papers-Summary/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/09/17/Papers-Reading-about-CV/" alt=""><img width="48" height="48" src="https://tse1-mm.cn.bing.net/th/id/OIP-C.KNjcp6IetyzFaIaSc8-eKAHaE8?w=303&h=201&c=7&r=0&o=5&dpr=1.88&pid=1.7" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-09-17</span><a class="blog-slider__title" href="2022/09/17/Papers-Reading-about-CV/" alt="">Papers Reading about CV</a><div class="blog-slider__text">计算机视觉论文阅读笔记</div><a class="blog-slider__button" href="2022/09/17/Papers-Reading-about-CV/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2023/06/05/Interview-Experience/" alt=""><img width="48" height="48" src="http:https://img.shijue.me/00964c481ad34d78acbf148d2b391c9e_d.jpg!dp6" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-06-05</span><a class="blog-slider__title" href="2023/06/05/Interview-Experience/" alt="">Interview Experience</a><div class="blog-slider__text">面经八股</div><a class="blog-slider__button" href="2023/06/05/Interview-Experience/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/01/21/Learning-Framework/" alt=""><img width="48" height="48" src="http:https://img.shijue.me/78ae8b05a73444cd9643a8312abc0d43.jpg!dp6" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-01-21</span><a class="blog-slider__title" href="2022/01/21/Learning-Framework/" alt="">Learning Framework</a><div class="blog-slider__text">学习大纲</div><a class="blog-slider__button" href="2022/01/21/Learning-Framework/" alt="">详情 </a></div></div></div><div class="blog-slider__pagination swiper-pagination-clickable swiper-pagination-bullets"></div></div></div>';
console.log('已挂载butterfly_swiper')
parent_div_git.insertAdjacentHTML("afterbegin",item_html)
}
var elist = 'undefined'.split(',');
var cpage = location.pathname;
var epage = '/';
var flag = 0;
for (var i=0;i<elist.length;i++){
if (cpage.includes(elist[i])){
flag++;
}
}
if ((epage ==='all')&&(flag == 0)){
butterfly_swiper_injector_config();
}
else if (epage === cpage){
butterfly_swiper_injector_config();
}
</script><script defer src="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.js"></script><script defer data-pjax src="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper_init.js"></script><script data-pjax src="https://npm.elemecdn.com/hexo-filter-gitcalendar/lib/gitcalendar.js"></script><script data-pjax>
function gitcalendar_injector_config(){
var parent_div_git = document.getElementById('recent-posts');
var item_html = '<container><style>#git_container{min-height: 280px}@media screen and (max-width:650px) {#git_container{min-height: 0px}}</style><div id="git_loading" style="width:10%;height:100%;margin:0 auto;display: block;"><svg xmlns="http:https://www.w3.org/2000/svg" xmlns:xlink="http:https://www.w3.org/1999/xlink" viewBox="0 0 50 50" style="enable-background:new 0 0 50 50" xml:space="preserve"><path fill="#d0d0d0" d="M25.251,6.461c-10.318,0-18.683,8.365-18.683,18.683h4.068c0-8.071,6.543-14.615,14.615-14.615V6.461z" transform="rotate(275.098 25 25)"><animatetransform attributeType="xml" attributeName="transform" type="rotate" from="0 25 25" to="360 25 25" dur="0.6s" repeatCount="indefinite"></animatetransform></path></svg><style>#git_container{display: none;}</style></div><div id="git_container"></div></container>';
parent_div_git.insertAdjacentHTML("afterbegin",item_html)
console.log('已挂载gitcalendar')
}
if( document.getElementById('recent-posts') && (location.pathname ==='/'|| '/' ==='all')){
gitcalendar_injector_config()
GitCalendarInit("https://gitcalendar.fomal.cc/api?xfliu1998",['#d9e0df', '#c6e0dc', '#a8dcd4', '#9adcd2', '#89ded1', '#77e0d0', '#5fdecb', '#47dcc6', '#39dcc3', '#1fdabe', '#00dab9'],'xfliu1998')
}
</script><!-- hexo injector body_end end --><script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"model":{"jsonPath":"/live2dw/assets/haruto.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false},"log":false,"pluginJsPath":"lib/","pluginModelPath":"assets/","pluginRootPath":"live2dw/","tagMode":false});</script></body></html>