报数、反转字符串和字符串中的第一个唯一字符

报数

报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:
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)
    本算法涉及递归,代码的调用次数为
    nn
    次。故而时间复杂度为
    O(n)O(n)
  • 空间复杂度:
    O(n)O(n)
    递归算法,调用次数随
    nn
    增加而成线性增加,每次调用申明变量数相同。故而空间复杂度为
    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)
    本算法代码的调用次数为
    nn
    次。故而时间复杂度为
    O(n)O(n)
  • 空间复杂度:
    O(1)O(1)
    申明对象数量为固定值。空间复杂度为常量
    O(1)O(1)

反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用
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. 1.
    设置变量 i = 0
  2. 2.
    替换字符串的第i位和倒数第 i 位,替换方式:使用es6的解构赋值进行变量的交换;
  3. 3.
    变量 i + 1,继续替换替换字符串的第 i 位和倒数第 i 位;
  4. 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(1)O(1)
    没有新开辟的内存空间

方法二 中间变量首尾替换法

思路
中间变量首尾替换法,逐位遍历,进行交换
详解
  1. 1.
    设置变量 i = 0
  2. 2.
    替换字符串的第i位和倒数第i位,替换方式:设置一个中间变量,替换两个字符串的值;
  3. 3.
    变量 i + 1,继续替换替换字符串的第i位和倒数第i位;
  4. 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)
    遍历次数:如果字符串长度为
    nn
    nn
    是偶数,遍历次数位
    n/2n/2
    ,如果
    nn
    是奇数,遍历次数为
    (n+1)/2(n+1)/2
  • 空间复杂度:
    O(1)O(1)
    1个临时变量

字符串中的第一个唯一字符

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
示例
1
s = "leetcode"
2
返回 0.
3
4
s = "loveleetcode",
5
返回 2.
Copied!
注意事项:您可以假定该字符串只包含小写字母。

方法一 库函数

思路
某个字符从头开始开始的索引和从尾开始找的索引如果相等,就说明这个字符只出现了一次
详解
  1. 1.
    从头到尾遍历一遍字段串;
  2. 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(n2)O(n^2)
    外层遍历,时间复杂度为
    O(n)O(n)
    ,调用 indexOf 的复杂度为
    O(n)O(n)
    ,得出总的时间复杂度为
    O(n2)O(n^2)
  • 空间复杂度:
    O(1)O(1)
    因为除了临时变量 i,没有开辟额外的空间

方法二 哈希

思路
遍历两次。第一次遍历,用一个哈希对象记录所有字符的出现次数;第二次遍历,找出哈希对象中只出现一次的字符的下标
详解
  1. 1.
    第一次遍历,用一个哈希对象记录所有字符的出现次数;
  2. 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)
    因为变量只有 hashi,开辟空间大小不随输入的变量变化
  • 时间复杂度:
    O(n)O(n)
    因为有两次遍历,且每次遍历都只有一层没有嵌套,所以遍历的次数只和入参字符串 s 的长度线性正相关
最近更新 1yr ago