Daily Archives: July 6, 2016

leetcode 6.

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Solution. An awesome solution is from this post. Basically, it uses a StringBuffer array to build vertical and oblique parts. Let’s say string is “PAHNAPLSIIGYIR” with 4 rows. And we have StringBuffer[] sbs

sbs[0]  P     I     N
sbs[1]  A   L S   I G
sbs[2]  Y A   H R
sbs[3]  P     I

In this way, to build vertical columns PAYP and ISHI, we can use below code:

for (int idx = 0; idx < numRows && i < len; idx++) {   // build vertical part
    sbs[idx].append(s.charAt(i));
}

In order to build oblique columns AL and RI, we can use below code:

for (int idx = numRows - 2; idx >= 1 && i < len; idx--) {  // build oblique part
    sbs[idx].append(s.charAt(i));
}

In the end, we concatenate the sbs[] array to get the result.

public static String convert(String s, int numRows) {
    StringBuffer[] sbs = new StringBuffer[numRows];
    for (int i = 0; i < numRows; i++) {
        sbs[i] = new StringBuffer();
    }
    int i = 0, len = s.length();
    while (i < len) {
        for (int idx = 0; idx < numRows && i < len; idx++, i++) {   // build vertical part
            sbs[idx].append(s.charAt(i));
        }
        for (int idx = numRows - 2; idx >= 1 && i < len; idx--, i++) {  // build oblique part
            sbs[idx].append(s.charAt(i));
        }
    }
    for (int j = 1; j < numRows; j++) {
        sbs[0].append(sbs[j]);
    }
    return sbs[0].toString();
}

Check my code on github.

leetcode 11.

Given n non-negative integers a₁, a₂, …, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Solution. This one has a greed solution which takes O(n) time and O(1) space. Set a left and right pointers to the pillars. Each time, calculate the area height[left] and height[right] can cover. Then, compare the height[left] and height[right], move the shorter pillar toward the center by 1 step.

Take a look at below example. Say we have pillars in both sides with height of h1 and h2.

From case1 and case2, we know, no matter what the right pillar will be, the area size(S2 or S3)will be always smaller than S1. This allow us to move the left pillar to right in order to find a larger size.

From case3 and case4, we know only when we move the pillar to another one which is taller than current pillar, then it would be possible to find a larger size.

My code on github.

public int maxArea(int[] height) {
    int max = 0, left = 0, right = height.length - 1;
    while (left < right) {
        int currArea = (right - left) * Math.min(height[right], height[left]);
        max = Math.max(max, currArea);
        if (height[left] < height[right]) { // move the shorter pillar inside
            left++;
        }
        else {
            right--;
        }
    }
    return max;
}