Daily Archives: January 3, 2016

Gray code

The original problem is from leetcode: https://leetcode.com/problems/gray-code/

And I found a very good solution from Wolfram: The code is called reflected because it can be generated in the following manner. Take the Gray code 0, 1. Write it forwards, then backwards: 0, 1, 1, 0. Then prepend 0s to the first half and 1s to the second half: 00, 01, 11, 10. Continuing, write 00, 01, 11, 10, 10, 11, 01, 00 to obtain: 000, 001, 011, 010, 110, 111, 101, 100, … (OEIS A014550). Each iteration therefore doubles the number of codes.

graycode

In this way, the problem can be solved in linear time.

Chek my code on github: link

Create maximum number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

In order to solve this problem, we should firstly build int[] maxNumber(int[] num, int k) function, which returns maximum int array from num[] with length k.
For example:
num[] = {9, 2, 5, 3, 8}, k = 5, return {9, 2, 5, 3, 8}
num[] = {9, 2, 5, 3, 8}, k = 4, return {9, 5, 3, 8}
num[] = {9, 2, 5, 3, 8}, k = 3, return {9, 5, 8}
num[] = {9, 2, 5, 3, 8}, k = 2, return {9, 8}

In order to achieve this function, we use a stack. Basic idea is that it pops stack top if next element is greater than stack top, and number of rest element is enough to fill k elements in stack.

We still need to create a compare function. int compare(int[] num1, int i, int[] num2, int j)
It returns positive if num1{i, i+1,…} is “greater” than num2{j, j+1, …}.
It returns negative if num1{i, i+1,…} is “less” than num2{j, j+1, …}.
It returns negative if num1{i, i+1,…} is “equal” to num2{j, j+1, …}.
For example,
num1 = {9, 2, 5, 8, 3}, i = 1, int[] num2= {5, 6, 6}, j = 0. Then we know 2583 is less than 566. So return negative number.
num1 = {9, 2, 5, 8, 3}, i = 2, int[] num2= {5, 6, 6}, j = 0. Then we know 583 is greater than 566. So return positive number.

Then the final solution is that we use this maxNumber function build i elements array from nums1 and k – i elements from nums2(i belongs to [0,…,k]). Then we merge them. When we merge, we should use compare to decide where the next element from.

check my code on github: link

 

Wiggle Sort II

This one is from leetcode: https://leetcode.com/problems/wiggle-sort-ii/
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]...
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

An old similar problem is wave sort. But in wave sort, it doesn’t has duplicate elements, which we can do it in linear time, O(1) extra space easily. link But for this problem, the difference is that it contains duplicate elements, which make it harder.

Ok, the solution is like below:
1. Sort array in descending order.
2. Put smaller elements into small[].
3. Put larger elements into large[].
4. Merge small[] and large[]: Put small in even position, put large in odd position

For example nums = [1, 2, 3, 4, 5].
Step 1, arr = [5, 4, 3, 2, 1]
Step 2, small = [3, 2, 1]
Step 3, large = [5, 4]
Step 4, arr = [3, 5, 2, 4, 1]

Another example nums = [4, 5, 5, 6]
Step 1, arr = [6, 5, 5, 4]
Step 2, small = [5, 4]
Step 3, large = [6, 5]
Step 4, arr = [5, 6, 5, 4]

check my code on github: link