153 Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Thoughts:

Python Codes:

108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Thoughts:

Make the number in the middle of the array the root of the BST, then construct the sub trees recursively with binary search.

Python Codes:

89 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.

Thoughts:
GrayCode(http://en.wikipedia.org/wiki/Gray_code)
PS: this is an interesting article to read :)

Python Codes:

75 Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.


Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?


Thoughts:
一开始想到的就是计数排序，但是计数排序需要两边扫描，第一遍统计红，白，蓝的数目，第二遍生成新数组。

考虑到题目要求one pass。这就意味着类似于链表的双指针问题，这里也要track两个index，一个是red的index，一个是blue的index，两边往中间走。

i从0到blue index扫描，
遇到0，放在red index位置，red index后移；
遇到2，放在blue index位置，blue index前移；
遇到1，i后移。
扫描一遍得到排好序的数组。时间O(n)，空间O(1)
credits: http://bit.ly/1I53sCI

Python Codes:

12 Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Thoughts:
这道题主要就在于如何处理每一位digit，并且按照区间不同处理：
1<=digit <=3
digit =4
digit = 5
5<digit<=8
digit =9
credits: http://bit.ly/1OmnkR0

Python Codes:

116 Populating Next Right Pointers in Each Node

Given 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  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Thoughts: 

当前层处理完next指针的连接以后，再调用下一级节点。

Python Codes: 

The Declaration

This blog will be an honest collection of my learning in my domain as well as in my life. Hope I'll stick to it as long as I can!

Since much of the content were open-source materials out there, I didn't put too much effort citing all the origins. Please let me know if it upsets you and I'll remove or add appropriate citations ASAP.

Last but not least: F*#K OFF, PROCRASTINATION!!!