*************************************************************************************************************************

*              感謝ZL同學(xué)的監(jiān)督，是我堅(jiān)持每天完成計(jì)劃的動(dòng)力                                                                         *

*************************************************************************************************************************

387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.Examples:s = "leetcode"return 0.s = "loveleetcode",return 2.Note: You may assume the string contain only lowercase letters.

自己想的方法：利用一個(gè)hashtable記錄已經(jīng)遇到的char，接著如果重復(fù)出現(xiàn)的話，把value置成-1。然后找values()里面除了-1最小的值就好了。

做這道題的時(shí)候，遇到的困難是values()返回的是一個(gè)Collection。這個(gè)Collection的作用是，只能使用exhanced for去遍歷，卻不能轉(zhuǎn)換成List或者其它子類。所以，不能使用Collections.sort去做。

public class Solution {    public int firstUniqChar(String s) {        if (s == null) {            return -1;        }                 if (s.length() == 1) {            return 0;        }                //use the hashtable to record        HashMap<Character, Integer> WordIndex = new HashMap<Character, Integer>();                for (int i = 0; i < s.length(); i++) {            if (wordIndex.containsKey(s.charAt(i))) {                wordIndex.put(s.charAt(i), -1);            } else {                wordIndex.put(s.charAt(i), i);            }        }                int min = Integer.MAX_VALUE;                for (Integer tmp : wordIndex.values()) {            if (tmp != -1) {                min = tmp < min ? tmp : min;            }        }                if (min == Integer.MAX_VALUE) {            return -1;        }                return min;    }}然而，比較簡(jiǎn)單的做法有兩個(gè)：第一個(gè)方法，利用字典HashTable的做法，字母和出現(xiàn)次數(shù)對(duì)。再遍歷一次鏈表，找出最先只出現(xiàn)一次的字母；第二個(gè)方法，利用String類提供的firstIndex和lastIndex的方法。如果一個(gè)字母有重復(fù)的話，兩個(gè)函數(shù)的返回值肯定不一樣。找到返回相同值的最小值即可。
第一個(gè)方法代碼 (明天寫)：
第二個(gè)方法代碼（明天寫）：
155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.push(x) -- Push element x onto stack.pop() -- Removes the element on top of the stack.top() -- Get the top element.getMin() -- Retrieve the minimum element in the stack.Example:MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();   --> Returns -3.minStack.pop();minStack.top();      --> Returns 0.minStack.getMin();   --> Returns -2.
這題做錯(cuò)的地方：對(duì)于getMin函數(shù)不能使用sort，直接使用Collections.min即可。由于java已經(jīng)棄用了Stack，所以這道題用LinkedList實(shí)現(xiàn)即可。但是使用LinkedList實(shí)現(xiàn)Stack需要注意，使用addFirst和removeFirst比Last要好。因?yàn)樽约簩?shí)現(xiàn)鏈表的時(shí)候也知道，當(dāng)addLast和removeLast的話，需要遍歷整個(gè)鏈表，十分低效且無(wú)謂。
代碼如下：
public class MinStack {    PRivate LinkedList<Integer> storage;        /** initialize your data structure here. */    public MinStack() {        this.storage = new LinkedList<Integer>();    }        public void push(int x) {        storage.addFirst(x);    }        public void pop() {        storage.removeFirst();    }        public int top() {        int ans = storage.peekFirst();        return ans;    }        public int getMin() {        return Collections.min(storage);    }}/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.這題一開始的思考方向錯(cuò)了，后來(lái)看了烙印網(wǎng)站的視頻，其實(shí)很好理解。首先，某個(gè)towel (bar)所能儲(chǔ)存的水量其實(shí)是當(dāng)前水桶的“短板” - 當(dāng)前bar的高度決定的。但是，并不是所有的bar都能儲(chǔ)水。所以我們首先需要判斷這個(gè)bar能不能儲(chǔ)水。如果能儲(chǔ)水，就把水量加到要返回的水量總和當(dāng)中。
怎么判斷當(dāng)前bar能不能儲(chǔ)水呢？
這就是比較tricky的地方了。主要看這個(gè)bar的左邊的所有bar中最高的bar是否能高過這個(gè)bar且右邊的所有bar中最高的bar是否能高過這個(gè)bar。如果兩邊都滿足，這個(gè)bar能儲(chǔ)水。否則，直接跳過這個(gè)bar即可。
public class Solution {    public int trap(int[] height) {        if (height == null || height.length < 3) {            return 0;        }                int[] maxHeightLeft = new int[height.length];        int[] maxHeightRight = new int[height.length];                maxHeightLeft[0] = 0;        maxHeightRight[height.length - 1] = 0;                int maxHeight = 0;        //fill in those two arrays        for (int i = 1; i < height.length; i++) {            maxHeight = 0;            for (int j = i - 1; j > -1; j--) {                maxHeight = height[j] > maxHeight ? height[j] : maxHeight;            }            maxHeightLeft[i] = maxHeight;        }                for (int i = 0; i < height.length - 1; i++) {            maxHeight = 0;            for (int j = i + 1; j < height.length; j++) {                maxHeight = height[j] > maxHeight ? height[j] : maxHeight;            }            maxHeightRight[i] = maxHeight;        }                //simple logic        int trap = 0;                for (int index = 0; index < height.length; index++) {            if (height[index] > maxHeightLeft[index] || height[index] > maxHeightRight[index]) {                continue;            }                        trap += (Math.min(maxHeightLeft[index], maxHeightRight[index]) - height[index]);        }                return trap;    }}116. Populating Next Right Pointers in Each NodeGiven a binary tree    struct TreeLinkNode {      TreeLinkNode *left;      TreeLinkNode *right;      TreeLinkNode *next;    }Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.Initially, all next pointers are set to NULL.Note:You may only use constant extra space.You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).For example,Given the following perfect binary tree,         1       /  /      2    3     / /  / /    4  5  6  7After calling your function, the tree should look like:         1 -> NULL       /  /      2 -> 3 -> NULL     / /  / /    4->5->6->7 -> NULL117. Populating Next Right Pointers in Each Node IIFollow up for problem "Populating Next Right Pointers in Each Node".What if the given tree could be any binary tree? Would your previous solution still work?Note:You may only use constant extra space.For example,Given the following binary tree,         1       /  /      2    3     / /    /    4   5    7After calling your function, the tree should look like:         1 -> NULL       /  /      2 -> 3 -> NULL     / /    /    4-> 5 -> 7 -> NULL
這兩題之所以結(jié)合在一起講，是因?yàn)橹苯佑?17的代碼就可以通過116的題目。116只是117的特殊形式（完全二叉樹）。
看完了烙印網(wǎng)站 I Deserve 的視頻后，這題的思路只需要記住下面的遞歸過程即可：
Step 1: 當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)或者為null的時(shí)候返回（base case）；
Step 2：鏈接當(dāng)前節(jié)點(diǎn)的左右兩個(gè)孩子（如果有兩個(gè)孩子的話，因?yàn)閟tep1，確保了至少有一個(gè)孩子）：左孩子.right = 右孩子。并且把孩子與其它的同層次的孩子的right都鏈接了。當(dāng)時(shí)這里需要這樣判斷邏輯：
if （有兩個(gè)孩子） {
鏈接兩個(gè)孩子，鏈接右孩子和root.right的左孩子或者右孩子（如果有的話）。這里自己寫的時(shí)候漏了考慮：如果root的right沒有孩子，當(dāng)時(shí)root.right.right有呢？所以這里需要另外設(shè)置個(gè)neighbour變量，然后用while直到找到當(dāng)前的左/右孩子的右邊的節(jié)點(diǎn)為止或者遍歷完所有root的neighbour。
} else {
用那個(gè)唯一的孩子，直接連接到root的neighbour的孩子（如果有）。與上述黑體字過程一致。
}
Step 3：遞歸調(diào)用右孩子；
Step 4：遞歸調(diào)用左孩子；
為什么要優(yōu)先調(diào)用右孩子呢？就是為了確保上述黑體字的過程能順利實(shí)現(xiàn)。否則，可能不能找完所有的neighbours. 
代碼如下：
public class Solution {    public void connect(TreeLinkNode root) {        if (root == null || (root.left == null && root.right == null)) {            return;        }                if (root.left != null && root.right != null) {            root.left.next = root.right;            TreeLinkNode parentNeibour = root.next;            while (parentNeibour != null) {                if (parentNeibour.left != null || parentNeibour.right != null) {                    root.right.next = (parentNeibour.left == null ? parentNeibour.right : parentNeibour.left);                    break;                }                parentNeibour = parentNeibour.next;            }        } else {            TreeLinkNode child = (root.left != null ? root.left : root.right);            TreeLinkNode parentNeibour = root.next;            while (parentNeibour != null) {                if (parentNeibour.left != null || parentNeibour.right != null) {                    child.next = (parentNeibour.left == null ? parentNeibour.right : parentNeibour.left);                    break;                }                parentNeibour = parentNeibour.next;            }        }                connect(root.right);        connect(root.left);    }}160. Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.For example, the following two linked lists:A:          a1 → a2                   ↘                     c1 → c2 → c3                   ↗            B:     b1 → b2 → b3begin to intersect at node c1.Notes:If the two linked lists have no intersection at all, return null.The linked lists must retain their original structure after the function returns.You may assume there are no cycles anywhere in the entire linked structure.Your code should preferably run in O(n) time and use only O(1) memory.
這道題其實(shí)很tricky，做這道題之前，需要知道cycleLinkedList的判斷標(biāo)準(zhǔn)：快慢指針能否相遇。
且如何找到circle的起點(diǎn)：slow.next = head的時(shí)候，head就是起點(diǎn)，否則一直：head = head.next; slow = slow.next;
這些在http://blog.csdn.net/firehotest/article/details/52665467 提到過，知道了這些之后，這道題就可以很tricky地解決了。把headB放到headA之后，然后看看有沒有cycle。如果有就是有交叉點(diǎn)啦。然后通過slow.next = head的方法找到交叉點(diǎn)。接著返回交叉點(diǎn)即可。
代碼：
/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    private ListNode cycleLinkedListII(ListNode head) {        if (head == null || head.next == null) {            return null;        }                ListNode fast = head.next;        ListNode slow = head;                while (fast != slow) {            if (fast == null || fast.next == null) {                return null;            }            fast = fast.next.next;            slow = slow.next;        }                while (head != slow.next) {            head = head.next;            slow = slow.next;        }                return head;    }            public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        if (headA == null || headB == null) {            return null;        }                ListNode cur = headA;                while (cur.next != null) {            cur = cur.next;        }                cur.next = headB;                ListNode result = cycleLinkedListII(headA);                cur.next = null;                return result;            }}