[LeetCode] Find Peak Element

A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.


解题思路：
用Binary Search


Python 解法：

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findPeakElement(self, num):
     def findPeakElementByBinarySearch(num, i, j):
      mid = (i + j)/2
      if mid < j and num[mid + 1] > num[mid]:
       return findPeakElementByBinarySearch(num, mid + 1, j)
      if mid > i and num[mid - 1] > num[mid]:
       return findPeakElementByBinarySearch(num, i, mid - 1)
      return num[mid]

     return self.findPeakElementByBinarySearch

[LeetCode] LargestNumber

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

解题思路：

关键就是判断大小的compare func

Python的解法：

class Solution:
    # @param num, a list of integers
    # @return a string
    def largestNumber(self, num):
     newNum = sorted([str(x) for x in num], cmp=self.compare)
     largeNum = ''.join(newNum) or '0'
     return largeNum

    def compare(self, a, b):
     return [1, -1][a + b > b + a]

[LeetCode]Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

解题思路：
这题还是挺巧妙的。由于每个node有一个指向随机结点的指针，而要找到此随机结点事很困难的。如果按照传统思路，新旧linkedlist分别为两个独立的linkedlist, 那对于新的linkedlist中的每个node来说，我们只知道对应的node在原来的linkedlist里指向的random 的node. 这是非常困难的，这的记住每个random node 在linkedlist 中的index, 这是非常复杂的。
所以，如果我们想到将新的node放到原来的linkedlist里，然后每个新的node都在对应旧的node的后面一位，那么我们就能很容易的找到新的random node了。因为每个新点的random node就是旧点的random node 的下一位。
总结下来，我们有三步：

1. copy the node
2. copy the random pointer
3. decouple the new linkedlist

Java Code:

public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode safehead = new RandomListNode(0);
           RandomListNode currP = head;
           
           //copy the node
           while(currP != null){
               RandomListNode tmp = new RandomListNode(currP.label);
               tmp.next = currP.next;
               currP.next = tmp;
               currP = tmp.next;
           }
           
           currP = head;
           //copy the random pointer
           while(currP != null){
               
               if(currP.random != null){
                  currP.next.random = currP.random.next;    
               }
               
               currP = currP.next.next;
           }
           
           //decouple the list
            RandomListNode p = safehead;
            currP = head;
            
            while(currP != null){
                p.next = currP.next;
                currP.next = currP.next.next;
                currP = currP.next;
                 p = p.next;
            }
           
            return safehead.next;
    }

[LeetCode] Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

解题思路：
找到中间点，然后左边就为其左子树，右边部分就为其右子树。
1. 找中间点，可以先扫描一遍list, 然后得出node的总数n, 然后n/2就是其中间点
2. 可以用两个pointer, 一个每次走1一步，另一个每次走2步。等走2步的pointer到达尾部时，走一步的pointer刚好走到中间位置。由于我们要找到中间位置的pointer. 所以我们找到了中间pointer的前一个node。

Java Code:

public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        ListNode safehead = new ListNode(0);
        safehead.next = head;
        
        ListNode prev = safehead;
        ListNode p = head;
        
        while( p != null && p.next != null){
            p = p.next.next;
            prev = prev.next;
        }
            
        TreeNode root = new TreeNode(prev.next.val);
        p = prev.next.next;
        prev.next = null;
        root.left = sortedListToBST(safehead.next);
        root.right = sortedListToBST(p);
            
        return root;
    }

[LeetCode] Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/ 

解题思路：

无向图的邻居，要注意避免重复建设node. 所以我们用一个hashmap来存储已经有的点。当遇到了已经有的点，直接从hahmap里取。

Java Code:

 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
       
        if(node == null){
            return null;
        }
        
        HashMap allnodes = new HashMap(); 
        List newnodes= new ArrayList();
        List oldnodes= new ArrayList();
       
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        allnodes.put(node.label, newNode);
        
        newnodes.add(newNode);
        oldnodes.add(node);
        
      do{  
          List newNext= new ArrayList();
          List oldNext= new ArrayList();
        
          for(int i = 0; i < oldnodes.size(); i++){
              UndirectedGraphNode oldnode = oldnodes.get(i);
            
            if(oldnode.neighbors == null){
                continue;
            }
            
            List oldneibors = oldnode.neighbors;
            List newneibors = new ArrayList();
            
            for(UndirectedGraphNode curr : oldneibors){
                UndirectedGraphNode newnode = null;
                if(allnodes.containsKey(curr.label)){
                   newnode = allnodes.get(curr.label);
                }else{
                  newnode = new UndirectedGraphNode(curr.label);
                  allnodes.put(curr.label, newnode);
                  newNext.add(newnode);
                  oldNext.add(curr);
                }
                newneibors.add(newnode);
            }                  
            newnodes.get(i).neighbors = newneibors;
        }
        
        oldnodes = oldNext;
        newnodes = newNext;
      }while(!oldnodes.isEmpty());
      
      return newNode;
    }

[LeetCode] Flattern Binary Tree To LinkedList

Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6 

解题思路：

1. 如果root同时有left, right, 则把right存到stack

2. 如果root有left, 则将root.right = root.left,即将左子 树移到右子树

3. 如果root == null, 则从stack pop出一个，将此作为root的右子树

4. 每次都将root.right 作为新的root， repeat 1-4

Java Code:

 public void flatten(TreeNode root) {
        TreeNode p = root;
        Stack tmp = new Stack();
        
        while(p != null){ 
            
         if(p.right != null && p.left != null){
             tmp.add(p.right);
         }
         
         if(p.left != null){
             p.right = p.left;
             p.left = null;
         }
         
         if(p.right == null && !tmp.isEmpty()){
             p.right = tmp.pop();
         }
         
         p = p.right;
        }
    }

[LeetCode] Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

 解题思路：
 1. 对于任何一个node, 有四种path情况需要考虑：
  1.1 仅有node
  1.2 左子树+node
  1.3 node + 右子树
  1.4 左子树 + node + 右子树

为了求最大的path sum. 我们需要从1-3中选出最大的返回给parent，从1-4中选出最大的作为备选的最后结果path sum.

Java Code:

public int maxPathSum(TreeNode root){
       int[] max = new int[1];
       max[0] = Integer.MIN_VALUE;
       maxSum(root, max);
       
       return max[0];
    }
    
    public int maxSum(TreeNode root, int[] max){
        int val = 0, left = 0, right = 0;
        
        val = root != null ? root.val : 0;   
        left = root.left != null? maxSum(root.left, max) : 0;
        right = root.right != null ? maxSum(root.right, max) : 0;
        
        int currMax = val;
        
        if(left > 0) currMax += left;
        if(right > 0) currMax += right;
        max[0] = max[0] > currMax? max[0] : currMax;
        
        if(left > 0 && left >= right) return val + left;
        if(right > 0 && right > left) return val + right;
        
        return val;
    }