第四周主题：Decrease and Conquer (减治法) 之 Best Time to Buy and Sell Stock III in LeetCode (in java)

题目：

http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/


要求：

 /**

  * Say you have an array for which the ith element is the price of a given

  * stock on day i.

  * 

  * Design an algorithm to find the maximum profit. You may complete at most

  * two transactions.

  * 

  * Note: You may not engage in multiple transactions at the same time (ie,

  * you must sell the stock before you buy again).

  */
(找出对某只股票能获得的最大收益，最多只能买卖两次，买了之后才能卖，卖了第一次之后才能买第二次)



解答：

分两步，分别找出在[0,i]和[i,n-1]之间的最大收益，[0,i]正序查找, [i,n-1]逆序查找，这样对于某个特定点i来说，[0,i]和[i,n-1]区间不会重合。
(0)

int[] maxProfits = new int[prices.length]; // save the max profits
maxProfits[0] = 0;

int minPrice = prices[0];
  int maxProfit = 0;
  int profit = 0;
  for (int i = 1; i < prices.length; i++) {
   profit = prices[i] - minPrice;
   if (profit > maxProfit){  //比较最大收益
    maxProfit = profit;
   }
   maxProfits[i] = maxProfit;
   if (prices[i] < minPrice){ //比较价格最小值
    minPrice = prices[i];
   }
  }

(2)

int both = maxProfits[prices.length-1];
  int maxPrice = prices[prices.length-1];
  maxProfit = 0;
  int temp = 0; //临时存放当前两次交易的最大收益
  for (int i = prices.length-2; i>=0; i--) {
   profit = maxPrice - prices[i]; 
   if (profit > maxProfit){ //比较最大收益
    maxProfit = profit;
   }
   temp = maxProfit + maxProfits[i];
   if (temp > both){
    both = temp;
   }
   if (prices[i] > maxPrice){ //比较价格最大值
    maxPrice = prices[i];
   }   
  }

最后return both

References:

[1] 代码在

https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/BestTimeToBuyAndSellStockIII.java

第三周主题：树 之 Linked List Cycle in LeetCode (in java)

题目：

http://oj.leetcode.com/problems/recover-binary-search-tree/


要求：

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?


/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */


(一个二叉树的两个元素被错误的交换了，在不改变结构的前提下修复这个二叉树)




解答：

O(1)挺难的，想了很久。

这个解法的关键点是中序遍历inorder travel如何才能不使用栈。查了很久，才明白这个要用十多年前数据结构课上，杀手曾经教过的线索二叉树Threaded Binary Tree。




关键点中的关键是：给每一个现在访问的节点current临时再找一个parent节点，该parent节点是其中序遍历时紧邻前面的一个节点，parent.right=current，有这样的临时parent，中序遍历时就不需要栈了。



那么这个parent节点在哪呢？应该是current节点为root的左子树最右边的那个节点。



怎么找这个parent节点呢？

我们这么来:

(1)如果左边走不动了（current.left==null）就往右边走

parent=current; current=current.right;

(2)当往左边可以走时，先找一个临时的pre=current.left;

让后让这个pre一直找.right，pre.right=null为止，这时pre就是current节点为root的左子树最右边的那个节点，就可以设while (pre.right!=null){


     pre = pre.right;

    }

(3) 但这里有个问题，你设了pre.right=current; 不就破坏了树的结构了吗？而且pre也没有被current走到过啊（current=pre的时候才算走到）。于是需要在这里做一个判断：

(3-1) if (pre.right == null){ pre.right = current; current = current.left;} 设定好临时parent，并且继续往左走；

(3-2) if (pre.right == current) {pre.right=null; parent = current; current=current.right;} pre.right == current说明该current左边的路已经走过了，该走右边了。过河拆桥，pre.right=null;

(4) (2)里面循环条件改为while (pre.right!=null && pre.right != current){


        pre = pre.right;

       }

这样我们就有了不需要栈遍历树的算法。

接下来就是找到两个错误点了，在每次往右走之前做个判断看看parent.val是否大于current.val，如果大于的话就是错误点。

