翻转整数、有效的字母异位词和翻转整数

翻转整数

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例
1
示例 1:
2
输入: 123
3
输出: 321
4
5
示例 2:
6
输入: -123
7
输出: -321
8
9
示例 3:
10
输入: 120
11
输出: 21
Copied!
注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为
[231,2311][−2^{31}, 2^{31} − 1]
。请根据这个假设,如果反转后整数溢出那么就返回 0。

方法一 翻转字符串方法

思路
如果将数字看成是有符号位的字符串,那么我们就能够通过使用 JS 提供的字符串方法来实现非符号部分的翻转,又因为整数的翻转并不影响符号,所以我们最后补充符号,完成算法。
详解
  1. 1.
    首先设置边界极值;
  2. 2.
    使用字符串的翻转函数进行主逻辑;
  3. 3.
    补充符号
  4. 4.
    然后拼接最终结果
代码
1
/**
2
* @param {number} x
3
* @return {number}
4
*/
5
const reverse = (x) => {
6
// 非空判断
7
if (typeof x !== 'number') {
8
return;
9
}
10
// 极值
11
const MAX = 2147483647;
12
const MIN = -2147483648;
13
14
// 识别数字剩余部分并翻转
15
const rest =
16
x > 0
17
? String(x)
18
.split('')
19
.reverse()
20
.join('')
21
: String(x)
22
.slice(1)
23
.split('')
24
.reverse()
25
.join('');
26
27
// 转换为正常值,区分正负数
28
const result = x > 0 ? parseInt(rest, 10) : 0 - parseInt(rest, 10);
29
30
// 边界情况
31
if (result >= MIN && result <= MAX) {
32
return result;
33
}
34
return 0;
35
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n)O(n)
    代码中 reverse 函数时间复杂度为
    O(n)O(n)
    nn
    为整数长度,因此时间复杂度为
    O(n)O(n)
    ,考虑到32位整数最大长度为 11,即 -2147483648,也可认为是常数时间复杂度
    O(1)O(1)
  • 空间复杂度:
    O(n)O(n)
    代码中创建临时 String 对象,
    nn
    为整数长度,因此空间复杂度为
    O(n)O(n)
    ,考虑到32位整数最大长度为11,即-2147483648,因此空间复杂度为
    O(1)O(1)

方法二 类似 欧几里得算法 求解

思路
我们借鉴欧几里得求最大公约数的方法来解题。符号的处理逻辑同方法一,这里我们通过模 10 取到最低位,然后又通过乘 10 将最低位迭代到最高位,完成翻转。
详解
  1. 1.
    设置边界极值;
  2. 2.
    取给定数值的绝对值,遍历循环生成每一位数字,借鉴欧几里得算法,从 num 的最后一位开始取值拼成新的数
  3. 3.
    同步剔除掉被消费的部分
  4. 4.
    如果最终结果为异常值,则直接返回 0;如果原本数据为负数,则对最终结果取反
  5. 5.
    返回最终结果
代码
1
/**
2
* @param {number} x
3
* @return {number}
4
*/
5
const reverse = (x) => {
6
// 获取相应数的绝对值
7
let int = Math.abs(x);
8
// 极值
9
const MAX = 2147483647;
10
const MIN = -2147483648;
11
let num = 0;
12
13
// 遍历循环生成每一位数字
14
while (int !== 0) {
15
// 借鉴欧几里得算法,从 num 的最后一位开始取值拼成新的数
16
num = (int % 10) + (num * 10);
17
// 剔除掉被消费的部分
18
int = Math.floor(int / 10);
19
}
20
// 异常值
21
if (num >= MAX || num <= MIN) {
22
return 0;
23
}
24
if (x < 0) {
25
return num * -1;
26
}
27
return num;
28
};
Copied!

复杂度分析:

  • 时间复杂度:
    O(n)O(n)
    代码中使用 for 循环,次数为
    nn
    ,即整数的长度,因此时间复杂度为
    O(n)O(n)
  • 空间复杂度:
    O(1)O(1)
    算法中只用到常数个变量,因此空间复杂度为
    O(1)O(1)

有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
示例1
1
输入: s = "anagram", t = "nagaram"
2
输出: true
Copied!
示例2
1
输入: s = "rat", t = "car"
2
输出: false
Copied!

方法一 利用数组sort()方法

思路
首先,对字符串字母进行排序,然后,比较两字符串是否相等。
详解
  1. 1.
    首先,将字符串转为数组。
  2. 2.
    利用数组 sort 方法进行排序。
  3. 3.
    然后,转为字符串进行比较,如果相等返回 true,反之返回 false。
代码
1
const isAnagram = (s, t) => {
2
const sArr = s.split('');
3
const tArr = t.split('');
4
const sortFn = (a, b) => {
5
return a.charCodeAt() - b.charCodeAt();
6
};
7
sArr.sort(sortFn);
8
tArr.sort(sortFn);
9
return sArr.join('') === tArr.join('');
10
};
Copied!
复杂度分析
  • 时间复杂度:
    O(nlogn)O(nlogn)
    JavaScriptsort 方法的实现原理,当数组长度小于等于 10 的时候,采用插入排序,大于 10 的时候,采用快排,快排的平均时间复杂度是
    O(nlogn)O(nlogn)
  • 空间复杂度:
    O(n)O(n)
    算法中申请了 2 个数组变量用于存放字符串分割后的字符串数组,所以数组空间长度跟字符串长度线性相关,所以为
    O(n)O(n)

