Monthly Archives: January 2016

Burst Balloons

Problem source: https://leetcode.com/problems/burst-balloons/

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

Solution: This problem is a good exercise for dp.

First of all, we extend nums[] with 1 on each side. For example, we extend [3, 1, 5, 8] to [1, 3, 1, 5, 8, 1]. Let’s define dp[][]. dp[left][right] means the maximum value when we burst all balloons between nums[left] to nums[right](pay attention that balloons left and right are not included). For [1, 3, 1, 5, 8, 1], the result is dp[0][5]. And we have dp formula:

balloonburst

check my code on github: link

Use proxy_mod to redirect apache to tomcat

Recently, I moved my legacy blog PersonalPage to newer wordpress on Amazon ec2. WordPress is on apache php. Old peronalpage was wrote on tomcat. They are running on different ports. Today, I configured that I only visit through same port by using mod_proxy. By mod_proxy, all the request www.allenlipeng47.com/PersonalPage will forward to www.allenlipeng47.com:8080/PersonalPage

In httpd, add below at the end of httpd.conf file
LoadModule proxy_module modules/mod_proxy.so
ProxyPass /PersonalPage http://www.allenlipeng47.com:8080/PersonalPage
ProxyPassReverse /PersonalPage http://www.allenlipeng47.com:8080/PersonalPage

In tomcat, add below proxyPort=”80″ at connector 8080 part:
<Connector port=”8080″ protocol=”HTTP/1.1″ proxyPort=”80″ />

Done. After I open my legacy www.allenlipeng47.com/PersonalPage website, it shows successfully.

Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Solution. We use a nums[] array to record how many times each letter happen in string. We use a stack to store the result. Then we go through each char ch. If ch already visited, then continue. If not visited, and ch is smaller than stack.top() and it still has stack.top() later(nums[stack.top()] > 0), then we pop stack.top().

check my code on github: link

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[]: Small is more element.  so put small first.(Or in another word 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