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

翻转整数

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例

示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [231,2311][−2^{31}, 2^{31} − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

方法一 翻转字符串方法

思路

如果将数字看成是有符号位的字符串,那么我们就能够通过使用 JS 提供的字符串方法来实现非符号部分的翻转,又因为整数的翻转并不影响符号,所以我们最后补充符号,完成算法。

详解

  1. 首先设置边界极值;

  2. 使用字符串的翻转函数进行主逻辑;

  3. 补充符号

  4. 然后拼接最终结果

代码

/**
* @param {number} x
* @return {number}
*/
const reverse = (x) => {
// 非空判断
if (typeof x !== 'number') {
return;
}
// 极值
const MAX = 2147483647;
const MIN = -2147483648;
// 识别数字剩余部分并翻转
const rest =
x > 0
? String(x)
.split('')
.reverse()
.join('')
: String(x)
.slice(1)
.split('')
.reverse()
.join('');
// 转换为正常值,区分正负数
const result = x > 0 ? parseInt(rest, 10) : 0 - parseInt(rest, 10);
// 边界情况
if (result >= MIN && result <= MAX) {
return result;
}
return 0;
};

复杂度分析

  • 时间复杂度: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. 设置边界极值;

  2. 取给定数值的绝对值,遍历循环生成每一位数字,借鉴欧几里得算法,从 num 的最后一位开始取值拼成新的数

  3. 同步剔除掉被消费的部分

  4. 如果最终结果为异常值,则直接返回 0;如果原本数据为负数,则对最终结果取反

  5. 返回最终结果

代码

/**
* @param {number} x
* @return {number}
*/
const reverse = (x) => {
// 获取相应数的绝对值
let int = Math.abs(x);
// 极值
const MAX = 2147483647;
const MIN = -2147483648;
let num = 0;
// 遍历循环生成每一位数字
while (int !== 0) {
// 借鉴欧几里得算法,从 num 的最后一位开始取值拼成新的数
num = (int % 10) + (num * 10);
// 剔除掉被消费的部分
int = Math.floor(int / 10);
}
// 异常值
if (num >= MAX || num <= MIN) {
return 0;
}
if (x < 0) {
return num * -1;
}
return num;
};

复杂度分析:

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

    代码中使用 for 循环,次数为 nn,即整数的长度,因此时间复杂度为 O(n)O(n)

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

    算法中只用到常数个变量,因此空间复杂度为 O(1)O(1)

有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例1

输入: s = "anagram", t = "nagaram"
输出: true

示例2

输入: s = "rat", t = "car"
输出: false

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

思路

首先,对字符串字母进行排序,然后,比较两字符串是否相等。

详解

  1. 首先,将字符串转为数组。

  2. 利用数组 sort 方法进行排序。

  3. 然后,转为字符串进行比较,如果相等返回 true,反之返回 false。

代码

const isAnagram = (s, t) => {
const sArr = s.split('');
const tArr = t.split('');
const sortFn = (a, b) => {
return a.charCodeAt() - b.charCodeAt();
};
sArr.sort(sortFn);
tArr.sort(sortFn);
return sArr.join('') === tArr.join('');
};

复杂度分析

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

    JavaScriptsort 方法的实现原理,当数组长度小于等于 10 的时候,采用插入排序,大于 10 的时候,采用快排,快排的平均时间复杂度是 O(nlogn)O(nlogn)

  • 空间复杂度:O(n)O(n) 算法中申请了 2 个数组变量用于存放字符串分割后的字符串数组,所以数组空间长度跟字符串长度线性相关,所以为 O(n)O(n)

方法二 计数累加方法

思路

声明一个对象记录字符串每个字母的个数,另外一个字符串每项与得到的对象做匹配,最后,根据计数判断是否相等。

详解

  1. 首先,声明一个变量,遍历其中一个字符串 s 或 t,对每个字母出现的次数进行累加。

  2. 然后,遍历另一个字符串,使每一个字母在已得到的对象中做匹配,如果匹配则对象下的字母个数减 1,如果匹配不到,则返回 false,如果最后对象中每个字母个数都为 0,则表示两字符串相等。

代码

const isAnagram = (s, t) => {
if (s.length !== t.length) {
return false;
}
const hash = {};
for (const k of s) {
hash[k] = hash[k] || 0;
hash[k] += 1;
}
for (const k of t) {
if (!hash[k]) {
return false;
}
hash[k] -= 1;
}
return true;
};

复杂度分析

  • 时间复杂度: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:

输入: "42
输出: 42

示例 2:

输入: "-42"
输出: -42

示例 3:

输入: "4193 with words"
输出: 4193

示例 4:

输入: "words and 987"
输出: 0

示例 5:

输入: "-91283472332"
输出: -2147483648

解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−2147483648) 。

说明:

你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(nlogn)O(n log n) , nn 是数组的大小。

方法一 正则匹配

思路

第一步,使用正则提取满足条件的字符,/^(-|\+)?\d+/g(-|\+)?表示第一位是-或+或都不是,\d+ 表示匹配多个数字

const result = str.trim().match(/^(-|\+)?\d+/g);

第二步,判断目标是否超过 Int 整形最大值或最小值

return result
? Math.max(Math.min(Number(result[0]), Math.pow(2,31)-1), -Math.pow(2,31))
: 0;

代码

/**
* @param {string} str
* @return {number}
*/
const myAtoi = function (str) {
// 提取需要的字符
const result = str.trim().match(/^(-|\+)?\d+/g);
return result
? Math.max(Math.min(Number(result[0]), Math.pow(2, 31) - 1), -Math.pow(2, 31))
: 0;
};

复杂度分析

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

    上述解法中,代码在执行的时候,它消耗的时间并不随着某个变量的增长而增长,因此时间复杂度为 O(1)O(1)

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

    上述解法中,额外所分配的空间都不随着处理数据量变化,所以空间复杂度为 O(1)O(1)

方法二 逐个判断

思路

第一步,去除字符串之中的空格

const news = str.trim();

第二步,通过执行 parseInt 判断是否为数字,不是数字返回 0 ,是数组继续解析

if(parseInt(news)){
return retrunNum(parseInt(news));
} else {
return 0;
}

第三步,判断目标是否超过 Int 整形最大值或最小值

const retrunNum = function (num) {
if (num >= -Math.pow(2, 31) && num <= Math.pow(2, 31) - 1) {
return num;
} else {
return num > 0 ? Math.pow(2, 31) - 1 : -Math.pow(2, 31);
}
};

代码

/**
* @param {string} str
* @return {number}
*/
const myAtoi = function (str) {
const news = str.trim();
if (parseInt(news)) {
return retrunNum(parseInt(news));
} else {
return 0;
}
};
const retrunNum = function (num) {
if (num >= -Math.pow(2, 31) && num <= Math.pow(2, 31) - 1) {
return num;
} else {
return num > 0 ? Math.pow(2, 31) - 1 : -Math.pow(2, 31);
}
};

复杂度分析

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

    上述解法中,代码在执行的时候,它消耗的时间并不随着某个变量的增长而增长,因此时间复杂度为 O(1)O(1)

  • 空间复杂度: O(1)O(1) 上述解法中,额外所分配的空间都不随着处理数据量变化,所以空间复杂度为 O(1)O(1)