方法二 计数累加方法

思路
声明一个对象记录字符串每个字母的个数,另外一个字符串每项与得到的对象做匹配,最后,根据计数判断是否相等。
详解
  1. 1.
    首先,声明一个变量,遍历其中一个字符串 s 或 t,对每个字母出现的次数进行累加。
  2. 2.
    然后,遍历另一个字符串,使每一个字母在已得到的对象中做匹配,如果匹配则对象下的字母个数减 1,如果匹配不到,则返回 false,如果最后对象中每个字母个数都为 0,则表示两字符串相等。
代码
1
const isAnagram = (s, t) => {
2
if (s.length !== t.length) {
3
return false;
4
}
5
const hash = {};
6
for (const k of s) {
7
hash[k] = hash[k] || 0;
8
hash[k] += 1;
9
}
10
for (const k of t) {
11
if (!hash[k]) {
12
return false;
13
}
14
hash[k] -= 1;
15
}
16
return true;
17
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n)O(n)
    算法中使用了 2 个单层循环,因此,时间复杂度为
    O(n)O(n)
  • 空间复杂度:
    O(1)O(1)
    申请的变量 hash 最大长度为 256,因为 Ascii 字符最多 256 种可能,因此,考虑为常量空间,即
    O(1)O(1)

字符串转换整数

atoi (表示 ascii to integer)是把字符串转换成整型数的一个函数,实现一个 atoi 函数,使其能将字符串转换成整数。
首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。
注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。
在任何情况下,若函数不能进行有效的转换时,请返回 0。
示例
示例 1:
1
输入: "42
2
输出: 42
Copied!
示例 2:
1
输入: "-42"
2
输出: -42
Copied!
示例 3:
1
输入: "4193 with words"
2
输出: 4193
Copied!
示例 4:
1
输入: "words and 987"
2
输出: 0
Copied!
示例 5:
1
输入: "-91283472332"
2
输出: -2147483648
Copied!
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−2147483648) 。
说明:
你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于
O(nlogn)O(n log n)
,
nn
是数组的大小。

方法一 正则匹配

思路
第一步,使用正则提取满足条件的字符,/^(-|\+)?\d+/g(-|\+)?表示第一位是-或+或都不是,\d+ 表示匹配多个数字
1
const result = str.trim().match(/^(-|\+)?\d+/g);
Copied!
第二步,判断目标是否超过 Int 整形最大值或最小值
1
return result
2
? Math.max(Math.min(Number(result[0]), Math.pow(2,31)-1), -Math.pow(2,31))
3
: 0;
Copied!
代码
1
/**
2
* @param {string} str
3
* @return {number}
4
*/
5
const myAtoi = function (str) {
6
// 提取需要的字符
7
const result = str.trim().match(/^(-|\+)?\d+/g);
8
return result
9
? Math.max(Math.min(Number(result[0]), Math.pow(2, 31) - 1), -Math.pow(2, 31))
10
: 0;
11
};
Copied!
复杂度分析
  • 时间复杂度:
    O(1)O(1)
    上述解法中,代码在执行的时候,它消耗的时间并不随着某个变量的增长而增长,因此时间复杂度为
    O(1)O(1)
  • 空间复杂度:
    O(1)O(1)
    上述解法中,额外所分配的空间都不随着处理数据量变化,所以空间复杂度为
    O(1)O(1)

方法二 逐个判断

思路
第一步,去除字符串之中的空格
1
const news = str.trim();
Copied!
第二步,通过执行 parseInt 判断是否为数字,不是数字返回 0 ,是数组继续解析
1
if(parseInt(news)){
2
return retrunNum(parseInt(news));
3
} else {
4
return 0;
5
}
Copied!
第三步,判断目标是否超过 Int 整形最大值或最小值
1
const retrunNum = function (num) {
2
if (num >= -Math.pow(2, 31) && num <= Math.pow(2, 31) - 1) {
3
return num;
4
} else {
5
return num > 0 ? Math.pow(2, 31) - 1 : -Math.pow(2, 31);
6
}
7
};
Copied!
代码
1
/**
2
* @param {string} str
3
* @return {number}
4
*/
5
const myAtoi = function (str) {
6
const news = str.trim();
7
if (parseInt(news)) {
8
return retrunNum(parseInt(news));
9
} else {
10
return 0;
11
}
12
};
13
const retrunNum = function (num) {
14
if (num >= -Math.pow(2, 31) && num <= Math.pow(2, 31) - 1) {
15
return num;
16
} else {
17
return num > 0 ? Math.pow(2, 31) - 1 : -Math.pow(2, 31);
18
}
19
};
Copied!
复杂度分析
  • 时间复杂度:
    O(1)O(1)
    上述解法中,代码在执行的时候,它消耗的时间并不随着某个变量的增长而增长,因此时间复杂度为
    O(1)O(1)
  • 空间复杂度:
    O(1)O(1)
    上述解法中,额外所分配的空间都不随着处理数据量变化,所以空间复杂度为
    O(1)O(1)