LeeCode -- 6. Zigzag transformation

Brother Xiaojing's blog

Code warehouse

6. Z Font conversion

Will a given string s According to the given number of rows numRows , From top to bottom 、 Left to right Z Font arrangement .

For example, the input string is "PAYPALISHIRING" The number of rows is 3 when , Arranged as follows ：

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

after , Your output needs to be read line by line from left to right , Generate a new string , such as ："PAHNAPLSIIGYIR".

Please implement this function to transform a string into a specified number of lines ：

string convert(string s, int numRows);

Example 1：

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

Example 2：

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

Example 3：

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

Tips ：

• 1 <= s.length <= 1000
• s By the English letters ( Lowercase and upper case )、',' and '.' form
• 1 <= numRows <= 1000

Algorithm implementation ideas ：

We put the string s As an array , This array subscript counts from zero , Until s The length of . according to Z Transformational thinking , hold s Fill in the table with the subscript of .

When numRows=3 When , The order is as follows ：

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-CRRNabhx-1657178615583)(http://nas.hepcloud.top:6391/images/2022/07/07/image-20220707150657666.png)]

When numRows=6 When , The order is as follows ：

When numRows=n+1 When , The order is as follows ：

Let's start with line zero and take characters , Take the first 0 individual , Then take the 2n individual , And then take 4n individual , Get the string all the way s The maximum length that can be taken . Then go to the first line , Take the first 1 individual , Then take the 2n-1 individual , Then take the 2n+1 individual , Get the string all the way s The maximum length that can be taken . Follow this idea until n That's ok . Because we stipulate that numRows=n+1, The last line is n That's ok .

Let's set the variable i from 0 To n Cycle through , Which line is marked . Set a variable j,j=0,2,4,6,8, … The reason for this setting is , Because it is convenient to calculate the subscript position of a line .j * n + i For the current element , that (j + 2) * n - i Is the position of the next element immediately after it , If there is one . Limit j * n + i and (j + 2) * n - i All less than s It's just as long as you want .

class Solution {
    
    public  String convert(String s, int numRows) {
    

        int n = numRows - 1;
        String res = "";

        if(numRows == 1){
    
            return s;
        }

        for(int i = 0; i < numRows; i++){
    

            for(int j = 0; j * n + i < s.length(); j = j + 2){
    
				//j * n + i For the current element 
                if(j * n + i < s.length()){
    
                    res = res + String.valueOf(s.charAt(j * n + i));
                }
				//(j + 2) * n - i yes j * n + i The next element 
                if((j + 2) * n - i < s.length() && i != 0 && i != n){
    
                    res = res + String.valueOf(s.charAt((j + 2) * n - i));
                }

            }

        }

        return res;
    }
}