报数、反转字符串和字符串中的第一个唯一字符
报数
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
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!
复杂度分析
- 时间复杂度：本算法涉及递归，代码的调用次数为次。故而时间复杂度为。
- 空间复杂度：递归算法，调用次数随增加而成线性增加，每次调用申明变量数相同。故而空间复杂度为。
方法二 循环法
递归法是由 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!
复杂度分析
- 时间复杂度：本算法代码的调用次数为次。故而时间复杂度为。
- 空间复杂度：申明对象数量为固定值。空间复杂度为常量。
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用
的额外空间解决这一问题。
你可以假设数组中的所有字符都是 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!
复杂度分析
- 时间复杂度：
- 空间复杂度：没有新开辟的内存空间
方法二 中间变量首尾替换法
思路
中间变量首尾替换法，逐位遍历，进行交换
详解
- 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!
复杂度分析
- 时间复杂度：遍历次数：如果字符串长度为，是偶数，遍历次数位，如果是奇数，遍历次数为
- 空间复杂度：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!
复杂度分析
- 时间复杂度：外层遍历，时间复杂度为，调用
indexOf的复杂度为，得出总的时间复杂度为 - 空间复杂度：因为除了临时变量
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!
复杂度分析
- 空间复杂度：因为变量只有
hash和i，开辟空间大小不随输入的变量变化 - 时间复杂度：因为有两次遍历，且每次遍历都只有一层没有嵌套，所以遍历的次数只和入参字符串
s的长度线性正相关
最近更新 1yr ago
复制链接