This is the 9th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The title

Arrange a given string s in zigzagging from top to bottom and left to right, numRows, according to the given number of rows.

For example, if the string “PAYPALISHIRING” is set to 3 rows, it will look like this:

P   A   H   N
A P L S I I G
Y   I   R
Copy the code

After that, your output needs to be read line by line from left to right, producing a new string, such as “PAHNAPLSIIGYIR”.

Implement this function to convert a string to the specified number of lines:

string convert(string s, int numRows);

Example 1:

Enter: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR” Example 2: Enter: S = “PAYPALISHIRING”, numRows = 4 Output: “PINALSIGYAHRPI” explanation:

P     I    N
A   L S  I G
Y A   H R
P     I
Copy the code

Example 3:

Input: s = “A”, numRows = 1 output: “A”

Tip:

1 <= s.length <= 1000 s Consists of lowercase and uppercase letters,’,’, and ‘.’. 1 <= numRows <= 1000

Train of thought

First of all, look at the topic for a long time, did not understand the z shape?

It turns out that if you look at it horizontally, it’s z. If you look at it vertically, it’s N

Convert the original string to char[], rearrange the subscripts of the array, and finally form a new string output based on the reorganized subscripts. You can split the entire output into the same units as shown above

L        D        R
E   O    E   I    I
E C      I H      N
T        S        G
Copy the code
  • 2 * numRows – 2
  • 2 * (numRows – I) or 2 * current row – 2.

In fact, row by row, except for the first and last lines, there is a letter between the two cells in each row, and we call the space to the left of the letter leftSpace and the space to the right rightSpace, starting at the second line, all the subscripts in this row start at 1, We can also write the first row of all subscripts as alternating additions of leftSpace and rightSpace, but because the rightSpace of the first row is 0, the same result will occur twice. In this case, we need to do special treatment and only remember once

public  String convert(String s, int numRows) {
    // No conversion is required at this point
    if (numRows <= 1) {
        return s;
    }
    char[] data = s.toCharArray();
    int[] resultIndex = new int[data.length];
    // The length of the left space between each cell
    int leftSpace = 2 * numRows - 2;
    // The length of the right space between each cell
    int rightSpace = 0;
    for (int i = 0, index = 0; i < numRows && index < data.length; i++) {
        int max = i;
        // Switch used to control the left and right space alternately add
        boolean flag = true;
        // It is used to compare whether the two subscripts added before and after are the same. It is used to deal with the problem that the same subscript will be added twice because the first and last lines have no spacing letters
        int lastAdd = i;
        // The beginning of each line is fixed to (line number -1)
        resultIndex[index] = i;
        index++;
        // Control the maximum index for each row
        while (data.length - 1 >= (flag ? max + (leftSpace - i * 2) : max + (rightSpace + i * 2))) {
            if (flag) {
                max = max + (leftSpace - i * 2);
                flag = false;
            } else {
                max = max + (rightSpace + i * 2);
                flag = true;
            }
            if(max ! = lastAdd) { resultIndex[index] = max; index++; lastAdd = max; } } } StringBuilder sb =new StringBuilder();
    for (int i = 0; i < resultIndex.length; i++) {
        sb.append(data[resultIndex[i]]);
    }
    return sb.toString();
}
Copy the code

Execution time: 2 ms, beating 99.99% of users in all Java commits

Memory consumption: 38.1 MB, beating 98.86% of all Java commits

Another way to do it

The above solution is mainly divided into multiple groups to find the rule in the following table and then join the string. In fact, the rule divided into left and right intervals is not particularly easy to find, and the implementation is tedious.

Let’s observe that as we traverse the string s sequentially, each character C increments to the maximum, then to the minimum, in the zigzag line index

That is, when printing out the zigzag sequence, the character line number is 0-> Max ->0-> Max…. – > end changes

Therefore, we can simulate the process of printing z-shape, store each line of data, and finally splicing the output result into a string according to the line number is the final result

 public static String convert2(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        The StringBuilder is used to store each row of data
        StringBuilder[] rows = new StringBuilder[numRows];
        Arrays.setAll(rows, i -> new StringBuilder());
        int row = 0, flag = -1;
        for (int j = 0; j < s.length(); j++) {
            // append to line n
            rows[row].append(s.charAt(j));
            // If the number of rows is 0 or maximum, the flag bit needs to be reversed
            // The purpose of the rollover is to continue the row with a uniform +=flag
            if (row == 0 || row == numRows - 1) {
                flag = -flag;
            }
            row += flag;
        }
        return String.join("", rows);
    }

Copy the code

Execution time: 8 ms, beating 34.18% of all Java commits

Memory consumption: 38.9 MB, beating 50.74% of all Java commits

Although the efficiency is reduced, the readability and comprehension are greatly improved. At the same time, this kind of thinking is more in line with people’s mental model and easier to remember. Therefore, I personally think that this kind of answer can meet the requirements if confronted with this question.

The more you learn today, the less you beg tomorrow