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

报数

报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:

1. 1
2. 11
3. 21
4. 1211
5. 111221

1 被读作 "one 1" ("一个一") , 即 11。 11 被读作 "two 1s" ("两个一"), 即 21。 21 被读作 "one 2", "one 1" ("一个二" , "一个一") , 即 1211。

给定一个正整数 n(1 ≤ n ≤ 30),输出报数序列的第 n 项。

注意:整数顺序将表示为一个字符串。 示例

输入: 1
输出: "1"
输入: 4
输出: "1211"

方法一 递归

想要获取第 n 项的结果,需要先获取到第 n-1 项的结果,然后报出第 n-1 项的结果做为第 n 项的结果。所以可以采用递归调用法。

const countAndSay = function (n) {
if (n === 1) {
return '1';
}
const preResult = countAndSay(n - 1); // 获取第 n-1 项的结果。
/**
* \d 匹配一个数字
* \1 匹配前面第一个括号内匹配到的内容
* (\d)\1* 匹配相邻数字相同的内容
* 使用replace方法将匹配到的内容处理为长度 + 内容的第一个字符
* 结果为所求报数
**/
return preResult.replace(/(\d)\1*/g, item => `${item.length}${item[0]}`);
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    本算法涉及递归,代码的调用次数为 nn 次。故而时间复杂度为O(n)O(n)

  • 空间复杂度:O(n)O(n)

    递归算法,调用次数随 nn 增加而成线性增加,每次调用申明变量数相同。故而空间复杂度为O(n)O(n)

方法二 循环法

递归法是由 n 到 1 计算相应的值并层层返回的,循环法正好相反,循环法由 1 计算到 n。然后将最终值返回。

const countAndSay = function (n) {
let result = '1'; // 第一个数为'1'
for (let i = 1; i < n; i++) { // 循环获取知道第 n 项。
// 同方法一
result = result.replace(/(\d)\1*/g, item => `${item.length}${item[0]}`);
}
return result;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    本算法代码的调用次数为 nn 次。故而时间复杂度为O(n)O(n)

  • 空间复杂度:O(1)O(1)

    申明对象数量为固定值。空间复杂度为常量O(1)O(1)

反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1)O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例1

输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例2

输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

方法一 首尾替换法

思路

首尾替换法,逐位遍历,进行交换

详解

  1. 设置变量 i = 0

  2. 替换字符串的第i位和倒数第 i 位,替换方式:使用es6的解构赋值进行变量的交换;

  3. 变量 i + 1,继续替换替换字符串的第 i 位和倒数第 i 位;

  4. 直到 i 大于字符串s的长度的中位数,完成真个字符串的反转

/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
const reverseString = function (s) {
for (let i = 0; i < s.length / 2; i++) {
[s[i], s[s.length - 1 - i]] = [s[s.length - 1 - i], s[i]];
}
return s;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

  • 空间复杂度:O(1)O(1)

    没有新开辟的内存空间

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

思路

中间变量首尾替换法,逐位遍历,进行交换

详解

  1. 设置变量 i = 0

  2. 替换字符串的第i位和倒数第i位,替换方式:设置一个中间变量,替换两个字符串的值;

  3. 变量 i + 1,继续替换替换字符串的第i位和倒数第i位;

  4. 直到i大于字符串s的长度的中位数,完成真个字符串的反转

/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
const reverseString = function (s) {
for (let i = 0; i < s.length / 2; i++) {
const a = s[i];
s[i] = s[s.length - i - 1];
s[s.length - i - 1] = a;
}
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    遍历次数:如果字符串长度为nnnn是偶数,遍历次数位 n/2n/2 ,如果nn是奇数,遍历次数为 (n+1)/2(n+1)/2

  • 空间复杂度:O(1)O(1)

    1个临时变量

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

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

示例

s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.

注意事项:您可以假定该字符串只包含小写字母。

方法一 库函数

思路

某个字符从头开始开始的索引和从尾开始找的索引如果相等,就说明这个字符只出现了一次

详解

  1. 从头到尾遍历一遍字段串;

  2. 判断每个位置的字符的 index()lastIndexOf() 的结果是否相等;

代码

/**
* @param {string} s
* @return {number}
*/
const firstUniqChar = function (s) {
for (let i = 0; i < s.length; i += 1) {
if (s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
return i;
}
}
return -1;
};

复杂度分析

  • 时间复杂度: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. 第一次遍历,用一个哈希对象记录所有字符的出现次数;

  2. 第二次遍历,找出哈希对象中只出现一次的字符的下标;

代码

/**
* @param {string} s
* @return {number}
*/
const firstUniqChar = function (s) {
const hash = {};
for (let i = 0; i < s.length; i += 1) {
if (!hash[s[i]]) {
hash[s[i]] = 1;
} else {
hash[s[i]] += 1;
}
}
for (let i = 0; i < s.length; i += 1) {
if (hash[s[i]] === 1) {
return i;
}
}
return -1;
};

复杂度分析

  • 空间复杂度:O(1)O(1)

    因为变量只有 hashi,开辟空间大小不随输入的变量变化

  • 时间复杂度:O(n)O(n)

    因为有两次遍历,且每次遍历都只有一层没有嵌套,所以遍历的次数只和入参字符串 s 的长度线性正相关