-
Notifications
You must be signed in to change notification settings - Fork 895
/
algorithm.md
executable file
·538 lines (335 loc) · 15.9 KB
/
algorithm.md
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
# 算法题目汇总
- [合并二维有序数组成一维有序数组,归并排序的思路](#合并二维有序数组成一维有序数组归并排序的思路)
- [多种方式实现斐波那契数列](#多种方式实现斐波那契数列)
- [字符串出现的不重复最长长度](#字符串出现的不重复最长长度)
- [有一堆整数,请把他们分成三份,确保每一份和尽量相等(11,42,23,4,5,6 4 5 6 11 23 42 56 78 90)](#有一堆整数请把他们分成三份确保每一份和尽量相等114223456-4-5-6-11-23-42-56-78-90)
- [[实操题]输入一条 polyline,输出 polyline 的中点](#实操题输入一条-polyline输出-polyline-的中点)
- [单向链表实现队列](#单向链表实现队列)
- [将给定的数组从顶级分类递归查找子分类,最终构建一个树状数组](#将给定的数组从顶级分类递归查找子分类最终构建一个树状数组)
- [实现一个将 52 张牌随机均等的分给四个人,比如输入 [0,1,2,3....51] ,输出[[1,2,16...],[4,3,6..],[....],[....]]](#实现一个将-52-张牌随机均等的分给四个人比如输入-012351-输出1216436)
- [按要求实现 rightView 函数](#按要求实现-rightview-函数)
- [二叉树序列化反序列化](#二叉树序列化反序列化)
- [输入一个数字,找到对应的字母](#输入一个数字找到对应的字母)
- [Given an int n, output Mausoleum Array solutions.](#given-an-int-n-output-mausoleum-array-solutions)
- [给一个字符串比如'abca',返回第一个不重复的字母](#给一个字符串比如abca返回第一个不重复的字母)
- [给定⼀个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效.](#给定个只包括--的字符串判断字符串是否有效)
- [手动实现一个函数,给定一个数组[1,0,2,3,4,-1,-3],输出任意两个值和为 0 的下标](#手动实现一个函数给定一个数组10234-1-3输出任意两个值和为-0-的下标)
- [介绍排序算法和快排原理](#介绍排序算法和快排原理)
- [一个人每次只能走一层楼梯或者两层楼梯,问走到第 80 层楼梯一共有多少种方法](#一个人每次只能走一层楼梯或者两层楼梯问走到第-80-层楼梯一共有多少种方法)
- [给定一个数组,形如 [1, 1, 2 , 3, 3, 3, 3, 4, 6, 6],给定一个数 n,例如 3,找出给定的数 n 在数组内出现的次数,要求时间复杂度小于 O(n)](#给定一个数组形如-1-1-2--3-3-3-3-4-6-6给定一个数-n例如-3找出给定的数-n-在数组内出现的次数要求时间复杂度小于-on)
- [现在有随机整数数组,例如[2,11,20,160,3,1...],请挑出数组内,三个随机整数和为 100 的所有数据。](#现在有随机整数数组例如2112016031请挑出数组内三个随机整数和为-100-的所有数据)
- [统计一组整形数组的最大差值?](#统计一组整形数组的最大差值)
- [介绍冒泡排序、选择排序,说说冒泡排序如何优化](#介绍冒泡排序选择排序说说冒泡排序如何优化)
- [如何判断链表是否有环](#如何判断链表是否有环)
- [介绍二叉搜索树的特点](#介绍二叉搜索树的特点)
- [手写数组去重函数(至少三种以上,说明时间复杂度)](#手写数组去重函数至少三种以上说明时间复杂度)
- [找到前 K 个最大的元素](#找到前-k-个最大的元素)
- [介绍下 DFS 深度优先](#介绍下-dfs-深度优先)
- [递归公式的时间复杂度为?(单选题)](#递归公式的时间复杂度为单选题)
- [用 JavaScript 实现一个标准的排序算法(快排、冒泡、选择排序),对某个数字数组进行由低到高的排序。](#用-javascript-实现一个标准的排序算法快排冒泡选择排序对某个数字数组进行由低到高的排序)
- [找出“aaaabbcccdddd”字符串中出现最多的字母?](#找出aaaabbcccdddd字符串中出现最多的字母)
- [求 n 以内的所有素数,并说明时间复杂度](#求-n-以内的所有素数并说明时间复杂度)
- [给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点](#给定一个二叉树找出其最大深度二叉树的深度为根节点到最远叶子节点的最长路径上的节点数说明-叶子节点是指没有子节点的节点)
- [给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和](#给定一个整数数组-nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和)
- [算法考察:Next Permutation](#算法考察next-permutation)
- [按要求实现代码](#按要求实现代码)
- [找出两个数组的交集元素](#找出两个数组的交集元素)
- [输入一个整数,输出该数二进制表示中 1 的个数](#输入一个整数输出该数二进制表示中-1-的个数)
- [⽤ js 实现随机选取 10–100 之间的 10 个且不重复的数字,存⼊⼀个数组,还要排序](#-js-实现随机选取-10100-之间的-10-个且不重复的数字存个数组还要排序)
- [请用算法实现,从给定的无序、不重复的数组data中,取出n个数,使其相加和为sum。并给出算法的时间/空间复杂度。(不需要找到所有的解,找到一个解即可)](#请用算法实现从给定的无序不重复的数组data中取出n个数使其相加和为sum并给出算法的时间空间复杂度不需要找到所有的解找到一个解即可)
### 合并二维有序数组成一维有序数组,归并排序的思路
公司:头条
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/8)
<br/>
### 多种方式实现斐波那契数列
公司:腾讯、CVTE、微软
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/9)
<br/>
### 字符串出现的不重复最长长度
公司:腾讯
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/10)
<br/>
### 有一堆整数,请把他们分成三份,确保每一份和尽量相等(11,42,23,4,5,6 4 5 6 11 23 42 56 78 90)
公司:滴滴
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/19)
<br/>
### [实操题]输入一条 polyline,输出 polyline 的中点
题目补充:
```js
算法:输入一条polyline,输出polyline的中点
绘制:在浏览器中绘制出polyline和中点
说明:中点是指沿着polyline,到polyline的起点和终点,距离相等,中点要求在polyline上
输入:[[10, 20], [20, 200], [30, 220], [40, 300], [100, 400]],以[10, 20]举例,10代表x坐标,20代表y坐标,单位是像素
要求:提供源代码,用原生JavaScript实现,不使用任何框架、类库、构建工具,本地打开html文件可直接看到效果
```
公司:腾讯
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/240)
<br/>
### 单向链表实现队列
公司:头条
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/214)
<br/>
### 将给定的数组从顶级分类递归查找子分类,最终构建一个树状数组
```js
/*
*数组:[{id:1, parentId: 0}, {id:2, parentId:1},{id:3, parentId:1}]
*输出结果:[{id:1, parentId: 0,children:[{id:2, parentId:1},{id:3, parentId:1}]}]
*说明:parentId为0 的是根节点
*/
```
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/212)
<br/>
### 实现一个将 52 张牌随机均等的分给四个人,比如输入 [0,1,2,3....51] ,输出[[1,2,16...],[4,3,6..],[....],[....]]
公司:顺丰
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/157)
<br/>
### 按要求实现 rightView 函数
```js
function TreeNode(val){
this.val = val;
this.left = null;
this.right = null;
}
function rightView(root){
// 请你实现
}
// => [1,4,3]
1 => 1
2 4 => 4
7 3 => 3
```
公司:头条
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/140)
<br/>
### 二叉树序列化反序列化
公司:微软
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/346)
<br/>
### 输入一个数字,找到对应的字母
```js
/*
如输入1 返回a
输入26返回z
输入27返回aa
输入28返回ab
输入53返回aaa
*/
```
公司:微软
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/345)
<br/>
### Given an int n, output Mausoleum Array solutions.
```js
// Given an int n, output Mausoleum Array solutions.
// Mausoleum Array:
// Construct by 1,1,2,2,3,3,…,n-1,n-1,n,n
// first were non-decreasing (i.e., increasing or remained the same), and then — non-increasing (decrease or remained unchanged).
// Mausoleum Array example:
// [1, 2, 2, 3, 4, 4, 3, 1];
// [1, 1];
// [2, 2, 1, 1];
// [1, 2, 3, 3, 2, 1].
// input/output example:
// n=1, [1,1]
// n=2, [1,1,2,2],[1,2,2,1],[2,2,1,1]
// n = 3,[3, 3, 2, 2, 1, 1],[2, 3, 3, 2, 1, 1],[2, 2, 3, 3, 1, 1],[1, 3, 3, 2, 2, 1],[1, 2, 3, 3, 2, 1],[1, 2, 2, 3, 3, 1],[1, 1, 3, 3, 2, 2],[1, 1, 2, 3, 3, 2],[1, 1, 2, 2, 3, 3]
```
公司:微软
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/344)
<br/>
### 给一个字符串比如'abca',返回第一个不重复的字母
公司:易车
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/334)
<br/>
### 给定⼀个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效.
```js
/*
有效字符串需满⾜:
1. 左括号必须⽤相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例1:
输⼊: "()"
输出: true
示例2:
输⼊: "()[]{}"
输出: true
示例 3:
输⼊: "(]"
输出: false
示例 4:
输⼊: "([)]"
输出: false
示例 5:
输⼊: "{[]}"
输出: true
*/
```
公司:新东方
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/327)
<br/>
### 手动实现一个函数,给定一个数组[1,0,2,3,4,-1,-3],输出任意两个值和为 0 的下标
公司:滴滴
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/321)
<br/>
### 介绍排序算法和快排原理
公司:寺库、百分点
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/314)
<br/>
### 一个人每次只能走一层楼梯或者两层楼梯,问走到第 80 层楼梯一共有多少种方法
公司:快手
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/291)
<br/>
### 给定一个数组,形如 [1, 1, 2 , 3, 3, 3, 3, 4, 6, 6],给定一个数 n,例如 3,找出给定的数 n 在数组内出现的次数,要求时间复杂度小于 O(n)
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/243)
<br/>
### 现在有随机整数数组,例如[2,11,20,160,3,1...],请挑出数组内,三个随机整数和为 100 的所有数据。
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/388)
<br/>
### 统计一组整形数组的最大差值?
公司:心娱
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/365)
<br/>
### 介绍冒泡排序、选择排序,说说冒泡排序如何优化
公司:有赞
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/492)
<br/>
### 如何判断链表是否有环
公司:有赞
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/490)
<br/>
### 介绍二叉搜索树的特点
公司:有赞
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/489)
<br/>
### 手写数组去重函数(至少三种以上,说明时间复杂度)
公司:携程、心娱
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/443)
<br/>
### 找到前 K 个最大的元素
公司:百分点
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/746)
<br/>
### 介绍下 DFS 深度优先
公司:海风教育
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/739)
<br/>
### 递归公式的时间复杂度为?(单选题)
```js
A.O(n)
B.O(logn)
C.O(nlogn)
D.O(n2)
```
公司:会小二
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/693)
<br/>
### 用 JavaScript 实现一个标准的排序算法(快排、冒泡、选择排序),对某个数字数组进行由低到高的排序。
公司:会小二
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/686)
<br/>
### 找出“aaaabbcccdddd”字符串中出现最多的字母?
公司:心娱
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/675)
<br/>
### 求 n 以内的所有素数,并说明时间复杂度
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/667)
<br/>
### 给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点
公司:头条
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/626)
<br/>
### 给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和
公司:头条
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/625)
<br/>
### 算法考察:Next Permutation
```js
/*
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
*/
```
公司:爱范儿
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/845)
<br/>
### 按要求实现代码
```js
/*
根据传入参数n(数字)对一维数组(纯数字)按照距离n最近的顺序排序。(距离即数字与n的差值的绝对值)
*/
var arr = [7, 28, -1, 0, 7, 33];
function sort(n) {
// your code
}
```
公司:高思教育
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/821)
<br/>
### 找出两个数组的交集元素
公司:乘法云
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/806)
<br/>
### 输入一个整数,输出该数二进制表示中 1 的个数
公司:新东方
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/798)
<br/>
### ⽤ js 实现随机选取 10–100 之间的 10 个且不重复的数字,存⼊⼀个数组,还要排序
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/795)
<br/>
### 请用算法实现,从给定的无序、不重复的数组data中,取出n个数,使其相加和为sum。并给出算法的时间/空间复杂度。(不需要找到所有的解,找到一个解即可)
```js
function getResult(data,n,sum){
// your code
}
```
公司:头条
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/902)
<br/>
### 给定⼀个⼤⼩为 n 的数组,找到其中的众数。众数是指在数组中出现次数⼤于 n/2 的元素
分类:算法
[答案&解析](https://github.com/lgwebdream/FE-Interview/issues/789)
<br/>