面试助力，算法 101：JavaScript 描述
搜索文档…
面试助力，算法 101：JavaScript 描述
目录
写在前面
学习指南
开篇——复杂度
字符串
翻转整数、有效的字母异位词和翻转整数
报数、反转字符串和字符串中的第一个唯一字符
验证回文字符串、实现 strStr() 、最长公共前缀和最长回文子串
数学
数组
链表
二叉树
动态规划
回溯算法
排序与搜索
栈和队列
结束篇
由
GitBook
提供支持
报数、反转字符串和字符串中的第一个唯一字符
报数
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1
1. 1
2
2. 11
3
3. 21
4
4. 1211
5
5. 111221
Copied!
1 被读作 "one 1" ("一个一") , 即 11。 11 被读作 "two 1s" ("两个一"）, 即 21。 21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
示例
1
输入: 1
2
输出: "1"
Copied!
1
输入: 4
2
输出: "1211"
Copied!
方法一 递归
想要获取第 n 项的结果，需要先获取到第 n-1 项的结果，然后报出第 n-1 项的结果做为第 n 项的结果。所以可以采用递归调用法。
1
const
countAndSay
=
function
(
n
)
{
2
if
(
n
===
1
)
{
3
return
'1'
;
4
}
5
const
preResult
=
countAndSay
(
n
-
1
);
// 获取第 n-1 项的结果。
6
/**
7
* \d 匹配一个数字
8
* \1 匹配前面第一个括号内匹配到的内容
9
* (\d)\1* 匹配相邻数字相同的内容
10
* 使用replace方法将匹配到的内容处理为长度 + 内容的第一个字符
11
* 结果为所求报数
12
**/
13
return
preResult
.
replace
(
/
(\d)\1*
/
g
,
item
=>
`
${
item
.
length
}${
item
[
0
]
}
`
);
14
};
Copied!
复杂度分析
时间复杂度：
O
(
n
)
O(n)
O
(
n
)
本算法涉及递归，代码的调用次数为
n
n
n
次。故而时间复杂度为
O
(
n
)
O(n)
O
(
n
)
。
空间复杂度：
O
(
n
)
O(n)
O
(
n
)
递归算法，调用次数随
n
n
n
增加而成线性增加，每次调用申明变量数相同。故而空间复杂度为
O
(
n
)
O(n)
O
(
n
)
。
方法二 循环法
递归法是由 n 到 1 计算相应的值并层层返回的，循环法正好相反，循环法由 1 计算到 n。然后将最终值返回。
1
const
countAndSay
=
function
(
n
)
{
2
let
result
=
'1'
;
// 第一个数为'1'
3
for
(
let
i
=
1
;
i
<
n
;
i
++
)
{
// 循环获取知道第 n 项。
4
// 同方法一
5
result
=
result
.
replace
(
/
(\d)\1*
/
g
,
item
=>
`
${
item
.
length
}${
item
[
0
]
}
`
);
6
}
7
return
result
;
8
};
Copied!
复杂度分析
时间复杂度：
O
(
n
)
O(n)
O
(
n
)
本算法代码的调用次数为
n
n
n
次。故而时间复杂度为
O
(
n
)
O(n)
O
(
n
)
。
空间复杂度：
O
(
1
)
O(1)
O
(
1
)
申明对象数量为固定值。空间复杂度为常量
O
(
1
)
O(1)
O
(
1
)
。
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用
O
(
1
)
O(1)
O
(
1
)
的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例1
1
输入：["h","e","l","l","o"]
2
输出：["o","l","l","e","h"]
Copied!
示例2
1
输入：["H","a","n","n","a","h"]
2
输出：["h","a","n","n","a","H"]
Copied!
方法一 首尾替换法
思路
首尾替换法，逐位遍历，进行交换
详解
1.
设置变量
i = 0
；
2.
替换字符串的第i位和倒数第
i
位，替换方式：使用es6的解构赋值进行变量的交换；
3.
变量
i + 1
，继续替换替换字符串的第
i
位和倒数第
i
位；
4.
直到
i
大于字符串s的长度的中位数，完成真个字符串的反转
1
/**
2
* @param {character[]} s
3
* @return {void} Do not return anything, modify s in-place instead.
4
*/
5
const
reverseString
=
function
(
s
)
{
6
for
(
let
i
=
0
;
i
<
s
.
length
/
2
;
i
++
)
{
7
[
s
[
i
],
s
[
s
.
length
-
1
-
i
]]
=
[
s
[
s
.
length
-
1
-
i
],
s
[
i
]];
8
}
9
return
s
;
10
};
Copied!
复杂度分析
时间复杂度：
O
(
n
)
O(n)
O
(
n
)
空间复杂度：
O
(
1
)
O(1)
O
(
1
)
没有新开辟的内存空间
方法二 中间变量首尾替换法
思路
中间变量首尾替换法，逐位遍历，进行交换
详解
1.
设置变量
i = 0
；
2.
替换字符串的第i位和倒数第i位，替换方式：设置一个中间变量，替换两个字符串的值；
3.
变量
i + 1
，继续替换替换字符串的第i位和倒数第i位；
4.
直到i大于字符串s的长度的中位数，完成真个字符串的反转
1
/**
2
* @param {character[]} s
3
* @return {void} Do not return anything, modify s in-place instead.
4
*/
5
const
reverseString
=
function
(
s
)
{
6
for
(
let
i
=
0
;
i
<
s
.
length
/
2
;
i
++
)
{
7
const
a
=
s
[
i
];
8
s
[
i
]
=
s
[
s
.
length
-
i
-
1
];
9
s
[
s
.
length
-
i
-
1
]
=
a
;
10
}
11
};
Copied!
复杂度分析
时间复杂度：
O
(
n
)
O(n)
O
(
n
)
遍历次数：如果字符串长度为
n
n
n
，
n
n
n
是偶数，遍历次数位
n
/
2
n/2
n
/2
，如果
n
n
n
是奇数，遍历次数为
(
n
+
1
)
/
2
(n+1)/2
(
n
+
1
)
/2
空间复杂度：
O
(
1
)
O(1)
O
(
1
)
1个临时变量
字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例
1
s = "leetcode"
2
返回 0.
3
4
s = "loveleetcode",
5
返回 2.
Copied!
注意事项
：您可以假定该字符串只包含小写字母。
方法一 库函数
思路
某个字符从头开始开始的索引和从尾开始找的索引如果相等，就说明这个字符只出现了一次
详解
1.
从头到尾遍历一遍字段串；
2.
判断每个位置的字符的
index()
和
lastIndexOf()
的结果是否相等；
代码
1
/**
2
* @param {string} s
3
* @return {number}
4
*/
5
const
firstUniqChar
=
function
(
s
)
{
6
for
(
let
i
=
0
;
i
<
s
.
length
;
i
+=
1
)
{
7
if
(
s
.
indexOf
(
s
[
i
])
===
s
.
lastIndexOf
(
s
[
i
]))
{
8
return
i
;
9
}
10
}
11
return
-
1
;
12
};
Copied!
复杂度分析
时间复杂度：
O
(
n
2
)
O(n^2)
O
(
n
2
)
外层遍历，时间复杂度为
O
(
n
)
O(n)
O
(
n
)
，调用
indexOf
的复杂度为
O
(
n
)
O(n)
O
(
n
)
，得出总的时间复杂度为
O
(
n
2
)
O(n^2)
O
(
n
2
)
空间复杂度：
O
(
1
)
O(1)
O
(
1
)
因为除了临时变量
i
，没有开辟额外的空间
方法二 哈希
思路
遍历两次。第一次遍历，用一个哈希对象记录所有字符的出现次数；第二次遍历，找出哈希对象中只出现一次的字符的下标
详解
1.
第一次遍历，用一个哈希对象记录所有字符的出现次数；
2.
第二次遍历，找出哈希对象中只出现一次的字符的下标；
代码
1
/**
2
* @param {string} s
3
* @return {number}
4
*/
5
const
firstUniqChar
=
function
(
s
)
{
6
const
hash
=
{};
7
for
(
let
i
=
0
;
i
<
s
.
length
;
i
+=
1
)
{
8
if
(
!
hash
[
s
[
i
]])
{
9
hash
[
s
[
i
]]
=
1
;
10
}
else
{
11
hash
[
s
[
i
]]
+=
1
;
12
}
13
}
14
for
(
let
i
=
0
;
i
<
s
.
length
;
i
+=
1
)
{
15
if
(
hash
[
s
[
i
]]
===
1
)
{
16
return
i
;
17
}
18
}
19
return
-
1
;
20
};
Copied!
复杂度分析
空间复杂度：
O
(
1
)
O(1)
O
(
1
)
因为变量只有
hash
和
i
，开辟空间大小不随输入的变量变化
时间复杂度：
O
(
n
)
O(n)
O
(
n
)
因为有两次遍历，且每次遍历都只有一层没有嵌套，所以遍历的次数只和入参字符串
s
的长度线性正相关
以前
翻转整数、有效的字母异位词和翻转整数
下一个
验证回文字符串、实现 strStr() 、最长公共前缀和最长回文子串
最近更新
2yr ago
复制链接
内容
报数
反转字符串
字符串中的第一个唯一字符