回文算法

验证回文字符串

比较常用的方法就是用 2 个指针,从字符串的前后两个方向,向内夹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<string.h>
int isParlindrome(char s[]){
int length = strlen(s);
char *p = &s[0], *q = &s[length-1];

while(p < q){
if(*p != *q)
return 0; /* 不是回文串 */
else{
p++;
q--;
}
}
return 1;
}

逻辑很简单,一个循环两个指针,就搞定了。有的题目忽略字母的大小写,这时只需再加一些判断即可,也很简单。


验证回文数

如果回文字符串中只包含数字,那么它也可以是一个回文数,例如 20200202。
想要验证回文数,比较简单的方法就是将其转换字符串,然后用验证字符回文串的算法模式去套用。但是这并没有用到数字的特性。
既然是数字,我们可以通过 除法取余 的方式,将这个数字进行翻转,然后比对翻转后的数字与原数字是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int isPalindrome(int num) {
if(x < 0)
return 0;
int revertedNumber = 0;
int tmp = num;
while(tmp != 0){
revertedNumber = (revertedNumber * 10) + (tmp % 10);
tmp /= 10;
}
if(revertedNumber == num)
return 1;
else
return 0;
}

验证回文链表

单链表这种特殊的结构,想要确定个长度也需要 O(n) 的复杂度,而且没有前驱指针,双指针前后夹的办法是没法用了。当然我们可以将它转换为我们熟悉的回文数或者回文串进行计算,但是这同样没有用到链表的特性。

在验证回文链表的场景下,我们可以通过快慢指针的方式找到链表的中间节点,然后再将原链表的一半反转,之后开始比对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef struct{
ElemType val;
ListNode *next;
}ListNode;

int isPalindrome(ListNode *head){
ListNode *slow = head, *fast = head;
ListNode *pre = head, prepre = NULL;

while(fast != NULL && fast->next != NULL){
pre = slow;
slow = slow -> next;
fast = fast -> next -> next;
pre -> next = prepre;
prepre = pre;
}

/* 如果快指针不为 NULL, 说明链表长度为奇数,需要再走一步 */
if(fast != NULL)
slow = slow -> next;

/* 此时 pre 指向原链表前半部分反转后的表头节点 */
/* solw 指向原链表的中间节点 */
while(pre != NULL && slow != NULL){
if(pre.val != slow.val)
return 0;

pre = pre -> next;
slow = slow -> next;
}
return 1;
}
------本文结束感谢您的阅读 ------
0%