-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path87dfb581.html
More file actions
467 lines (362 loc) · 40.8 KB
/
87dfb581.html
File metadata and controls
467 lines (362 loc) · 40.8 KB
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
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.3.0">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css" integrity="sha256-HtsXJanqjKTc8vVQjO4YMhiqFoXkfBsjBWcX91T1jr8=" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
<script class="next-config" data-name="main" type="application/json">{"hostname":"tallate.github.io","root":"/","images":"/images","scheme":"Gemini","darkmode":false,"version":"8.18.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":false,"style":null},"fold":{"enable":false,"height":500},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"}}</script><script src="/js/config.js"></script>
<meta name="description" content="以前做leetcode时积累了不少比较经典的问题，但是很少总结，经常做一道是一道，效率颇低，而且应付面试经常会碰到挺熟但还是被“卡住”的情况，遂做一总结。 只摘出Medium和Hard问题。 有的题可以有多个分类，我只将其归入最合适解法的那类中。 题目有大类、有子类，大类是链表、数组、动态规划，子类指的是单独的一种“套路”，比如树中的深度优先搜索是一种套路，动态规划中的背包也属于一种套路。">
<meta property="og:type" content="article">
<meta property="og:title" content="算法题复盘">
<meta property="og:url" content="https://tallate.github.io/87dfb581.html">
<meta property="og:site_name" content="Tallate">
<meta property="og:description" content="以前做leetcode时积累了不少比较经典的问题，但是很少总结，经常做一道是一道，效率颇低，而且应付面试经常会碰到挺熟但还是被“卡住”的情况，遂做一总结。 只摘出Medium和Hard问题。 有的题可以有多个分类，我只将其归入最合适解法的那类中。 题目有大类、有子类，大类是链表、数组、动态规划，子类指的是单独的一种“套路”，比如树中的深度优先搜索是一种套路，动态规划中的背包也属于一种套路。">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-12-13T14:28:55.000Z">
<meta property="article:modified_time" content="2025-07-06T17:56:20.900Z">
<meta property="article:author" content="tallate">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="https://tallate.github.io/87dfb581.html">
<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"https://tallate.github.io/87dfb581.html","path":"/87dfb581.html","title":"算法题复盘"}</script>
<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>算法题复盘 | Tallate</title>
<noscript>
<link rel="stylesheet" href="/css/noscript.css">
</noscript>
</head>
<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
<div class="headband"></div>
<main class="main">
<div class="column">
<header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切换导航栏" role="button">
<span class="toggle-line"></span>
<span class="toggle-line"></span>
<span class="toggle-line"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<i class="logo-line"></i>
<p class="site-title">Tallate</p>
<i class="logo-line"></i>
</a>
<p class="site-subtitle" itemprop="description">该吃吃该喝喝 啥事别往心里搁</p>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger" aria-label="搜索" role="button">
<i class="fa fa-search fa-fw fa-lg"></i>
</div>
</div>
</div>
<nav class="site-nav">
<ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="home fa-fw"></i>首页</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="user fa-fw"></i>关于</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="tags fa-fw"></i>标签<span class="badge">84</span></a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="th fa-fw"></i>分类<span class="badge">25</span></a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="archive fa-fw"></i>归档<span class="badge">192</span></a></li>
<li class="menu-item menu-item-search">
<a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
</a>
</li>
</ul>
</nav>
<div class="search-pop-overlay">
<div class="popup search-popup"><div class="search-header">
<span class="search-icon">
<i class="fa fa-search"></i>
</span>
<div class="search-input-container">
<input autocomplete="off" autocapitalize="off" maxlength="80"
placeholder="搜索..." spellcheck="false"
type="search" class="search-input">
</div>
<span class="popup-btn-close" role="button">
<i class="fa fa-times-circle"></i>
</span>
</div>
<div class="search-result-container no-result">
<div class="search-result-icon">
<i class="fa fa-spinner fa-pulse fa-5x"></i>
</div>
</div>
</div>
</div>
</header>
<aside class="sidebar">
<div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
<ul class="sidebar-nav">
<li class="sidebar-nav-toc">
文章目录
</li>
<li class="sidebar-nav-overview">
站点概览
</li>
</ul>
<div class="sidebar-panel-container">
<!--noindex-->
<div class="post-toc-wrap sidebar-panel">
<div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E6%95%B0%E7%BB%84%E3%80%81%E5%AD%97%E7%AC%A6%E4%B8%B2%E3%80%81%E5%BA%8F%E5%88%97%E3%80%81%E9%93%BE%E8%A1%A8"><span class="nav-number">1.</span> <span class="nav-text">数组、字符串、序列、链表</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%9A%BE%E4%BB%A5%E8%A2%AB%E5%BD%92%E7%B1%BB"><span class="nav-number">1.1.</span> <span class="nav-text">难以被归类</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Two-Pointers"><span class="nav-number">1.2.</span> <span class="nav-text">Two Pointers</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Binary-Search"><span class="nav-number">1.3.</span> <span class="nav-text">Binary Search</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A4%A7%E6%95%B0"><span class="nav-number">1.4.</span> <span class="nav-text">大数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#DFS%E3%80%81BFS%E3%80%81backtracking"><span class="nav-number">1.5.</span> <span class="nav-text">DFS、BFS、backtracking</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#hash"><span class="nav-number">1.6.</span> <span class="nav-text">hash</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E6%A0%91"><span class="nav-number">2.</span> <span class="nav-text">树</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%90%9C%E7%B4%A2%EF%BC%88DFS%E3%80%81BFS%EF%BC%89"><span class="nav-number">2.1.</span> <span class="nav-text">搜索（DFS、BFS）</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%89%8D%E5%BA%8F%E3%80%81%E4%B8%AD%E5%BA%8F%E3%80%81%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86"><span class="nav-number">2.2.</span> <span class="nav-text">前序、中序、后序遍历</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-number">2.3.</span> <span class="nav-text">二叉树</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1-%E5%88%86%E6%B2%BB"><span class="nav-number">3.</span> <span class="nav-text">算法设计 - 分治</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1-%E8%B4%AA%E5%BF%83"><span class="nav-number">4.</span> <span class="nav-text">算法设计 - 贪心</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1-%E5%9B%9E%E6%BA%AF"><span class="nav-number">5.</span> <span class="nav-text">算法设计 - 回溯</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92"><span class="nav-number">6.</span> <span class="nav-text">算法设计 - 动态规划</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9C%80%E5%AD%90%E4%B8%B2%E3%80%81%E6%9C%80%E5%AD%90%E5%BA%8F%E5%88%97%E9%97%AE%E9%A2%98"><span class="nav-number">6.1.</span> <span class="nav-text">最子串、最子序列问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="nav-number">6.2.</span> <span class="nav-text">背包问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%85%B6%E4%BB%96"><span class="nav-number">6.3.</span> <span class="nav-text">其他</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E6%95%B0%E5%AD%A6%E9%A2%98"><span class="nav-number">7.</span> <span class="nav-text">数学题</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BD%99%E6%95%B0"><span class="nav-number">7.1.</span> <span class="nav-text">余数</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E5%8F%82%E8%80%83"><span class="nav-number">8.</span> <span class="nav-text">参考</span></a></li></ol></div>
</div>
<!--/noindex-->
<div class="site-overview-wrap sidebar-panel">
<div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
<p class="site-author-name" itemprop="name">tallate</p>
<div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
<nav class="site-state">
<div class="site-state-item site-state-posts">
<a href="/archives/">
<span class="site-state-item-count">192</span>
<span class="site-state-item-name">日志</span>
</a>
</div>
<div class="site-state-item site-state-categories">
<a href="/categories/">
<span class="site-state-item-count">25</span>
<span class="site-state-item-name">分类</span></a>
</div>
<div class="site-state-item site-state-tags">
<a href="/tags/">
<span class="site-state-item-count">84</span>
<span class="site-state-item-name">标签</span></a>
</div>
</nav>
</div>
</div>
</div>
</div>
</aside>
</div>
<div class="main-inner post posts-expand">
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://tallate.github.io/87dfb581.html">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="tallate">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Tallate">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="算法题复盘 | Tallate">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
算法题复盘
</h1>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2020-12-13 22:28:55" itemprop="dateCreated datePublished" datetime="2020-12-13T22:28:55+08:00">2020-12-13</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2025-07-07 01:56:20" itemprop="dateModified" datetime="2025-07-07T01:56:20+08:00">2025-07-07</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody"><p>以前做leetcode时积累了不少比较经典的问题，但是很少总结，经常做一道是一道，效率颇低，而且应付面试经常会碰到挺熟但还是被“卡住”的情况，遂做一总结。</p>
<ul>
<li>只摘出Medium和Hard问题。</li>
<li>有的题可以有多个分类，我只将其归入最合适解法的那类中。</li>
<li>题目有大类、有子类，大类是链表、数组、动态规划，子类指的是单独的一种“套路”，比如树中的深度优先搜索是一种套路，动态规划中的背包也属于一种套路。</li>
</ul>
<span id="more"></span>
<h1 id="数组、字符串、序列、链表"><a href="#数组、字符串、序列、链表" class="headerlink" title="数组、字符串、序列、链表"></a>数组、字符串、序列、链表</h1><h2 id="难以被归类"><a href="#难以被归类" class="headerlink" title="难以被归类"></a>难以被归类</h2><ol>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/longest-palindromic-substring/">https://leetcode.com/problems/longest-palindromic-substring/</a><br>这一题乍一看似乎用DP好解，先找出所有长度为2的回文，再找长度为3的，以此类推，但是DP是O(n2)的。<br>这题有非DP的更优解法，即遍历然后”从中间往外扩的方式”，比如122213，设置l、r两个指针，当遍历到位置i=1时先将r推进到i=3，然后再判断i=0和i=4是否相等，得到回文长度5，之后再从i=5开始找下一个回文串。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/remove-nth-node-from-end-of-list/">https://leetcode.com/problems/remove-nth-node-from-end-of-list/</a><br>删除倒数第n个元素。<br>递归返回链表长度，判断下next链表长度是n则删除之。<br>注意边界条件n是链表头部的情况。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/">https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/</a><br>搜索回溯。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked</a><br>两两交换链表节点，递归做很简单</p>
</li>
<li><p>(hard)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked</a><br>k个一组反转链表，考验细节</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked</a><br>我用的最简单的枚举方式，O(n^2)，但是如果第一次遍历记录hash[n]为前n个数字的和，可以对每个nums[i]找j使得hash[i] - hash[j] = k，这样可以得到一个O(n)的解法。</p>
</li>
<li><p>(easy)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-100-liked</a><br>对称二叉树，用了两个栈来保存左和右子树，每次从栈弹出两个左右子树root节点，比较左子树的右节点和右子树的左节点。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked</a><br>轮转数组<br>简单方法可以直接new一个数组来保存轮转后的位置或者时间换空间来一个个轮转<br>复杂方法涉及到将前最大公约数个数字进行轮转操作，轮转指的是将nums[i]放到nums[i + k]，再把nums[i + k]放到nums[i + 2k]，以此类推直到初始位置，为什么是最大公约数涉及一个推导，我是直接看的官方的题解。<br>另外求最大公约数是使用的辗转相除法。</p>
</li>
</ol>
<h2 id="Two-Pointers"><a href="#Two-Pointers" class="headerlink" title="Two Pointers"></a>Two Pointers</h2><p>在链表、数组里找出一个满足条件的子串、子序列，暴力搜索会导致O(n2)的复杂度，而让两个指针同时滑动可以更快地找到目标结果。</p>
<ul>
<li>目标链表、数组一般是有序的；</li>
</ul>
<ol>
<li>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/longest-substring-without-repeating-characters/">https://leetcode.com/problems/longest-substring-without-repeating-characters/</a><br>用hash保存已出现的元素，当然直接用一个<code>bool[26]</code>记录也没问题</li>
<li>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/container-with-most-water/">https://leetcode.com/problems/container-with-most-water/</a><br>确定桶的两个端点，最多能装多少水。<br>一种最简单的想法是O(n2)的，即算出所有区间(i, j)内能装的水量，比较所有这些区间，得到最大值。<br>但用双指针能得到更简单的解法初始化l=0, r=数组长度，如果l位置的高度较低则l++，反之r–。为什么不是反过来？可以用反证法证明，如果l较低我们却令r–，这时不管r的下一个值是多少，面积始终是<code>height[l] * (r - l)</code>，面积只能是越来越小，也就是短板效应。</li>
<li>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/3sum/">https://leetcode.com/problems/3sum/</a><br>找出数组中的所有三元组(a, b, c)，令a+b+c=0。<br>一种简单的想法是将所有数据保存到Map中，然后找二元组(a, b)令a+b=-c。<br>还有一种twoPointer的解法，复杂度也是O(n2)。</li>
<li>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/next-permutation/submissions/">https://leetcode.cn/problems/next-permutation/submissions/</a><br>找下一个排列，比如12543，要把3和2交换，然后把最后3个数字倒序排列成13245。</li>
</ol>
<h2 id="Binary-Search"><a href="#Binary-Search" class="headerlink" title="Binary Search"></a>Binary Search</h2><p>二分搜索每次将查询范围缩小一半，以期找到目标结果。</p>
<ul>
<li>输入数组是有序的；</li>
<li>如何找到结果的上确界、下确界？</li>
</ul>
<ol>
<li>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/search-in-rotated-sorted-array/">https://leetcode.com/problems/search-in-rotated-sorted-array/</a><br>就是二分查找，只是折半后需要比较一下中间位置元素和lmax、rmax之间的大小。</li>
<li>(hard)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/median-of-two-sorted-arrays/">https://leetcode.com/problems/median-of-two-sorted-arrays/</a><br>思路还是二分查找的思路，只不过这题需要对两个数组同时缩小范围。</li>
</ol>
<h2 id="大数"><a href="#大数" class="headerlink" title="大数"></a>大数</h2><p>大数不能用基本类型保存，主要思路是用链表、数组等结构来实现数学运算。</p>
<ol>
<li>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/add-two-numbers/">https://leetcode.com/problems/add-two-numbers/</a><br>链表保存数字，相加时注意进位。<br>引申：可以用数组存、可以是别的进制。</li>
</ol>
<h2 id="DFS、BFS、backtracking"><a href="#DFS、BFS、backtracking" class="headerlink" title="DFS、BFS、backtracking"></a>DFS、BFS、backtracking</h2><p>比如给出多个数组，找出他们元素的组合这种问题。</p>
<ol>
<li>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/letter-combinations-of-a-phone-number/">https://leetcode.com/problems/letter-combinations-of-a-phone-number/</a><br>电话按键组合。<br>深度优先搜索求多个按键元素的笛卡尔积。</li>
<li>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/generate-parentheses/">https://leetcode.com/problems/generate-parentheses/</a><br>括号组合。<br>每次选左括号或右括号，当右括号选得比左括号多时就直接返回（剪枝）。</li>
</ol>
<h2 id="hash"><a href="#hash" class="headerlink" title="hash"></a>hash</h2><p>给出一个数组，求2-sum、3-sum、4-sum，这种问题都可以使用hash来保存中间结果</p>
<ol>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/4sum/">https://leetcode.com/problems/4sum/</a><br>4sum问题的基础是2sum和3sum，即对<code>a[x]</code>找<code>3sum(x+1, -a[x])</code>。<br>3sum就是对<code>a[x]</code>找<code>2sum(x+1, -a[x])</code>。<br>2sum问题可以通过twoPointers方法解决，即<code>a[l]+a[r]<sum</code>则l++，<code>a[l]+a[r]>sum</code>则r–，若<code>a[l]+a[r]==sum</code>则l++、r–，且如果<code>a[l]==a[l+1]</code>也要忽略掉，因为要避免重复。</p>
</li>
<li><p>需要优化(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/longest-consecutive-sequence/description/">https://leetcode.cn/problems/longest-consecutive-sequence/description/</a><br>hash+并查集<br>关键是使用hash来存储并查集的集合：</p>
</li>
</ol>
<ul>
<li>数据范围是-10^9~10^9，因此不能使用数组来存储；我刚开始想在并查集的根用负数存储集合的大小，但是看到数据范围包含了负数所以行不通，只能新开了一个hash集合用于存储大小</li>
<li>并查集压缩路径可以减少耗时</li>
</ul>
<h1 id="树"><a href="#树" class="headerlink" title="树"></a>树</h1><h2 id="搜索（DFS、BFS）"><a href="#搜索（DFS、BFS）" class="headerlink" title="搜索（DFS、BFS）"></a>搜索（DFS、BFS）</h2><ol>
<li>(hard)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/sum-of-distances-in-tree/">https://leetcode.com/problems/sum-of-distances-in-tree/</a><br>求每个节点到其他所有节点的路径和。<br>最开始想到这题可以用Floyd求所有节点之间的最短路径，然后再算结果就好算了，复杂度是O(n3)，。</li>
</ol>
<h2 id="前序、中序、后序遍历"><a href="#前序、中序、后序遍历" class="headerlink" title="前序、中序、后序遍历"></a>前序、中序、后序遍历</h2><ol>
<li>(hard)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/recover-binary-search-tree/">https://leetcode.com/problems/recover-binary-search-tree/</a><br>交换树中两个节点，使得树恢复成二叉搜索树。<br>如果一棵树左边（包括root）有个节点比右边（包括root）大，则将这两个节点换一下即可。<br>解法描述起来简单，前序中序似乎都有解法，我采用的是后序遍历：先找到两个子节点的<最小值, 最大值>，然后在root处判断是否要进行交换。注意不要在遍历过程中交换，而是在整棵树遍历完毕后再交换一次。</li>
</ol>
<h2 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h2><ol>
<li><p>（miduem）<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/validate-binary-search-tree/submissions/">https://leetcode.cn/problems/validate-binary-search-tree/submissions/</a><br>按二叉搜索树定义编写遍历代码，考验递归理解。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/">https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/</a><br>按二叉树的前序和中序遍历还原二叉树<br>思路是用hash保存每个节点值的位置（节点值不重复），前序的第一个数就是root，使用hash就可以快速找到在中序遍历中的root的位置，据此可以得到左右子树的范围。</p>
</li>
</ol>
<h1 id="算法设计-分治"><a href="#算法设计-分治" class="headerlink" title="算法设计 - 分治"></a>算法设计 - 分治</h1><p>分治法的思路是将大问题每次分成多个对等的子问题，并且将子问题的结果合并后能得到原问题的解。</p>
<ol>
<li>(hard)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/merge-k-sorted-lists/">https://leetcode.com/problems/merge-k-sorted-lists/</a><br>这题初看似乎挺简单，每次从n个链表中找出最小的那个添加到result即可，但是这样时间复杂度是非常高的，达到了O(n<em>n</em>m)。<br>其实可以使用分治法来简化问题，每次将一半的链表先合并，然后再将两个合并后的链表合并，这样时间复杂度只有O(n*m)</li>
</ol>
<h1 id="算法设计-贪心"><a href="#算法设计-贪心" class="headerlink" title="算法设计 - 贪心"></a>算法设计 - 贪心</h1><ol>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/jump-game/description/">https://leetcode.cn/problems/jump-game/description/</a><br>刚看到以为是要做搜索，但实际上只需要从左向右扫描一次，只要每个节点向右跳的范围里有能跳更远的节点，就能一直往右跳到最后。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/container-with-most-water/description/">https://leetcode.cn/problems/container-with-most-water/description/</a><br>这里的贪心策略是：从最左和最右两条线为起点，宽度更小的容器如果要装水量更大，必然高度要比最左或最右更高，每次都从左或右的低者收缩宽度找到更高的一条线。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/maximum-swap/">https://leetcode.cn/problems/maximum-swap/</a><br>贪心策略，比较复杂，见注释</p>
</li>
</ol>
<h1 id="算法设计-回溯"><a href="#算法设计-回溯" class="headerlink" title="算法设计 - 回溯"></a>算法设计 - 回溯</h1><ol>
<li>(hard)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/n-queens/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/n-queens/description/?envType=study-plan-v2&envId=top-100-liked</a><br>N皇后问题，我的解法是写扩散的，定义<code>int[][] visited</code>来记录能被之前放的皇后吃到的位置，这些位置不能再放皇后，然后一行一行地遍历整个棋盘。</li>
</ol>
<h1 id="算法设计-动态规划"><a href="#算法设计-动态规划" class="headerlink" title="算法设计 - 动态规划"></a>算法设计 - 动态规划</h1><h2 id="最子串、最子序列问题"><a href="#最子串、最子序列问题" class="headerlink" title="最子串、最子序列问题"></a>最<em>子串、最</em>子序列问题</h2><ol>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/palindromic-substrings/description/">https://leetcode.cn/problems/palindromic-substrings/description/</a><br>找所有回文子串，动态规划存储的状态表达式是d[x][y] = (s[x] == s[y]) && d[x+1][y-1]</p>
</li>
<li><p>(hard)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/longest-valid-parentheses/">https://leetcode.com/problems/longest-valid-parentheses/</a><br>找子串，其中括号必须是成对的。<br>最简单的办法是先找长度为2的，然后再在2的基础上找长度为4的，以此类推，复杂度会高一些。<br>还有一种办法是用一个栈来保存括号，遇到左括号时直接压入，而当遇到右括号时则将栈中的左括号弹出，统计连续能成对的数量（如果压入一个右括号不能与之前的左括号成对，说明接下来的括号和之前的括号都不能成对了）。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/longest-increasing-subsequence/submissions/">https://leetcode.cn/problems/longest-increasing-subsequence/submissions/</a><br>n^2是动态规划的方案，dp[i]存储以nums[i]作为结尾的序列长度，对每个i，需要遍历所有j < i，更新dp[i] = max(dp[j]{nums[j] < nums[i]}) + 1<br>nlogn的方案很难想，存储牌堆顶数组top[n], 其中top[i] = 长度为i的序列的最大值，每抽一张牌k，搜索top[i]中第一个比nums[k]大的替换，如果找不到则插入到末尾，题解：<a target="_blank" rel="noopener" href="https://www.kancloud.cn/digest/pieces-algorithm/163625">https://www.kancloud.cn/digest/pieces-algorithm/163625</a></p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=top-100-liked</a><br>最长公共子序列问题<br>dp[i][j] = dp[i - 1][j - 1] + 1, t1[i] == t2[j]<br>dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]), t1[i] != t2[j]</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/maximum-product-subarray/description/">https://leetcode.cn/problems/maximum-product-subarray/description/</a><br>乘积最大子数组，因为最大成绩可能是偶数个负数相乘，因此需要定义两个数组，一个mindp[i]存储以第i个数为末尾的子数组的最小乘积<br>如果当前数nums[i] < 0，则<br>maxdp[i] = max(mindp[i] * nums[i], nums[i])<br>mindp[i] = min(maxdp[i] * nums[i], nums[i])<br>如果当前数nums[i] > 0，则<br>maxdp[i] = max(maxdp[i] * nums[i], nums[i])<br>mindp[i] = min(mindp[i] * nums[i], nums[i])</p>
</li>
</ol>
<h2 id="背包问题"><a href="#背包问题" class="headerlink" title="背包问题"></a>背包问题</h2><ol>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/partition-equal-subset-sum/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/partition-equal-subset-sum/description/?envType=study-plan-v2&envId=top-100-liked</a><br>抽象为01背包问题，定义dp[j]的价值为数值，如果最终dp[j]==j，说明存在和为j的数，状态转移函数：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])<br>01背包问题，需要先遍历物品，因为每个物品只能使用一次，然后容量上从大到小遍历。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/coin-change/description/">https://leetcode.cn/problems/coin-change/description/</a><br>01背包的升级问题，完全背包问题，定义时dp[amount]表示每个容量可以使用的最少硬币数量，从容量1开始遍历，求dp[amount]的最小值，有状态表达式：dp[n] = min(dp[n], dp[n - x] + 1), x为遍历所有硬币的价值<br>01背包问题因为物品用不用是有状态的，所以会增加一个维度dp[amount][coin]</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked</a><br>将目标数分解为完全平方数的和，我理解成完全背包问题，不过刚开始goods需要自己算出来。</p>
</li>
</ol>
<h2 id="其他"><a href="#其他" class="headerlink" title="其他"></a>其他</h2><ol>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/house-robber/submissions/">https://leetcode.cn/problems/house-robber/submissions/</a><br>dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])<br>dp[i][1] = nums[i] + dp[i - 1][0]</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/maximal-square/description/">https://leetcode.cn/problems/maximal-square/description/</a><br>dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])<br>[i][j]代表以该位置作为右下角形成的最大的正方形的边长</p>
</li>
<li><p>待优化(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/">https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/</a><br>买卖股票<br>定义多个状态：因为包含冷冻期，因此增加一个冷冻状态，注意买股票后不一定要后一天马上卖出，因此增加一个持有状态。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked</a><br>单词拆分，思路有点像完全背包。</p>
</li>
<li><p>(medium)<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked">https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked</a><br>编辑距离，定义dp[i][j]为word1的前i个字符转换为word2的前j个字符的最少需要操作次数<br>如果两个字符相等，则dp[i][j]=dp[i-1][j-1]，即不需要任何操作<br>删除字符、新增字符可以表示成dp[i-1][j], dp[i][j-1]，因此两个字符不等时的表达式为dp[i][j]=min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1</p>
</li>
</ol>
<h1 id="数学题"><a href="#数学题" class="headerlink" title="数学题"></a>数学题</h1><h2 id="余数"><a href="#余数" class="headerlink" title="余数"></a>余数</h2><ol>
<li>(medium)<a target="_blank" rel="noopener" href="https://leetcode.com/problems/divide-two-integers/">https://leetcode.com/problems/divide-two-integers/</a><br>这题有两种思路，比如要得到a除以b的商的话：<br>一种可以是每次加一个b，直到超过a再停下来；<br>或者利用位操作每次给b=b<<1，直到b超过a再停下来，然后每次a减去b，并累计减了多少个b。</li>
</ol>
<h1 id="参考"><a href="#参考" class="headerlink" title="参考"></a>参考</h1><ol>
<li><a target="_blank" rel="noopener" href="https://www.zhihu.com/question/36738189">LeetCode按照怎样的顺序来刷题比较好？</a></li>
</ol>
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/[email protected]/dist/kity.min.js"></script><script type="text/javascript" src="https://cdn.jsdelivr.net/npm/[email protected]/dist/kityminder.core.min.js"></script><script defer="true" type="text/javascript" src="https://cdn.jsdelivr.net/npm/[email protected]/dist/mindmap.min.js"></script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/mindmap.min.css">
</div>
<footer class="post-footer">
<div class="post-nav">
<div class="post-nav-item">
<a href="/c6369e85.html" rel="prev" title="分布式事务实现">
<i class="fa fa-angle-left"></i> 分布式事务实现
</a>
</div>
<div class="post-nav-item">
<a href="/3a4761a.html" rel="next" title="MySQL2_1explain">
MySQL2_1explain <i class="fa fa-angle-right"></i>
</a>
</div>
</div>
</footer>
</article>
</div>
</div>
</main>
<footer class="footer">
<div class="footer-inner">
<div class="copyright">
©
<span itemprop="copyrightYear">2025</span>
<span class="with-love">
<i class="fa fa-heart"></i>
</span>
<span class="author" itemprop="copyrightHolder">tallate</span>
</div>
<div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
</div>
</div>
</footer>
<div class="back-to-top" role="button" aria-label="返回顶部">
<i class="fa fa-arrow-up fa-lg"></i>
<span>0%</span>
</div>
<a href="https://github.com/tallate" class="github-corner" title="在 GitHub 上关注我" aria-label="在 GitHub 上关注我" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>
<noscript>
<div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>
<script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/next-boot.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.1/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>
<script class="next-config" data-name="mermaid" type="application/json">{"enable":true,"version":"7.1.2","options":null,"js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mermaid/10.3.0/mermaid.min.js","integrity":"sha256-9y71g5Lz/KLsHjB8uXwnkuWDtAMDSzD/HdIbqhJfTAI="}}</script>
<script src="/js/third-party/tags/mermaid.js"></script>
</body>
</html>