Menu Close

回文回文之判断回文大礼包[Asian Elephant]

fairy-tales-4057425_960_720.jpg

回文回文之判断回文大礼包[Asian Elephant]

这是回文回文系列文章的第一篇,当餐前甜点吧

1.验证回文串

image-20200519194150274.png

  • 判断一个字符串是否是回文:
    • 利用左右指针,分别从左到右扫,不相等,返回false,都扫完后,true

核心方法(判断一个char[]是否是回文)

  • 第二题会用到这段代码

整体代码

2.验证回文字符串 Ⅱ

image-20200519195201166.png

题目分析

  • 给一次机会删除某个字符,再判断是否是回文,下面的两种情况对应代码中的两处

image-20200519200048054.png

  • 只需要当发现chas[left]!=chas[right]时,跳过left 或者right

3.回文链表

image-20200519200611421.png

方法1:栈

  • 先将链表的元素push进栈,然后遍历链表,边遍历边弹出栈顶元素

方法2:

clipboard.png

  • 先输入一个字符串,将其构成单链表。之后,可先定位到链表的中间位置,再将链表的后半段逆置。之后使用两个指针同时从链表头部和中间开始逐一向后遍历比较。
  • 借助了快慢指针找到中间的元素
  • 翻转链表用的是比较朴素的做法,还有种递归翻转链表的做法

复杂度分析

  • 时间复杂度为O(n)
  • 空间复杂度为O(1)

4.回文栈

判断一个栈是不是回文

  • 根据栈的特性,可以将字符串全部压入栈,再依次将各个字符出栈,从而得到原字符串的逆置串,将逆置串中的各个字符分别和原字符串中各个字符进行比较,如果完全一致,则为回文串。

本文完

关联阅读

发表评论

电子邮件地址不会被公开。 必填项已用*标注

苏ICP备20029284号-1