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

翻转整数
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例
示例 1:
输入: 123
输出: 321
​
示例 2:
输入: -123
输出: -321
​
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,231−1][−2^{31}, 2^{31} − 1][−231,231−1]。请根据这个假设，如果反转后整数溢出那么就返回 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;
};
复杂度分析
时间复杂度：O(n)O(n)O(n)​
代码中 reverse 函数时间复杂度为 O(n)O(n)O(n)，nnn 为整数长度，因此时间复杂度为 O(n)O(n)O(n)，考虑到32位整数最大长度为 11，即 -2147483648，也可认为是常数时间复杂度 O(1)O(1)O(1)。
空间复杂度：O(n)O(n)O(n)​
代码中创建临时 String 对象，nnn 为整数长度，因此空间复杂度为 O(n)O(n)O(n)，考虑到32位整数最大长度为11，即-2147483648，因此空间复杂度为 O(1)O(1)O(1)。
方法二 类似 欧几里得算法 求解
思路
我们借鉴欧几里得求最大公约数的方法来解题。符号的处理逻辑同方法一，这里我们通过模 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;
};
复杂度分析：
时间复杂度：O(n)O(n)O(n)​
代码中使用 for 循环，次数为 nnn，即整数的长度，因此时间复杂度为 O(n)O(n)O(n)。
空间复杂度：O(1)O(1)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()方法
思路
首先，对字符串字母进行排序，然后，比较两字符串是否相等。
详解
首先，将字符串转为数组。
利用数组 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('');
};
复杂度分析
时间复杂度：O(nlogn)O(nlogn)O(nlogn)​
JavaScript 的 sort 方法的实现原理，当数组长度小于等于 10 的时候，采用插入排序，大于 10 的时候，采用快排，快排的平均时间复杂度是 O(nlogn)O(nlogn)O(nlogn)。
空间复杂度：O(n)O(n)O(n) 算法中申请了 2 个数组变量用于存放字符串分割后的字符串数组，所以数组空间长度跟字符串长度线性相关，所以为 O(n)O(n)O(n)。
方法二 计数累加方法
思路
声明一个对象记录字符串每个字母的个数，另外一个字符串每项与得到的对象做匹配，最后，根据计数判断是否相等。
详解
首先，声明一个变量，遍历其中一个字符串 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;
};
复杂度分析
时间复杂度：O(n)O(n)O(n)​
算法中使用了 2 个单层循环，因此，时间复杂度为 O(n)O(n)O(n)。
空间复杂度：O(1)O(1)O(1)​
申请的变量 hash 最大长度为 256，因为 Ascii 字符最多 256 种可能，因此，考虑为常量空间，即 O(1)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)O(nlogn) , nnn 是数组的大小。
方法一 正则匹配
思路
第一步，使用正则提取满足条件的字符，/^(-|\+)?\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)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)O(1) 上述解法中，额外所分配的空间都不随着处理数据量变化，所以空间复杂度为 O(1)O(1)O(1)​
以前
字符串
下一个
报数、反转字符串和字符串中的第一个唯一字符
最近更新 1 year ago
翻转整数、有效的字母异位词和翻转整数

翻转整数

方法一翻转字符串方法

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

复杂度分析：

有效的字母异位词

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

方法二计数累加方法

字符串转换整数

方法一正则匹配

方法二逐个判断

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

翻转整数

方法一 翻转字符串方法

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

复杂度分析：

有效的字母异位词

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

方法二 计数累加方法

字符串转换整数

方法一 正则匹配

方法二 逐个判断

方法一翻转字符串方法

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

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

方法二计数累加方法

方法一正则匹配

方法二逐个判断
