给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例
示例 1:输入: 123输出: 321示例 2:输入: -123输出: -321示例 3:输入: 120输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 。请根据这个假设,如果反转后整数溢出那么就返回 0。
思路
如果将数字看成是有符号位的字符串,那么我们就能够通过使用 JS 提供的字符串方法来实现非符号部分的翻转,又因为整数的翻转并不影响符号,所以我们最后补充符号,完成算法。
详解
首先设置边界极值;
使用字符串的翻转函数进行主逻辑;
补充符号
然后拼接最终结果
代码
/*** @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;};
复杂度分析
时间复杂度:
代码中 reverse
函数时间复杂度为 , 为整数长度,因此时间复杂度为 ,考虑到32位整数最大长度为 11,即 -2147483648,也可认为是常数时间复杂度 。
空间复杂度:
代码中创建临时 String
对象, 为整数长度,因此空间复杂度为 ,考虑到32位整数最大长度为11,即-2147483648,因此空间复杂度为 。
思路
我们借鉴欧几里得求最大公约数的方法来解题。符号的处理逻辑同方法一,这里我们通过模 10 取到最低位,然后又通过乘 10 将最低位迭代到最高位,完成翻转。
详解
设置边界极值;
取给定数值的绝对值,遍历循环生成每一位数字,借鉴欧几里得算法,从 num 的最后一位开始取值拼成新的数
同步剔除掉被消费的部分
如果最终结果为异常值,则直接返回 0;如果原本数据为负数,则对最终结果取反
返回最终结果
代码
/*** @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;};
时间复杂度:
代码中使用 for 循环,次数为 ,即整数的长度,因此时间复杂度为 。
空间复杂度:
算法中只用到常数个变量,因此空间复杂度为 。
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
示例1
输入: s = "anagram", t = "nagaram"输出: true
示例2
输入: s = "rat", t = "car"输出: false
思路
首先,对字符串字母进行排序,然后,比较两字符串是否相等。
详解
首先,将字符串转为数组。
利用数组 sort 方法进行排序。
然后,转为字符串进行比较,如果相等返回 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('');};
复杂度分析
时间复杂度:
JavaScript
的 sort
方法的实现原理,当数组长度小于等于 10 的时候,采用插入排序,大于 10 的时候,采用快排,快排的平均时间复杂度是 。
空间复杂度: 算法中申请了 2 个数组变量用于存放字符串分割后的字符串数组,所以数组空间长度跟字符串长度线性相关,所以为 。
思路
声明一个对象记录字符串每个字母的个数,另外一个字符串每项与得到的对象做匹配,最后,根据计数判断是否相等。
详解
首先,声明一个变量,遍历其中一个字符串 s 或 t,对每个字母出现的次数进行累加。
然后,遍历另一个字符串,使每一个字母在已得到的对象中做匹配,如果匹配则对象下的字母个数减 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;};
复杂度分析
时间复杂度:
算法中使用了 2 个单层循环,因此,时间复杂度为 。
空间复杂度:
申请的变量 hash 最大长度为 256,因为 Ascii 字符最多 256 种可能,因此,考虑为常量空间,即 。
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 ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 , 是数组的大小。
思路
第一步,使用正则提取满足条件的字符,/^(-|\+)?\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;};
复杂度分析
时间复杂度:
上述解法中,代码在执行的时候,它消耗的时间并不随着某个变量的增长而增长,因此时间复杂度为
空间复杂度:
上述解法中,额外所分配的空间都不随着处理数据量变化,所以空间复杂度为
思路
第一步,去除字符串之中的空格
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);}};
复杂度分析
时间复杂度:
上述解法中,代码在执行的时候,它消耗的时间并不随着某个变量的增长而增长,因此时间复杂度为
空间复杂度: 上述解法中,额外所分配的空间都不随着处理数据量变化,所以空间复杂度为