-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
3341 lines (3052 loc) · 89.8 KB
/
index.html
File metadata and controls
3341 lines (3052 loc) · 89.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
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
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en ">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>摸鱼日志 || 记录一些日常学习及奇奇怪怪的事情</title>
<meta name="author" content="Like Frost">
<meta name="description" content="吾生也有涯，而知也无涯 ">
<meta name="keywords" content="编程,coding,个人博客 ">
<link rel="icon" href="/images/avatar.jpg">
<link rel="stylesheet" href="/css/antd.min.css">
<link rel="stylesheet" href="/css/full-theme.css">
<script src="/js/vue.js"></script>
<script src="/js/antd.min.js"></script>
<meta name="generator" content="Hexo 5.4.0"></head>
<body>
<div id="loading"
style="height: 100vh; width: 100%; position: fixed;display: flex;z-index: 200; justify-content: space-between;">
<div id="loadleft" style="width: 50%;background-color: #ffffff;transition: width 0.6s ease-out;"></div>
<div id="loadright" style="width: 50%;background-color: #ffffff;transition: width 0.6s ease-out;"></div>
<div
style="position: fixed; height: 100vh; width: 100%;display: flex;justify-content: center;align-items: center;">
<div id="loadcontent"
style="width:400px;height:400px;padding:50px;border-radius:50%;display:flex;justify-content:center;align-items:center;border:solid 10px#a3ddfb; text-align:center;opacity:1;transition:opacity 0.3s ease-out;">
<div>
<h2>LOADING...</h2>
<p>加载过慢请开启缓存(浏览器默认开启)</p>
<div>
<img src="/dancingkitty.gif" alt="loading">
</div>
</div>
</div>
</div>
</div>
<div id="layout">
<transition name="into">
<div v-show="show_page" style="display: none;">
<div id="menu_show">
<nav id="menu">
<div class="desktop-menu">
<a href="/">
<span class="title">摸鱼日志</span>
</a>
<a href="/">
<span>
<a-icon type="home" theme="outlined" />
</span>
<span>首页</span>
</a>
<a href="/tags">
<span>
<a-icon type="tags" theme="outlined" />
</span>
<span>标签</span>
</a>
<a href="/archives">
<span>
<a-icon type="ordered-list" theme="outlined" />
</span>
<span>归档</span>
</a>
</div>
<div :class="'phone-menu ' + menu_show" id="phone-menu">
<div :class="'title'" @click="menu_show=!menu_show">
<span style="margin-right: 10px;">
<a-icon type="appstore" theme="filled" />
</span>
<span>摸鱼日志</span>
</div>
<div class="items" v-show="menu_show">
<a href="/">
<div class="item">
<div style="min-width:20px; max-width:50px; width: 10%">
<a-icon type="home" theme="outlined" />
</div>
<div style="min-width:100px;max-width: 150%;width: 20%;">首页</div>
</div>
</a>
<a href="/tags">
<div class="item">
<div style="min-width:20px; max-width:50px; width: 10%">
<a-icon type="tags" theme="outlined" />
</div>
<div style="min-width:100px;max-width: 150%;width: 20%;">标签</div>
</div>
</a>
<a href="/archives">
<div class="item">
<div style="min-width:20px; max-width:50px; width: 10%">
<a-icon type="ordered-list" theme="outlined" />
</div>
<div style="min-width:100px;max-width: 150%;width: 20%;">归档</div>
</div>
</a>
</div>
<div class="curtain" v-show="menu_show"></div>
</div>
</nav>
</div>
<div id="main">
<div id="home-head" style=background-image:url('/home.jpg')>
<script>
var menu = document.getElementById("menu")
menu.className += " menu-color"
</script>
<div id="home-info" class="home-info" @click="home_click">
<span class="loop"></span>
<span class="loop"></span>
<span class="loop"></span>
<span class="loop"></span>
<span class="info">
<div class="wrap">
<h1>摸鱼日志</h1>
<h3>记录一些日常学习及奇奇怪怪的事情</h3>
<h5>吾生也有涯，而知也无涯</h5>
</div>
</span>
</div>
</div>
<div id="home-posts-wrap" class=>
<div id="home-posts">
<div id="posts">
<div class="post">
<a href="/随机面试题/">
<h2>
随机面试题
</h2>
</a>
<div class="category-and-date">
<span class="date">
<span class="icon">
<a-icon type="calendar" theme="filled" />
</span>
2024/3/6
</span>
</div>
<div class="excerpt">
<div class="content" v-pre>
<span id="more"></span>
<ul>
<li><p><strong>JavaScript作用域和闭包</strong><br>Q：解释 JavaScript 中的词法作用域（Lexical Scoping）和闭包（Closure）。闭包是如何工作的，它们在实际开发中有哪些用途？<br>A：词法作用域是指一个函数的内部作用域，闭包是函数以及其周围的此法环境，它通常是一个函数，这个函数能访问外部的变量，因此这个变量一直存续在函数存续期间；在实际开发过程中，闭包可以用于将函数和他词法环境绑定，比如计算长方形的面积，当他的宽固定时，就可以写作：</p>
<pre><code class="js">function calcArea(width){
return (height)=>{
return width*height;
}
}
const area = calcArea(10);
area(20);
</code></pre>
<p>另外，闭包也用于节流、防抖等，但要注意错误的使用闭包会造成内存泄漏。<br>C：实际应用：数据封装（模拟私有变量）、函数柯里化、事件处理器和回调函数</p>
</li>
<li><p><strong>异步编程</strong><br>Q：解释 <code>Promise</code> 和 <code>async/await</code> 在 JavaScript 中的作用。如何使用它们处理异步操作？请给出一个使用 <code>async/await</code> 处理 HTTP 请求并捕获错误的示例代码。<br>A：由于js是单线程的，所以一些网络请求等需求需要异步实现，最早使用的方式是回调函数，但是当一个回调函数依赖于另一个回调函数的时候，就会造成回调地狱，promise为了解决这一问题出现，promise的构造函数接受resolve和reject两个参数；async/await是promise的语法糖，实现了用同步的写法实现异步请求。<br>C：promise是一个代表了异步操作最终完成或失败的对象。</p>
<p>示例代码：</p>
<pre><code class="js">async function getData(){
try{
const res = await axios.get("xx");
console.log(res);
}catch(err){
console.log(err);
}
}
getData();
</code></pre>
</li>
<li><p><strong>CSS布局</strong><br>Q：描述 Flexbox 和 Grid 布局的主要区别。你更倾向于在什么情况下使用 Flexbox，什么情况下使用 Grid？<br>A：flex是弹性盒子，gird是栅格布局，flex较为灵活。<br>C：flexbox是一种布局方法，意味着它能够处理元素在一个方向上的空间分配，flex设计的初衷是为了提供一种有效的方式来布局、对齐和分配在容器中的项目空间，即使大小是未知或动态变化的。 一维布局；<br>grid是二维布局。</p>
</li>
<li><p><strong>前端性能优化</strong><br>Q：列举至少五种你可以用来提高网页性能的方法或技术。请解释为什么这些方法会影响性能，并且你是如何决定哪些方法最适合当前项目的。<br>A：1. 使用精灵图，当前端使用较多小尺寸icon的时候，可以考虑把这些合并成一个较大的精灵图，避免多次请求服务器资源；2. 首屏加载优化，可以使用服务端渲染（ssr），加载首屏时直接渲染服务端返回的html，避免因计算样式或加载js脚本影响加载速度； 3. 减少页面的重排和重绘，尽量避免使用table，因为table中一个小的变化会引起整个页面的重排； 4. 使用缓存，当资源未发生改变时，使用本地缓存可以提高用户体验； 5. 开启gzip加速，前端资源通过gzip打包放在服务器上，减少文件体积，加快获取速度。<br>C：决定使用什么优化技术：分析网站或应用的性能瓶颈。</p>
</li>
<li><p><strong>Web安全</strong><br>Q：解释跨站脚本攻击（XSS）和跨站请求伪造（CSRF）的区别。你会如何防御这两种攻击？<br>A： XSS是通过在url、文本字段中注入script脚本实现的，比如在访问页面网址时携带参数，参数内包含script脚本，页面通过参数解析，执行恶意脚本；或者在评论区内提交一段script脚本，看到的用户都会遭受攻击；<br>CSRF是利用用户的授权信息去伪造请求，比如引导用户点击危险网站，恶意脚本会利用用户的身份认证去伪造危险行为。<br>为了防范XSS，可以对js代码进行转义、过滤用户输入等；防范CSRF可以防止页面注入iframe、使用csrf token验证等。</p>
</li>
</ul>
<hr>
<h3 id="1-实现一个-Promise-all"><a href="#1-实现一个-Promise-all" class="headerlink" title="1. 实现一个 Promise.all"></a>1. 实现一个 Promise.all</h3><p><strong>题目</strong>：请手写实现一个 <code>Promise.all</code> 函数，该函数接收一个 Promise 对象的数组作为参数，并返回一个新的 Promise 实例。新的 Promise 实例在所有输入 Promise 都成功解决时解决，返回值是一个包含所有输入 Promise 解决值的数组。如果任何一个输入 Promise 被拒绝，新的 Promise 立即拒绝，拒绝的原因是第一个拒绝的 Promise 的原因。</p>
<pre><code class="js">function promiseAll(promises) {
let result = new Array(promises.length);
let success = 0;
return new Promise((resolve, reject) => {
promises.forEach((promise, index) => {
promise
.then((res) => {
result[index] = res;
success++;
if (success === promises.length) {
resolve(result);
}
})
.catch((e) => {
reject(e);
});
});
});
}
function promiseAllSettled(promises) {
let result = new Array(promises.length);
let count = 0;
return new Promise((resolve, reject) => {
promises.forEach((promise, index) => {
promise
.then((res) => {
result[index] = { state: "fulfilled", value: res };
count++;
if (count === promises.length) {
resolve(result);
}
})
.catch((err) => {
result[index] = { state: "rejected", err };
count++;
if (count === promises.length) {
resolve(result);
}
});
});
});
}
let p1 = new Promise((resolve, reject) => {
setTimeout(() => {
resolve("p1");
}, 1000);
});
let p2 = new Promise((resolve, reject) => {
setTimeout(() => {
resolve("p2");
}, 2000);
});
let p3 = new Promise((resolve, reject) => {
setTimeout(() => {
reject("p3");
}, 3000);
});
promiseAll([p1, p2, p3])
.then((res) => {
console.log(res);
})
.catch((err) => {
console.log(err);
});
promiseAllSettled([p1, p2, p3])
.then((res) => {
console.log(res);
})
.catch((err) => {
console.log(err);
});
</code></pre>
<h3 id="2-实现一个简单的路由"><a href="#2-实现一个简单的路由" class="headerlink" title="2. 实现一个简单的路由"></a>2. 实现一个简单的路由</h3><p><strong>题目</strong>：在不使用任何前端路由库的情况下，如何实现一个简单的前端路由（SPA）功能？请描述你的思路，并给出基本的实现代码。</p>
<h3 id="3-实现防抖（Debounce）函数"><a href="#3-实现防抖（Debounce）函数" class="headerlink" title="3. 实现防抖（Debounce）函数"></a>3. 实现防抖（Debounce）函数</h3><p><strong>题目</strong>：请实现一个防抖（Debounce）函数。防抖函数接收一个函数和等待时间作为参数，并返回一个新的函数。返回的新函数在被连续调用时，只有在等待时间过去后才会执行原函数，如果在等待时间内再次被调用，则重新计时。</p>
<pre><code class="js">function debounce(func, wait) {
let timeout = null;
return function () {
clearTimeout(timeout);
let arg = arguments;
let _this = this;
timeout = setTimeout(() => {
func.apply(_this, arg);
}, wait);
};
}
let add = (a, b) => {
console.log(a + b);
};
const debounceAdd = debounce(add, 1000);
setTimeout(() => {
debounceAdd(1, 2);
}, 200);
setTimeout(() => {
debounceAdd(1, 2);
}, 200);
</code></pre>
<h3 id="4-实现一个简单的模板引擎"><a href="#4-实现一个简单的模板引擎" class="headerlink" title="4. 实现一个简单的模板引擎"></a>4. 实现一个简单的模板引擎</h3><p><strong>题目</strong>：实现一个简单的模板引擎，它能够将类似于 <code>"Hello, {{name}}!"</code> 的模板字符串和一个对象如 <code>{name: "World"}</code> 作为输入，并输出 <code>"Hello, World!"</code>。请描述你的实现思路，并给出代码。</p>
<h3 id="5-CSS-垂直居中的方法"><a href="#5-CSS-垂直居中的方法" class="headerlink" title="5. CSS 垂直居中的方法"></a>5. CSS 垂直居中的方法</h3><p><strong>题目</strong>：请列举至少三种使得一个元素在其父元素中垂直居中的方法，并简要描述每种方法的原理和使用场景。</p>
<ul>
<li>深拷贝</li>
</ul>
<pre><code class="js">const deepClone = (obj) => {
if (obj === null || typeof obj !== "object") return obj;
let result = Array.isArray(obj) ? [] : {};
for (let key in obj) {
if (obj.hasOwnProperty(key)) {
if (obj[key] && typeof obj[key] === "object") {
result[key] = deepClone(obj[key]);
} else {
result[key] = obj[key];
}
}
}
};
</code></pre>
<ul>
<li>手写instanceOf</li>
</ul>
<pre><code class="js">const myInstance = (left, right) => {
if (left !== "object" || left === null) return false;
let proto = Object.getPrototypeOf(left);
while (proto) {
if (proto === right.prototype) return true;
proto = Object.getPrototypeOf(proto);
}
return false;
};
</code></pre>
<ul>
<li>手写new</li>
</ul>
<pre><code class="js">function myNew(fn, ...args) {
const obj = {};
obj.__proto__ = fn.prototype;
let result = fn.apply(fn, args);
return result instanceof Object ? result : obj;
}
</code></pre>
<ul>
<li>实现简单ajax</li>
</ul>
<pre><code class="js">function ajax(options) {
const xhr = new XMLHttpRequest();
options = options || {};
options.type = (options.type || "GET").toUpperCase();
options.dataType = options.dataType || "json";
const params = options.data;
if (options.type === "GET") {
xhr.open("GET", options.url + "?" + params, true);
xhr.send(null);
} else if (options.type === "POST") {
xhr.open("POST", options.url, true);
xhr.send(params);
}
xhr.onreadystatechange = function () {
if (xhr.readyState === 4) {
const status = xhr.status;
if (status >= 200 && status < 300) {
options.success && options.success(xhr.responseText, xhr.responseXML);
} else {
options.fail && options.fail(status);
}
}
};
}
ajax({
url: "http://localhost:3000/api",
type: "GET",
data: {
name: "zhangsan",
age: 18,
},
dataType: "json",
success: function (response, xml) {
console.log(response);
},
fail: function (status) {
console.log(status);
},
});
</code></pre>
<ul>
<li>函数柯里化</li>
</ul>
<pre><code class="js">const curry = function (fn) {
return function curried(...args) {
if (args.length > fn.length) {
return function () {
return curried(...args.concat([...arguments]));
};
}
return fn(...args);
};
};
</code></pre>
<ul>
<li>节流和防抖</li>
</ul>
<pre><code class="js">function debounce(func, wait) {
let timeout = null;
return function () {
let args = arguments;
let _this = this;
if (timeout) clearTimeout(timeout);
timeout = setTimeout(() => {
func.apply(_this, args);
}, wait);
};
}
function throttle(func, wait) {
let timeout = null;
return function () {
let args = arguments;
let _this = this;
if (!timeout) {
timeout = setTimeout(() => {
func.apply(_this, args);
timeout = null;
}, wait);
}
};
}
function throttle(func, wait) {
let oldtime = Date.now();
return function () {
let args = arguments;
let _this = this;
let newtime = Date.now();
if (newtime - oldtime >= wait) {
func.apply(_this, args);
oldtime = Date.now();
}
};
}
</code></pre>
<ul>
<li>并查集</li>
</ul>
<pre><code class="js">function createUnionFind(size) {
const parent = new Array(size).fill(0).map((_, i) => i);
function find(x) {
if (parent[x] === x) {
return x;
}
parent[x] = find(parent[x]);
return parent[x];
}
function union(x, y) {
let rootX = find(x);
let rootY = find(y);
if (rootX !== rootY) {
parent[rootX] = rootY;
}
}
function connected(x, y) {
return find(x) === find(y);
}
return {
find,
union,
connected,
};
}
</code></pre>
</div>
</div>
<div class="post-tags">
<span class="icon">
<a-icon type="tags" theme="filled" />
</span>
<span class="tag">
<a href="/tags/前端" style=color:#00bcd4>
前端
</a>
</span>
</div>
<a href="/随机面试题/ " class="go-post">
阅读全文
</a>
</div>
<div class="post">
<a href="/LeetCode-Hot100/">
<h2>
LeetCode Hot100
</h2>
</a>
<div class="category-and-date">
<span class="date">
<span class="icon">
<a-icon type="calendar" theme="filled" />
</span>
2024/2/26
</span>
</div>
<div class="excerpt">
<div class="content" v-pre>
<span id="more"></span>
<h3 id="哈希"><a href="#哈希" class="headerlink" title="哈希"></a>哈希</h3><ul>
<li>两数之和</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
let map = new Map();
for (let i = 0; i < nums.length; i++) {
map.set(nums[i], i);
}
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i]) && map.get(target - nums[i]) !== i) {
return [i, map.get(target - nums[i])];
}
}
};
</code></pre>
<ul>
<li>字母异位词</li>
</ul>
<pre><code class="js">/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
let map = new Map();
for (let str of strs) {
if (map.has(str.split("").sort().join(""))) {
map.get(str.split("").sort().join("")).push(str);
} else {
map.set(str.split("").sort().join(""), [str]);
}
}
return Array.from(map.values());
};
</code></pre>
<ul>
<li>最长连续序列(使用set和动态规划)</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
let set = new Set(nums);
let result = 0;
for (let num of nums) {
if (!set.has(num - 1)) {
let current = num;
let count = 1;
while (set.has(current + 1)) {
current++;
count++;
}
result = Math.max(result, count);
}
}
return result;
};
</code></pre>
<pre><code class="js">/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
if (nums.length == 0) {
return 0;
}
let dp = [];
let result = 1;
dp[0] = 1;
nums.sort((a, b) => a - b);
for (let i = 1; i < nums.length; i++) {
dp[i] = 1;
if (nums[i] == nums[i - 1]) {
dp[i] = dp[i - 1];
}
if (nums[i] == nums[i - 1] + 1) {
dp[i] = dp[i - 1] + 1;
}
result = Math.max(result, dp[i]);
}
return result;
};
</code></pre>
<h3 id="双指针"><a href="#双指针" class="headerlink" title="双指针"></a>双指针</h3><ul>
<li>移动零</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums) {
let a = 0;
let b = 0;
while (a < nums.length) {
if (nums[a] !== 0) {
nums[b] = nums[a];
b++;
}
a++;
}
while (b < nums.length) {
nums[b] = 0;
b++;
}
};
</code></pre>
<ul>
<li>盛最多水的容器(从两端往中间移动短板，因为多少水是由短板决定的，移动长板并不能改善)</li>
</ul>
<pre><code class="js">/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let result = 0;
let left = 0;
let right = height.length - 1;
while (left < right) {
result = Math.max(
result,
(right - left) * Math.min(height[left], height[right])
);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return result;
};
</code></pre>
<ul>
<li>三数之和</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
let result = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 2; i++) {
if (i === 0 || nums[i] !== nums[i - 1]) {
let sum = 0 - nums[i];
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] === sum) {
result.push([nums[i], nums[left], nums[right]]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) left++; // 跳过重复元素
while (left < right && nums[right] === nums[right + 1]) right--; // 跳过重复元素
} else if (nums[left] + nums[right] < sum) {
left++;
} else {
right--;
}
}
}
}
return result;
};
</code></pre>
<ul>
<li>接雨水(双指针，类似于打擂，永远是强者在台上)</li>
</ul>
<pre><code class="js">/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let result = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
result += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
result += rightMax - height[right];
}
right--;
}
}
return result;
};
</code></pre>
<h3 id="滑动窗口"><a href="#滑动窗口" class="headerlink" title="滑动窗口"></a>滑动窗口</h3><ul>
<li>无重复字符的最长字串</li>
</ul>
<pre><code class="js">/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let max = 0;
let start = 0;
let map = new Map();
for (let i = 0; i < s.length; i++) {
if (map.has(s[i])) {
start = Math.max(start, map.get(s[i]) + 1);
}
max = Math.max(max, i - start + 1);
map.set(s[i], i);
}
return max;
};
</code></pre>
<ul>
<li>找到字符串中所有的字母异位词</li>
</ul>
<pre><code class="js">/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function (s, p) {
if (s.length < p.length) return [];
let result = [];
let pMap = new Array(26).fill(0);
let sMap = new Array(26).fill(0);
for (let i = 0; i < p.length; i++) {
sMap[s.charCodeAt(i) - 97]++;
pMap[p.charCodeAt(i) - 97]++;
}
for (let i = 0; i <= s.length - p.length; i++) {
if (sMap.join("") === pMap.join("")) result.push(i);
sMap[s.charCodeAt(i) - 97]--;
sMap[s.charCodeAt(i + p.length) - 97]++;
}
return result;
};
</code></pre>
<h3 id="子串"><a href="#子串" class="headerlink" title="子串"></a>子串</h3><ul>
<li>和为k的子数组(前缀和优化)</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function (nums, k) {
let result = 0;
let sum = 0;
let map = new Map();
map.set(0, 1);
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
result += map.get(sum - k) || 0;
map.set(sum, (map.get(sum) || 0) + 1);
}
return result;
};
</code></pre>
<ul>
<li>滑动窗口最大值(单调队列-双端队列)</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
const q = [];
const result = [];
for (let i = 0; i < k; i++) {
while (q.length && nums[q[q.length - 1]] <= nums[i]) {
q.pop();
}
q.push(i);
}
result.push(nums[q[0]]);
for (let i = k; i < nums.length; i++) {
while (q.length && nums[i] >= nums[q[q.length - 1]]) {
q.pop();
}
q.push(i);
while (q[0] <= i - k) {
q.shift();
}
result.push(nums[q[0]]);
}
return result;
};
</code></pre>
<h3 id="普通数组"><a href="#普通数组" class="headerlink" title="普通数组"></a>普通数组</h3><ul>
<li>最大子数组和(类似于dp，当和小于0的时候就丢弃)</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
let max = nums[0];
let sum = 0;
for (let i = 0; i < nums.length; i++) {
if (sum < 0) {
sum = 0;
}
sum += nums[i];
max = Math.max(max, sum);
}
return max;
};
</code></pre>
<ul>
<li>合并区间（排序）</li>
</ul>
<pre><code class="js">/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function (intervals) {
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 0; i < intervals.length - 1; i++) {
if (intervals[i][1] >= intervals[i + 1][0]) {
intervals[i][1] = Math.max(intervals[i][1], intervals[i + 1][1]);
intervals.splice(i + 1, 1);
i--;
}
}
return intervals;
};
</code></pre>
<ul>
<li>轮转数组(注意处理k大于数组长度的情况)</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function (nums, k) {
k = k % nums.length;
nums.unshift(...nums.slice(nums.length - k));
nums.splice(nums.length - k, k);
};
</code></pre>
<ul>
<li>除自身以外数组的乘积(前缀乘积和后缀乘积)</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function (nums) {
let pre = new Array(nums.length).fill(1);
let post = new Array(nums.length).fill(1);
let result = [];
pre[0] = nums[0];
for (let i = 1; i < nums.length; i++) {
pre[i] = pre[i - 1] * nums[i];
}
post[nums.length - 1] = nums[nums.length - 1];
for (let i = nums.length - 2; i >= 0; i--) {
post[i] = post[i + 1] * nums[i];
}
for (let i = 0; i < nums.length; i++) {
result.push(
i === 0
? post[i + 1]
: i === nums.length - 1
? pre[i - 1]
: pre[i - 1] * post[i + 1]
);
}
return result;
};
</code></pre>
<ul>
<li>空间复杂度为o(1) ，利用输出数组作为后缀乘积</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function (nums) {
let post = new Array(nums.length).fill(1);
post[nums.length - 1] = nums[nums.length - 1];
for (let i = nums.length - 2; i >= 0; i--) {
post[i] = post[i + 1] * nums[i];
}
let pre = 1;
for (let i = 0; i < nums.length - 1; i++) {
post[i] = post[i + 1] * pre;
pre *= nums[i];
}
post[nums.length - 1] = pre;
return post;
};
</code></pre>
<ul>
<li>缺失的第一个正数(将现有数组想办法当成hash表)</li>
</ul>
<pre><code class="js">/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function (nums) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] < 1 || nums[i] > nums.length) {
nums[i] = Infinity;
}
}
for (let i = 0; i < nums.length; i++) {
if (
nums[i] < Infinity &&
nums[i] > -Infinity &&
nums[Math.abs(nums[i]) - 1] > 0
) {
nums[Math.abs(nums[i]) - 1] = -nums[Math.abs(nums[i]) - 1];
}
}
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return nums.length + 1;
};
</code></pre>
<h3 id="矩阵"><a href="#矩阵" class="headerlink" title="矩阵"></a>矩阵</h3><ul>
<li>矩阵置零</li>
</ul>
<pre><code class="js">/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function (matrix) {
let m = matrix.length;
let n = matrix[0].length;
for (let i = 0; i < m; i++) {
if (matrix[i].includes(0)) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] !== 0) {
matrix[i][j] = "x";
} else {
for (let k = 0; k < m; k++) {
if (matrix[k][j] !== 0) {
matrix[k][j] = "x";
}
}
}
}
}
}