<LC刷题二>回文字符串判断之leetcode125&234

其他刷题记录见博客首页

1，leecode125 验证回文串

原题：

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

实例：

输入: "A man, a plan, a canal: Panama"

输出: true

输入: "race a car"

输出: false

解决：

定义游标i j，i自左向右移动，j自右向左移动，判断字母数字i j是否相等即可

时间复杂度O(n)

空间复杂度O(1)

class Solution {

    private boolean isAlphanumeric(char c){

        return ((c>='a'&& c<='z')||(c>='A'&&c<='Z')||(c>=''&&c<=''));

    }

    private boolean isEqualIgnoreCase(char a,char b){

        //小写字母a比大写字母A大32

        if (a>='A'&& a<='Z') a+=;

        if (b>='A'&& b<='Z') b+=;

        return a==b;

    }

    public boolean isPalindrome(String s){

        if (s==null||s.length()==) return true;

        int i=,j=s.length()-;

        for (;i<j;++i,--j){

            //判断游标i,j是否为字符或数字，charAt(i)取i位置的字符，放在for循环里，把字符串遍历，取每个字符

            while (i<j&&!isAlphanumeric(s.charAt(i))) i++;

            while (i<j&&!isAlphanumeric(s.charAt(j))) j--;

            //判断每对i,j游标是否相等

            if (i<j&&!isEqualIgnoreCase(s.charAt(i),s.charAt(j))){

                return false;

            }

        }

        return true;

    }

}

2, leetcode234 回文链表

题目：

请判断一个链表是否为回文链表。

实例：

输入: ->

输出: false

输入: ->->->

输出: true

解决：

定义指向当前节点的cur，和指向前一节点的pre，for循环限定执行1/2 length次，由于cur改变指向后单链表就断了，所以把cur.next下一节点存储起来。

cur指向前一节点pre，pre移到cur位置，cur移到next位置，判断长度是否为奇数，否则cur继续移动一位，pre和cur各自向俩头移动进行比较是否相同

(链表中next为指向下一节点的指针)

class Solution {

    public boolean isPalindrome(ListNode head) {

         int len=;
　　　　  //反转一半的链表

        for (ListNode p=head;p!=null;p=p.next,++len);

            ListNode cur =head;

            ListNode pre=null;

            for (int i=;i<len/;i++) {

                ListNode next = cur.next;

                cur.next = pre;

                pre = cur;

                cur = next;

            }

            if (len%==) cur=cur.next;

            for (;pre!=null&&cur!=null;cur=cur.next,pre=pre.next){

                if (cur.val!=pre.val){

                    return false;

                }

            }return true;

    }

}

巴特西

<LC刷题二>回文字符串判断之leetcode125&234

1，leecode125 验证回文串

2, leetcode234 回文链表

最新文章

热门文章