第六周主题：数字 之 GrayCode in LeetCode (in java)

题目：

http://oj.leetcode.com/problems/gray-code/


要求：


The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2


Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.




解答：

画画就出来了。为了好分析，我们看n=4的情况，那么一共有2^4=16种codes


 
 


  
0
  
0
  
0
  
0
 

  
0
  
0
  
0
  
1
 

  
0
  
0
  
1
  
1
 

  
0
  
0
  
1
  
0
 

  
0
  
1
  
1
  
0
 

  
0
  
1
  
1
  
1
 

  
0
  
1
  
0
  
1
 

  
0
  
1
  
0
  
0
 

  
1
  
1
  
0
  
0
 

  
1
  
1
  
0
  
1
 

  
1
  
1
  
1
  
1
 

  
1
  
1
  
1
  
0
 

  
1
  
0
  
1
  
0
 

  
1
  
0
  
1
  
1
 

  
1
  
0
  
0
  
1
 

  
1
  
0
  
0
  
0
 

规律：

（1）第一列对半分成up 和down 部分， up都是0，down都是1；

（2）从二列开始，在前一列子列的基础上，再对半细分成up和down部分，如果在第一列的down部分，则需要把01序列倒过来。

References:

[1] 代码在

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

第四周主题：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