但如果找到第二个点的话，怎么知道这是第二个，不是第一个呢？引入一个变量found=false，找到第一个之后，就设为true。

注意，node1=parent，node2=current。因为node1肯定是两者里的大数，node2肯定是两者里的小数。


if (parent!=null && parent.val > current.val){

           if (!found){

            node1 = parent;

            found = true;

           }

           node2 = current;

}

遍历完树之后，swap node1和node2就行了。

这样就圆满了，oh yeah！

References:

[1] 代码在

https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/RecoverBinarySearchTree.java

Windows Phone App 8.0 Development (001) -- MiniBrowser

(1) in MainPage.xaml
in <phone:PhoneApplicationPage>
SupportedOrientations="PortraitOrLandscape" Orientation="Portrait"

(2) in MainPage.xaml
set        
<Grid x:Name="ContentPanel" Grid.Row="1" Margin="12,0,12,0">
<TextBox x:Name="TestBoxUrl" Margin="10,10,85,0" TextWrapping="NoWrap" Text="http://www.google.com" VerticalAlignment="Top"/>
<Button x:Name="ButtonGo" Content="Go" HorizontalAlignment="Right" Margin="346,10,0,0" VerticalAlignment="Top" Click="ButtonGo_Click"/>
<phone:WebBrowser x:Name="WebBrowserMini" Margin="10,82,0,0"/>
</Grid>

(3) in Mainpage.xaml.cs
set
        private void ButtonGo_Click(object sender, RoutedEventArgs e)
        {
            string site = TestBoxUrl.Text;
            WebBrowserMini.Navigate(new Uri(site, UriKind.Absolute));
        }

Windows Phone App 8.0 Development (000)

1) Install sdk8.0

2) register windows phone
How to register your phone for development.

3) for the error "Exception from HRESULT: 0x89721500"
Solution: delete the folder "C:\Users\<username>\AppData\Local\Microsoft\Phone Tools\CoreCon\11.0"

LeetCode Notes002

Albert Chen's Week002

• MergeSortedLists

Solution064

• SortList

Soution148

使用MergeSort，用快慢指针找中间点。
ListNode slow = slow.next;
ListNode fast = fast.next.next;

• MergeKSortedLists 

Solution022

先设定:
最小值min = Integer.Max_VALUE;
最小值所在list序号minList = 0;
已经到结尾的list数目count = 0;

如果某list到了末尾, count++;
每一步比较所有list的head，在循环内将最小的数加入min，并且记录该list的序号在minList

• LinkedListCycle LinkedListCycleII

Solution141
Solution142

http://rockylearningcs.blogspot.com/2014/02/linked-list-cycle-in-leetcode-in-java.html
LinkedListCycle(Solution141): 同上，使用快慢指针；
LinkedListCycleII(Solution142): 有更好的方法是：
(0) isCycle();
(1) 首先找出环的长度（在slow和fast相遇后，让他们继续走，再次相遇的时候，迭代次数就是环的长度C）
(2) 然后让一个指针从链表head开始点先走环的长度C
(3) 再令另一个指针从链表head开始点出发，这样这两个指针的相遇点就必然是交点。因为第一个指针走过了L + C步，第二个指针走过了L步。

• ReverseNodesInKGroup

Solution024
Albert Chen语：大体说来，思路就是取k个，前后标记好，然后把这k个挨个reverse了，然后前后再连好。。。

• CopyListWithRandomPointer

Solution138

Albert Chen语：这题有两种做法。一种是用辅助空间的，就是先把新的node都建好，在旧的node和新的node之间保持一个一一对应关系(比如，用hashmap)，然后把旧的关系拷贝到新的链表上来。这样会占用比较多的空间。

第二种方法如下所示，先为每一个节点建立一个拷贝：

原链表 A->B->C->D
带有拷贝的链表 A->A'->B->B'->C->C'->D->D'

这样为拷贝random pointer提供了一个便利，比如说，A的random pointer指向D，那么我们知道A的next指向A'，D的next指向D'，只要将A的next的random pointer指向D的next就可以了。

最后，NULL要特殊处理，清注意。
可以在Solution138 看到我生成RandomListNode list的函数。