算法学习笔记 — 数字与字符串处理

算法并不是什么高深的领域内容,我们平时在项目开发中几乎都有涉及,比如翻转字符串、字符串截取,这些熟悉的函数方法你一定有所接触。

翻转整数

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

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

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

解法一:利用数组的 reverse 方法

思路:在 JavaScript 中数组有一个 reverse 方法,该方法是将数组元素进行翻转。既然数组有翻转的方法,那么我们能不能想办法将数字转换成数组呢?目前虽然没有直接将数字转换成数组的方法,但我们可以考虑先将数字变成字符串,然后将字符串数值转换数组,利用数组的 reverse 方法翻转数组后,将转换回数字。

/**
 * 翻转整数
 * @param {number} num 需要翻转的整数
 * @return {number} 翻转后的整数
 */
function reverseInteger(num) {
  // 异常值处理
  if (typeof num !== 'number') return NaN
  // 获取绝对值状态下的翻转整数
  let result = parseInt(Math.abs(num).toString().split('').reverse().join(''), 10)
  // 补充符号
  result = num < 0 ? 0 - result : result
  // 判断溢出
  if (result >= Math.pow(2, 31) - 1 || result <= Math.pow(-2, 31) + 1) return 0
  return result
}

复杂度分析

  • 时间复杂度:$ O(n) $
    当前算法将数值转换为字符串进行字符串转数组,数组翻转以及数组转字符串操作,该过程时间消耗与数值的位数 $ n $ 有关,可以认为是 $ 3n $ 的时间消耗,忽略系数,因此时间复杂度可以认为是 $ O(n) $。
    考虑到该题限制了数值范围为 32 位的有符号整数,其最大整数位长度为 11,也可以认为是常数时间复杂度 $ O(1) $。

  • 空间复杂度:$ O(n) $
    当前算法在转换过程中临时创建了字符串和数组对象,临时空间的大小与数值的位数 $ n $ 有关,因此空间复杂度为 $ O(n) $。
    考虑到该题限制了数值范围为 32 位的有符号整数,其最大整数位长度为 11,也可以认为是常数空间复杂度 $ O(1) $。

解法二:借助欧几里得算法求解

思路:我们借鉴欧几里得求最大公约数的方法来解题。符号的处理逻辑不变,对于整数部分我们通过模 10 取到最低位,然后又通过乘 10 将最低位迭代到最高位,完成数值翻转。

/**
 * 翻转整数
 * @param {number} num 需要翻转的整数
 * @return {number} 翻转后的整数
 */
function reverseInteger(num) {
  // 异常值处理
  if (typeof num !== 'number') return NaN
  // 获取相应数的绝对值
  let int = Math.abs(num)
  let result = 0
  // 遍历循环生成每一位数字
  while (int !== 0) {
    // 借鉴欧几里得算法,从 num 的最后一位开始取值拼成新的数
    result = int % 10 + result * 10
    // 剔除掉被消费的部分
    int = Math.floor(int / 10)
  }
  // 补充符号
  result = num < 0 ? 0 - result : result
  // 判断溢出
  if (result >= Math.pow(2, 31) - 1 || result <= Math.pow(-2, 31) + 1) return 0
  return result
}

复杂度分析

  • 时间复杂度:$ O(n) $
    由于当前算法只使用了 while 循环,循环次数为 $ n $ 次,即数值的整数长度,因此时间复杂度为 $ O(n) $。

  • 空间复杂度:$ O(1) $
    当前算法只用到了常数个变量,因此空间复杂度为 $ O(1) $。

有效的字母异位词

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

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

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

解法一:利用数组的 sort 方法

思路:先将字符串转为数组,利用数组的 sort 方法进行默认排序,将排序后的数组转会字符串,比较字符串是否相等。

/**
 * 判断是否为有效的字母异位词
 * @param {string} source 当前字符串
 * @param {string} target 目标字符串
 * @return {boolean} 排序后的字符串
 */
function isAnagram(source, target) {
  if (typeof source !== 'string' || typeof target !== 'string') {
    return false
  }
  /**
   * 字符串排序
   * @param {string} str 需要排序的字符串
   * @return {string} 排序后的字符串
   */
  const sortString = str => {
    return str.split('').sort().join('')
  }
  return sortString(source) === sortString(target)
}

复杂度分析

  • 时间复杂度:$ O(nlog(n)) $
    当前算法主要借助了数组的 sort 方法,但 JavaScript 中 sort 方法的实现原理,当数组长度小于等于 10 的时候,采用插入排序 $ O(n^2) $,大于 10 的时候,采用快速排序,快速排序的平均时间复杂度是 $ O(nlog(n)) $。

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

解法二:计数累加法

思路:先统计第一个字符串的字符类型和出现次数,然后对另一个字符串进行对比统计,如果字符类型不一致或者出现次数不同,则表示两个字符串不相等。

/**
 * 判断是否为有效的字母异位词
 * @param {string} source 当前字符串
 * @param {string} target 目标字符串
 * @return {boolean} 排序后的字符串
 */
