*************************************************************************************************************************
* 感謝ZL同學的監督，是我堅持每天完成計劃的動力 *
*************************************************************************************************************************
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.
自己想的方法：利用一個hashtable記錄已經遇到的char，接著如果重復出現的話，把value置成-1。然后找values()里面除了-1最小的值就好了。
做這道題的時候，遇到的困難是values()返回的是一個Collection。這個Collection的作用是，只能使用exhanced for去遍歷，卻不能轉換成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; }}然而，比較簡單的做法有兩個：第一個方法，利用字典HashTable的做法，字母和出現次數對。再遍歷一次鏈表，找出最先只出現一次的字母；第二個方法，利用String類提供的firstIndex和lastIndex的方法。如果一個字母有重復的話，兩個函數的返回值肯定不一樣。找到返回相同值的最小值即可。第一個方法代碼 (明天寫)：
第二個方法代碼（明天寫）：
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.
這題做錯的地方：對于getMin函數不能使用sort，直接使用Collections.min即可。由于java已經棄用了Stack，所以這道題用LinkedList實現即可。但是使用LinkedList實現Stack需要注意，使用addFirst和removeFirst比Last要好。因為自己實現鏈表的時候也知道，當addLast和removeLast的話，需要遍歷整個鏈表，十分低效且無謂。
代碼如下：
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.這題一開始的思考方向錯了，后來看了烙印網站的視頻，其實很好理解。首先，某個towel (bar)所能儲存的水量其實是當前水桶的“短板” - 當前bar的高度決定的。但是，并不是所有的bar都能儲水。所以我們首先需要判斷這個bar能不能儲水。如果能儲水，就把水量加到要返回的水量總和當中。
怎么判斷當前bar能不能儲水呢？
這就是比較tricky的地方了。主要看這個bar的左邊的所有bar中最高的bar是否能高過這個bar且右邊的所有bar中最高的bar是否能高過這個bar。如果兩邊都滿足，這個bar能儲水。否則，直接跳過這個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這兩題之所以結合在一起講，是因為直接用117的代碼就可以通過116的題目。116只是117的特殊形式（完全二叉樹）。
看完了烙印網站 I Deserve 的視頻后，這題的思路只需要記住下面的遞歸過程即可：
Step 1: 當前節點是葉子節點或者為null的時候返回（base case）；
Step 2：鏈接當前節點的左右兩個孩子（如果有兩個孩子的話，因為step1，確保了至少有一個孩子）：左孩子.right = 右孩子。并且把孩子與其它的同層次的孩子的right都鏈接了。當時這里需要這樣判斷邏輯：
if （有兩個孩子） {
鏈接兩個孩子，鏈接右孩子和root.right的左孩子或者右孩子（如果有的話）。這里自己寫的時候漏了考慮：如果root的right沒有孩子，當時root.right.right有呢？所以這里需要另外設置個neighbour變量，然后用while直到找到當前的左/右孩子的右邊的節點為止或者遍歷完所有root的neighbour。
} else {
用那個唯一的孩子，直接連接到root的neighbour的孩子（如果有）。與上述黑體字過程一致。
}
Step 3：遞歸調用右孩子；
Step 4：遞歸調用左孩子；
為什么要優先調用右孩子呢？就是為了確保上述黑體字的過程能順利實現。否則，可能不能找完所有的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 ListsWrite 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.
這道題其實很tricky，做這道題之前，需要知道cycleLinkedList的判斷標準：快慢指針能否相遇。
且如何找到circle的起點：slow.next = head的時候，head就是起點，否則一直：head = head.next; slow = slow.next;
這些在http://blog.csdn.net/firehotest/article/details/52665467 提到過，知道了這些之后，這道題就可以很tricky地解決了。把headB放到headA之后，然后看看有沒有cycle。如果有就是有交叉點啦。然后通過slow.next = head的方法找到交叉點。接著返回交叉點即可。
代碼：
/** * 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; }}
新聞熱點
疑難解答
