第六周主题：数字 之 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

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的函数。

第二周主题：链表 之 Linked List Cycle in LeetCode (in java)

题目：

http://oj.leetcode.com/problems/linked-list-cycle/

http://oj.leetcode.com/problems/linked-list-cycle-ii/



要求：
I Given a linked list, determine if it has a cycle in it.


II Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */


(给定一个ListNode结构的链表，(I)看是否有cycle；(II)看循环在哪个节点，如果没有cycle，返回null)




解答：




(I) 设定两个index node: slow and fast，沿着链表的顺序跑下去：slow跑得慢，每次跑一步；fast跑得快，每次跑两步。如果有cycle的话，迟早两个index是会相遇的。




(0) ListNode slow = head; ListNode fast = head;

(1) while (true) 循环内slow = slow.next; fast = fast.next.next; (注意先判断fast.next是否为null)

fast.next == null -> return false;
slow == null -> return false;
fast == null -> return false;
slow == fast -> return true;





(II) 假设找到了cycle (slow == fast)，怎么找是哪个节点开始呢？我们引入一个ListNode pre = head; pre每次跑一步，slow循环一圈找是否slow == pre。那怎么判断slow是否循环一圈呢？别忘了，我们的fast还在那呢，保持fast不动，只要看是否slow == fast就知道了。

(0) slow == fast is true

(1) while (pre != slow) 循环内 slow = slow.next;

slow跑圈 


while ((slow != pre) && (slow != fast)) {
 slow = slow.next;
}

 如果slow跑完了，或者遇到pre了



if (slow == pre)

break;

else

pre = pre.next;




(2) return slow;

References:

[1] 代码在
https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/LinkedListCycle.java
https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/LinkedListCycleII.java

LeetCode Notes001

Albert Chen's Week001

• MergeSortedArray (Solution088)

http://oj.leetcode.com/problems/merge-sorted-array/
Merge from the end

• SingleNumberII (Solution137)

http://oj.leetcode.com/problems/single-number-ii/

（0）初始设定ones=0; twos=0;
（1）用twos记录到当前为止，二进制”1“出现3k+2次的位数；twos = twos | (ones & A[i]);
（2）用ones记录到当前为止，二进制“1”出现3k+1次的位数；ones = ones ^ A[i];
（3）当ones和twos的某一位同时为”1“时，即该位出现二进制”1“ 3k+3次（也就是3k次），清零该位。xthrees = ~(ones & twos); // xthrees 是二进制“1”没有出现3k次的位数ones = ones & xthrees;twos = twos & xthrees;
（4）遍历完数组中所有的数之后，ones记录的就是最终结果。

• SortColors (Solution075)

http://oj.leetcode.com/problems/sort-colors/
int i = 0; // for end of zeros
int j = n; // for start of twos;
int k = 0; // iterator

• Permutation(Solution045), PermuationII(Solution046), NextPermutation(Solution030)

http://oj.leetcode.com/problems/permutations/
http://oj.leetcode.com/problems/permutations-ii/
http://oj.leetcode.com/problems/next-permutation/

(0)  input: int[] num
(1) sort(num)
(1.5) do {add}while (nextPermutation is true)
(2-7) boolean nextPermutaion()

• (2-6) 循环体
• (2) 从后往前找到最大的倒序subarray of num (i, num.length-1)
• for i = num.length-1; i >0; i--
• if num[i-1]<num[i]
• (3) 从后往前在subarray里找到第一个num[j]大于num[i-1]
• for j = num.length-1; j>=i; j--
• if num[j]>num[i-1]
• (4) swap(num[j],num[i-1])
• (5) reverse subarray (i, num.length-1)
• (6) return true
• (7) 终止条件，并且维持next permutation的语义
• reverse num(0, num.length-1) and return false;

第一周主题：数组 之 Single Number II in LeetCode (in java)

题目：http://oj.leetcode.com/problems/single-number-ii/

要求：

Given an array of integers, every element appears three times except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

(给定一个包含n个整数的数组，除了一个数出现一次外所有的整数均出现三次，找出这个只出现一次的整数。)




解答：

这是一道很有趣的位运算题。百思不得其解，最后看了[1]介绍的思路。

如果用二进制来表达数组中每一个数字的话，如果我们遍历一遍数组中的所有的数，即将数组中所有数的二进制表达的每位上的“1”都数一遍，那么除了需要找的那个只出现一次的整数外，其他所有的数字二进制表示中每一位“1”都出现了3k次（k为非负整数）。

如果能有办法将所有的二进制表达中这些3k个“1”清零，那么剩下的二进制表达就表示了需要找到的数。

（0）初始设定ones=0; twos=0;

（1）用twos记录到当前为止，二进制”1“出现3k+2次的位数；

twos = twos | (ones & A[i]);

（2）用ones记录到当前为止，二进制“1”出现3k+1次的位数；

ones = ones ^ A[i];

（3）当ones和twos的某一位同时为”1“时，即该位出现二进制”1“ 3k+3次（也就是3k次），清零该位。

xthrees = ~(ones & twos); // xthrees 是二进制“1”没有出现3k次的位数

ones = ones & xthrees;

twos = twos & xthrees;

（4）遍历完数组中所有的数之后，ones记录的就是最终结果。

扩展：

同样的道理，可以解决{给定一个包含n个整数的数组，除了一个数出现两次外所有的整数均出现三次，找出这个只出现两次的整数。}，return twos就行了。

更强的扩展: {给定一个包含n个整数的数组，有一个整数x出现b次，一个整数y出现c次，其他所有的数均出现a次，其中b和c均不是a的倍数，找出x和y。}可以参见[1]，思路是一样的。

Reference:

[1] leetcode Single Number II - 位运算处理数组中的数

[2] 代码在 https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/SingleNumberII.java