function isAnagram(source, target) {
  if (typeof source !== 'string' || typeof target !== 'string') {
    return false
  }
  if (source.length !== target.length) {
    return false
  }
  const hash = Object.create(null)
  for (const k of source) {
    hash[k] = k in hash ? hash[k] + 1 : 1
  }
  for (const k of target) {
    if (!(k in hash)) return false
    hash[k] -= 1
  }
  return true
}

复杂度分析

  • 时间复杂度:$ O(n) $
    当前算法只使用了两次单循环,因此时间复杂度为 $ O(n) $。

  • 空间复杂度:$ O(1) $
    当前算法只使用 hashk 两个变量,空间大小不随字符串的变量而变化。

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

给定一个字符串,假定该字符串只包含小写字母,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

解法一:利用 js 自带方法求解

思路:如果字符串某个字符的正向索引值和反向索引值相同,则表示该字符只出现了一次。

/**
 * 获取字符串中的第一个唯一字符
 * @param {string} str 目标字符串
 * @return {number} 唯一字符的索引值,如果不存在,则返回 -1。
 */
function firstUniqChar(str) {
  if (typeof str !== 'string') return -1
  for (let i = 0; i < str.length; i += 1) {
    if (str.indexOf(str[i]) === str.lastIndexOf(str[i])) {
      return i
    }
  }
  return -1
}

复杂度分析

  • 时间复杂度:$ O(n^2) $
    循环的时间复杂度为 $ O(n) $,indexOflastIndexOf 的时间复杂度均为 $ O(n) $,所以总时间复杂度应该为 $ O(n^2) $。

  • 空间复杂度:$ O(1) $
    除了临时变量 i,没有开辟额外的存储空间。

解法二:利用哈希

思路:先使用一个对象存储所有的字符出现次数,再找出对象中字符只出现一次的下标。

/**
 * 获取字符串中的第一个唯一字符
 * @param {string} str 目标字符串
 * @return {number} 唯一字符的索引值,如果不存在,则返回 -1。
 */
function firstUniqChar(str) {
  if (typeof str !== 'string') return -1
  const hash = Object.create(null)
  for (const k of str) {
    hash[k] = k in hash ? hash[k] + 1 : 1
  }
  for (let i = 0; i < str.length; i += 1) {
    if (hash[str[i]] === 1) {
      return i
    }
  }
  return -1
}

复杂度分析

  • 时间复杂度:$ O(n) $
    该算法存在两次遍历,每次遍历的时间复杂度为 $ O(n) $,因为不存在嵌套遍历,因此时间复杂度只与变量 str 有关。

  • 空间复杂度:$ O(1) $
    当前算法只使用 hashki 三个变量,空间大小不随字符串的变量而变化。

验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。本题中,我们将空字符串定义为有效的回文串。

示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:
输入: "race a car"
输出: false

解法一:字符串遍历

思路:先移除字符串中的非字母和数字,再将字符串转换为数组,再对数组首尾一一比较,即可得出结果。

/**
 * 验证回文串
 * @param {string} str 需要判断的字符串
 * @return {boolean} 是否为回文串
 */
function isPalindrome(str) {
  if (typeof str !== 'string') return false
  // 将传入的字符串,统一转化为小写,同时去除非字母和数字,在转换为数组
  const strArr = str.toLowerCase().replace(/[^a-z0-9]/g, '').split('')
  let i = 0
  let j = strArr.length - 1
  // 循环比较元素
  while (i < j) {
    // 从首尾开始, 一一比较元素是否相等
    if (strArr[i] === strArr[j]) {
      // 若相等,即第二个元素和倒数第二个元素继续比较,依次类推
      i += 1
      j -= 1
    } else {
      // 只要有一个相对位置上不相等,既不是回文串
      return false
    }
  }
  return true
}

复杂度分析

  • 时间复杂度:$ O(n) $
    该算法中 while 循环最多执行 $ n/2 $ 次,因此时间复杂度为 $ O(n) $。

  • 空间复杂度:$ O(n) $
    该算法使用了长度为 $ n $ 的数组,因此空间复杂度为 $ O(n) $。

解法二:利用数组的 reverse 方法

思路:先移除字符串中的非字母和数字,然后利用数组的 reverse 方法将字符串翻转,再和原字符串进行比较,即可得到结果。

/**
 * 验证回文串
 * @param {string} str 需要判断的字符串
 * @return {boolean} 是否为回文串
 */
function isPalindrome(str) {
  if (typeof str !== 'string') return false
  // 将传入的字符串,统一转化为小写,同时去除非字母和数字,在转换为数组
  const strArr = str.toLowerCase().replace(/[^a-z0-9]/g, '').split('')
  // 将2个字符进行比较得出结果
  return strArr.join('') === strArr.reverse().join('')
}

复杂度分析

  • 时间复杂度:$ O(n) $
    该算法中所用的 js 方法的时间复杂度都为 $ O(n) $,且都在独立的循环中执行,因此,总的时间复杂度依然为 $ O(n) $。

  • 空间复杂度:$ O(n) $
    该算法使用了长度为 $ n $ 的数组,因此空间复杂度为 $ O(n) $。

此为原创文章,转载请注明出处