第六周arts

Algorithm

看專欄《數(shù)據(jù)結構與算法之美》遇到的一道算法題：
題目描述：給定一個單鏈表連接的字符串，判斷是不是回文字符串
比如：

• a->b->c->b->a 是
• a->b->b->a 是
• a->b->c 否

思路分析：

• 如果是普通的字符串則很好判斷，利用數(shù)組的訪問為O（1）+ 對稱性即可判斷
• 單鏈表則不能這么做，我的思路：
  思路1：將鏈表逆序之后與原鏈表對比：需要先將原鏈表拷貝一份(如何copy)，然后逆序
  思路2：快慢指針找到中間節(jié)點，然后逆序前半部分鏈表，之后遍歷比較前后兩部分鏈表即可，最后將鏈表前半部分逆序還原, 具體思路見代碼注釋。

具體代碼實現(xiàn)如下:

public class PalidromeString {

    public static void main(String[] args) {
        PalidromeString ps = new PalidromeString();
        Node head = new Node('1');
//        Node p1 = head.next = new Node('1');
//        Node p2 = p1.next = new Node('2');
//        Node p3 = p2.next = new Node('1');
//        Node p4 = p3.next = new Node('1');
        System.out.println(ps.isPalidromeString2(head));
    }

    //思路1：時間復雜度：O（n）,空間復雜度：O（n）
    public boolean isPalidromeString(Node head) {

        if (head == null) {
            return true;
        }

        //copy head 這里假設head是包含元素的
        Node copyHead = new Node(head.val);
        Node originP = head.next, copyP = copyHead;
        while (originP != null) {
            copyP.next = new Node(originP.val);

            originP = originP.next;
            copyP = copyP.next;
        }

        //reverse copyHead
        Node p = copyHead, q = p.next;
        while (q != null) {
            p.next = q.next;
            q.next = copyHead;

            //更新
            copyHead = q;
            q = p.next;
        }

        //開始比較
        originP = head;
        copyP = copyHead;
        while (originP != null && copyP != null) {
            if (originP.val != copyP.val) {
                return false;
            }
            originP = originP.next;
            copyP = copyP.next;
        }

        return true;
    }

    /**
     * 思路2：快慢指針，先找到中間節(jié)點，然后將前半段逆序，然后分別從開頭和中間順序比較，最后將前半段逆序還原（一般實現(xiàn)是不改變輸入）
     * 時間復雜度O（n）,空間復雜度O（1）
     * 注意點：找中間節(jié)點或者比較時，與鏈表中的個數(shù)是偶數(shù)還是奇數(shù)是息息相關的，注意區(qū)分對待；尤其要注意空指針的判斷
     * 比如：
     * 偶數(shù)個：1->2->2->1, 中間節(jié)點mid這里取第二個2（當然如果取第一個2也可以，但是后面的逆序條件判斷需要變化），
     * 逆序p,q,當q==mid時停止逆序，可以保證只有前半段逆序，比較指針：head, mid即可，逆序回去呢，同理
     * 奇數(shù)個：1->2->3->2->1, 中間節(jié)點mid為3，逆序p,q,也可以q==mid的時候停止逆序，則逆序之后為2->1->3->2->1,比較：head,mid.next開始比較
     * 逆序回去呢，同理
     * 上述分析可以保證偶數(shù)，奇數(shù)保持統(tǒng)一
     */

    public boolean isPalidromeString2(Node head) {
        if (head == null) {
            return true;
        }

        //按照上述分析，利用快慢指針找出符合條件的中間節(jié)點,最后慢指針指向的就是中間節(jié)點
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node mid = slow;

        //前半段逆序
        Node p = head, q = p.next;
        while (q != null && q != mid) {
            p.next = q.next;
            q.next = head;

            //更新
            head = q;
            q = p.next;
        }

        //開始比較，奇數(shù)：head，mid.next(注意只有一個元素時), 偶數(shù)：head, mid
        Node start1 = head, start2;
        if (fast == null) {
            //說明是偶數(shù)個元素
            start2 = mid;
        } else {
            start2 = mid.next;
        }
        //這樣判斷可以很好的避免只有一個元素的誤判
        boolean isPalidromeString = true;
        while(start1 != null && start2 != null){
            if(start1.val != start2.val){
                isPalidromeString = false;
                break;
            }
            start1 = start1.next;
            start2 = start2.next;
        }

        //還原前半段逆序的元素
        p = head;
        q = p.next;
        while (q != null && q != mid) {
            p.next = q.next;
            q.next = head;

            //更新
            head = q;
            q = p.next;
        }

        return isPalidromeString;
    }
}

class Node {
    Node next = null;
    char val;

    public Node(char val) {
        this.val = val;
    }

}

Review

繼續(xù)微服務相關的英文文章：
關于nginx上的introduction-to-microservices的系列文章，讀書筆記鏈接：http://www.itdecent.cn/p/fd47ae1917dc

Tip

使用Spring事務的時候遇到的一個坑：在加了Spring事務的函數(shù)里面涉及對同一個數(shù)據(jù)庫多個表的插入操作，發(fā)現(xiàn)某個表的插入記錄失敗后，之前插入其他表的數(shù)據(jù)竟然成功了。
造成的原因：在事務函數(shù)中加了try...catch，直接把數(shù)據(jù)庫異常給catch掉了，導致Spring不知道要回滾。Spring的回滾機制：在事務層拋出異常時，Spring會做回滾標記，所以不能在事務層try...catch, try...catch應該放在調(diào)用事務函數(shù)的地方。

Share

一直在分享這一塊不知道寫什么，就分享下最近激勵自己的一句話吧。
自律給你自由，自由是什么？自由不是你想干什么就干什么，而是不想干什么就不干什么，所以從堅持arts, 堅持運動開始，把優(yōu)秀當成一種習慣。