Algorithm practice - Z-font transformation

Z-font Transformation:

The solution of this problem is only for personal understanding. If there are other ideas or solutions, welcome to explore!
Buckle link: Z igzag transformation

Title:

A given string s is arranged in a zigzag manner from top to bottom and from left to right according to the given number of rows numRows.

For example, when the input string is "paypalishing" and the number of lines is 3, the arrangement is as follows:

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

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

Please implement this function to transform the string to the specified number of lines:

String convert(String s, int numRows);

Example:

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
 Output:"PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
 Output:"PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
 Output:"A"

analysis:

Since the title does not require the output of the Z-font transformed style, only the final string result should be output. So when I do this problem, I'm actually looking for the law of Z-font Transformation:

Let's take the input string given by the title as an example. When the input string s = "paypalishing", numRows = 4, the result of Z-font transformation is "PINALSIGYAHRPI":

Input: s = "PAYPALISHIRING", numRows = 4
Z-Font transformation and arrangement explanation:
P →→→ I →→→ N
A → L S → I G
Y A → H R
P →→→ I
 Output:"PINALSIGYAHRPI"

Here, we should not be affected by the shape of Z-font transformation. We can compress its shape, and the output remains unchanged, which seems more convenient to understand:

P   I   N
A L S I G
Y A H R
P   I
 Output:"PINALSIGYAHRPI"

Then replace the of each character with the subscript of its string to get a string arranged as follows. At this time, we can find that the difference between the corresponding positions of the longer columns is 6. After looking at several permutations, we can conclude that the formula is dvalue = 2 * NumRows - 2 (minus 2 because there are no elements in the first and last rows of the second column):

0     6      12
1  5  7  11  13
2  4  8  10
3     9
 Difference: DValue = 2*4-2

At this time, we regard the first column and the second column as a whole, then divide this group of strings into three parts: head, body and tail, find their laws, and find that each element can be written as i * DValue + j and its variants; Moreover, in the body part, we found that j1 in the first column and j2 in the second column satisfy j1 + j2 = DValue:

//First output head (i * DValue)
0 * 6 + 0 |           | 1 * 6 + 0 |           | 2 * 6 + 0

//Then output the body (i * DValue+j)
0 * 6 + 1 | 0 * 6 + 5 | 1 * 6 + 1 | 1 * 6 + 5 | 2 * 6 + 1
0 * 6 + 2 | 0 * 6 + 4 | 1 * 6 + 2 | 1 * 6 + 4 | 

//Last output tail (i * DValue + numRows - 1)
0 * 6 + 3 |           | 1 * 6 + 3 |           |

Now that the law has been found, clear your mind and start writing code

code:

First look at the above analysis! Understand and think for yourself. Don't look at the code in a hurry!

public String convert(String s, int numRows) {  //s is the input array and numRows is the required number of columns
        //When the length of S is less than numRows and numRows==1, s is returned directly
        if (s.length() < numRows || numRows == 1){
            return s;
        }

        //Difference between two column numbers
        int DValue = 2 * numRows - 2;
        //Create an array object to store the spliced array. Objects can be modified multiple times without generating new unused objects.
        //Because StringBuilder has speed advantages over StringBuffer, StringBuilder is used
        StringBuilder newStr = new StringBuilder();

        //Output the first line (i*DValue)
        for (int i=0 ; i * DValue < s.length() ; i++){
            //The loop is entered when the first number in the last column is less than the total length of the array
            newStr.append(s.charAt(i * DValue));//charAt is the character returned at the specified index; append is to store the read data in this sequence
        }

        //Output intermediate (i*DValue+j)
        for (int j=0 ; j < numRows - 2 ; j++){
            for (int i = 0; i * DValue  + j + 1 < s.length(); i++ ){
                //Entry loop that is not the first or last line
                newStr.append(s.charAt(i * DValue  + j + 1));//Output only columns 1, 3, 5

                if (i * DValue + (DValue - j - 1) < s.length()){
                    newStr.append(s.charAt(i * DValue + (DValue - j - 1)));
                }
            }
        }

        //Output the last line (i*DValue+numRows-1)
        for (int i=0 ; i * DValue + numRows - 1 < s.length() ; i++){
            //The loop is entered when the last number in the last column is less than the total length of the array
            newStr.append(s.charAt(i * DValue + numRows -1));
        }

        return newStr.toString();
    }

Finally, the operating efficiency obtained in the force buckle:

Keywords: Java Algorithm

Added by blaster_master on Fri, 14 Jan 2022 09:05:19 +0200