linux *** 作系统shell脚本,检查出给出的串是否为回文

#!/bin/bash

s=`echo -n $1 | wc -c` 

n=$((($s)/2))

i=1

while [ $i -le $n ] 

do

    c1=`echo -n $1 | cut -c $i`

    c2=`echo -n $1 | cut -c $s`

    if test $c1 != $c2

    then

        echo "不是回文"

        break

    fi

    i=$(($i+1))

    s=$(($s-1))

done

if test $c1 = $c2

then

    echo "是回文"   

fi

运行： shell.sh string

对于单链表来说，判断回文最简单的方法就是遍历链表，将链表中的元素复制到数组中，然后对数组进行判断是否是回文数组，但是这不符合O(1)的空间复杂度。

由于空间复杂度的要求，需要就地 *** 作链表，不能开辟多余的空间来进行处理，因此引入快慢指针来进行 *** 作。

快慢指针： slow 和 fast，每次slow指针前进一步，fast指针前进两步，当遇到指针为空时说明遍历链表完成，此时也就可以找到链表的中心位置。

注意，由于链表的长度可能是奇数也可能是偶数，因此应该做一个判断。

找到链表的中心后，把链表的后半部分进行就地逆转，就地逆转是采用头插法即可。

后半部分逆转完成后，将链表的前半部分和后半部分一次比较，即可判断是否是回文。

实现代码如下：

链表类定义：

class ListNode {

int val

ListNode next

ListNode(int x) {

val = x

}

}

链表就地反转：

public static ListNode reverseList(ListNode head){

ListNode ptr = head, ptr2 = head

ListNode fast = head.next

while(fast!=null){

//头插法

ptr = fast.next

fast.next = head

head = fast

fast = ptr

}

//反转完成后将原头指针的next设置为null

ptr2.next = null

return head

}

判断链表是否是回文：

1 public static boolean isPalindrome(ListNode head){

2 if(head==null || head.next==null){

3 return true

4 }

5 //建立快慢指针，寻找链表中心

6 ListNode slow = head

7 ListNode fast = head

8 while(fast!=null &&fast.next!=null){

9 slow = slow.next

10 fast = fast.next.next

11 }

12

13 if(fast == null){

14 //偶数个元素(进行链表反转)

15 ListNode ptr = slow, ptr2 = slow

16 ListNode fast1 = slow.next

17 while(fast1!=null){

18 ptr = fast1.next

19 fast1.next = slow

20 slow = fast1

21 fast1 = ptr

22 }

23 ptr2.next = null

24 }else{

25 //奇数个元素(进行链表反转)

26 ListNode ptr = slow.next,ptr2 = slow.next

27 ListNode fast1 = slow.next.next

28 while(fast1 != null){

29 ptr = fast1.next

30 fast1.next = slow.next

31 slow.next = fast1

32 fast1 = ptr

33 }

34 ptr2.next = null

35 slow = slow.next

36 }

37

38 while(slow!=null){

39 if(head.val!=slow.val)

40 return false

41 slow = slow.next

42 head = head.next

43 }

44 return true

45 }

46

47 }

1、打开JUPTER NOTEBOOK，新建一个PYTHON文档。

2、n = input("Please input string: ")print(n)首先让用户输入要进行判断的字符串，然后打印出来查看一下。

3、可以用IF语句来进行判断，判断倒向的是否等于正向的即可。

4、还可以简化一下流程。

5、如下图也可以定义一个新的FUNCTION，然后进行判断。

6、可以利用长度范围不断往回减去范围值，得到反向的字符串，就完成了。

扩展资料：

首先，一个回文串的字符频度应该是：中点频度最低为1，其他字符频度最低为2。那么，如果串中有频度是1的字符，它肯定位于回文串的中心，不然就不属于任何回文串。因此，按频度可以筛选掉一定量的多余字符，将母串进行分割。分割的好处是子串有界。

最懒方法：遍历整串，从中心向两侧扩张并做比较，取得长度，最后返回最大长度所在的串。

优化：在遍历整串过程中，最大长度maxlen会时刻增加，那么，当分割后的有界子串长度小于最大长度maxlen时，就不需要再去判断了。

如果串的某个连续子串(len>=2)它们的频度都是1，那么就不属于任何回文串，可以快速剔除，节省时间。这是关键。

---