前端也来点算法(TypeScript版) | 2 - 回文数和回文链表

662

算法采用 TS 进行编写。

回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。回文链表是链表节点的值和回文数有相同规律的链表。

回文数

这个数字可以看成是以中心对称分布的。最优的方案是尽量少的循环和使用空间,所以能不能想办法只循环 length / 2 次就可以判断出结果?显然是可以的,因为它具备对称性,所以排除边界条件之后,判断 str[i]str[length - i - 1]0 - length / 2 内是否一直相等就可确定是不是回文数。

TS 代码实现

export function isPalindrome1(x: number): boolean {
  // 排除小于0的边界条件
  if (x < 0) return false
  // 将数字转换成字符串,方便遍历
  const str = String(x)
  // 减少循环次数,只遍历一般的长度
  for (let i = 0; i < str.length / 2; i++) {
    // 如果遍历过程中有任何一个 `i` 与 `length - i - 1` 对应的值不相等,则一定可以确定不对称
    if (str[i] !== str[str.length - i - 1]) return false
  }
  // 遍历完都没有出现不等,则可以确定是回文数了
  return true
}

分析复杂度:由于要遍历 length / 2 次,所以时间复杂度是 O(n),没有消耗额外的空间,复杂度为 O(1)。

回文链表

回文链表和回文数非常相似,只不过链表是套了一个壳子。所以我们可以考虑把链表中的值先提取出来,然后再像回文数那样判断提取出来的数是否对称。

节点的结构:有 valnext 两个属性,val 是节点存储的值,next 是指向下一个节点的指针。

export class ListNode {
  constructor(public val: number, public next: ListNode | null) {}
}

回文链表有几个边界条件:

  1. head 节点,也就是链表的第一个节点就是 null,则判断是回文链表
  2. head.next 也就是第二个节点为 null,表示只有 head 节点,这也是一个回文链表。
  3. 正常情况,遍历完链表所有节点的值,判断是不是符合回文数对称的特性。
// 先将链表数据提取出来成为数组,然后判断数组是不是回文数组
export function isPalindromeLinkedList(head: ListNode | null): boolean {
  // 两个边界条件,都属于是回文链表
  if (head === null || head.next === null) return true
  // arr 存储所有节点中的 val
  const arr: number[] = []
  // 遍历链表时的临时节点
  let current: ListNode | null = head
  // 一直遍历链表, 用 current = current.next ,直到 current 不指向任何节点
  while (current) {
    // 把节点的值存到 arr
    arr.push(current.val)
    // 更换当前遍历的节点
    current = current.next
  }
  // 判断节点值得数组是否满足对称的特性
  for (let i = 0; i < arr.length / 2; i++) {
    if (arr[i] !== arr[arr.length - i - 1]) return false
  }
  // 遍历完成,没有不等的情况,判断是一个回文链表
  return true
}

复杂度分析:while 循环最坏的情况是 length 次,for 循环 length / 2 次,所以时间复杂度是 O(n),由于没有消耗额外的空间,空间复杂度是 O(1)。


用 TypeScript 写代码明显感觉错误率在减低,在写代码的阶段就会提示大部分书写错误,TypeScript 现在大势所趋,欢迎大家关注我,一起学习、进步!!!

算法系列文章 前端也来点算法(TS 版) 系列文章

欢迎大家关注我的掘金和公众号,算法、TypeScript、React 及其生态源码定期讲解。