如何鉴别回文-golang实现 2019-06-09 19:09 label programming

回文，亦称回环，是正读反读都能读通的句子，亦有将文字排列成圆圈者，是一种修辞方式和文字游戏。Ref

比如中文的：上海自来水来自海上 就是一句回文；而英文中比较常用的回文单词有：level, refer, noon 等等。

在很多面试中我们会遇到如何判断回文的考题，而回文以什么形式出现也直接决定了算法实现的难易程度，下面我会介绍当回文以三种不同的数据结构来存储时，我们如何判别它是回文。

• 回文存储在字符串中
  这也许是最容易实现的一种存储形式，我可以将字符串当作一个字符数组，用两个指针，一头一尾，一个向前，一个向后遍历数组，比较遇到的每一个字符，如果有任何一个字符不相等，就返回FALSE；否则直至两个指针相遇，返回TRUE。 让我们用Golang来实现该过程：

  func IsStringPalindrome(s string) bool {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true
  }     

• 回文以整数的形式出现
  给予一个满足回文形式的整数，如何判断是否为回文？ 比如：1234321，54345等等。一个简单的解决方案就是，将整数拆分成单独的一个个数字，然后采用判断字符串是否为回文的方式即可判断原有整数是否为回文。那么如何将一个整数拆分成单独的数字呢？只要让该整数除以10，每次获取整除后的余数，然后其商继续除以10，直到商为0，停止循环。如果你收集每次获取到的余数存入一个整数数组，到最后程序退出时，数组中存储的数字，从头到尾刚好是原有整数的翻转数字，不过回文，其特殊性就在于，将一个回文翻转后，和原有回文仍然相同，因此不影响我们对回文的判断。让我们用Golang来实现该过程：

  func IsIntPalindrome(s int) bool {
    if s < 0 {
        return false
    }
    //定义一个字符数组
    str := []rune{}
    a := s
    //假设商等于初始的整数
    //只要商不为0，就继续循环
    for a > 0 {
        k := a
        a = k / 10
        //收集每次除以10后的余数
        str = append(str, rune(k%10))
    }
    //用判断字符串是否为回文的方式，判断收集到的字符数组是否为回文
    return IsStringPalindrome(string(str))
  }      

• 回文存储在单向链表当中
  假设我们有如下形式的单向链表：

  type Node struct {
    Data rune
    Next *Node
  }  

  如何判断存储于该单向链表中的字符为回文字串？ 关于回文的特性，我们还有一点没有提及，那就是所有的回文字串，肯定都是奇数位。必然有一个中心点，向两边对称，对称是偶数，偶数+1，必然是奇数。如果我们用一个慢指针和一个快指针来遍历链表，慢指针一次前进一步，快指针一次前进两步。那么当快指针走到链表末尾时，慢指针必然位于链表中间（凡是存储了奇数个字符的链表必然有该特点）；此时让慢指针继续往下走，但是用另外一个指针，在中部的位置往前走，然后比较慢指针和该指针遇到的每一个字符，如果不相等，立即返回FALSE，否则直到慢指针走到链表尾，程序结束，返回TRUE。 你可能已经发现问题了，就是从中部开始的指针如何往前走，这个毕竟是单向链表，每个节点都不知道前一节点的指针，是无法往回走的；所以慢指针从起始点到终点这个过程中，除了移动指针往前走，还需要将前半部分的next指针逆序，这样才能用一个指针从中部往前走。 让我们用Golang来实现该过程：

  //如果回文存储在单向链表中，判断是否为回文的实现
  func IsPalindrome(head *Node) bool {
    if head == nil {
        return false
    }
    slow := head
    fast := head
    prev := head
    next := slow.Next
    if next == nil {
        return true
    }
  
    for fast != nil && fast.Next != nil {
        if fast.Next.Next == nil {
            fast = fast.Next
            break
        } else {
            fast = fast.Next.Next
        }
        //慢指针往后移动的过程中，将前半部分链表翻转，将 next 指针指向反过来
        prev = slow
        slow = next
        next = slow.Next
        slow.Next = prev
    }
    //如果是回文，此时slow指针在链表中部
  
    slow = next
    for slow != nil {
        if slow.Data != prev.Data {
            return false
        } else {
            slow = slow.Next //往前继续走
            prev = prev.Next //往回走
        }
    }
    return true
  }      

  这就是回文的三种存储方式实现，难度也是依次递增，希望对大家有所帮助。