This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

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:

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

String convert(string s, int numRows);

Example 1:

Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR”

Example 2:

Input: s = “PAYPALISHIRING”, numRows = 4 Output: “PINALSIGYAHRPI” Explanation: PINALSIGYAHRPI

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

6. Z transform

Ii. Analysis of Ideas:

  1. ifnumRowsIf it is 1, it is the original string.
  2. Declare a variable
    • rowsUsed to store z strings
    • flagCurrent storage direction (Direction: Up or Down)
    • rowCurrent store row
  3. Initialize therows, convenient for later use
  4. traverses
  5. Stores s[I] to the current line
  6. The following code is key, changing the direction of the current line pointer.
if(row <= 0 || row >= numRows - 1) {
    flag = flag == 1 ? -1 : 1;
}
Copy the code
  1. Changes the position of the row pointer based on the current direction
  2. Integrate string returns in rows

Iii. AC Code:

/ * * *@param {string} s
 * @param {number} numRows
 * @return {string}* /
var convert = function(s, numRows) {
    let len = s.length;
    if(numRows == 1) return s;
    let rows = [], flag = -1, row = 0;
    for(let i = 0; i < numRows; i++) rows[i] = ' ';
    for(let i = 0; i < len; i++) {
        rows[row] += s.charAt(i)
        if(row <= 0 || row >= numRows - 1) {
            flag = flag == 1 ? -1 : 1;
        }
        row += flag
    }
    return rows.reduce((str, cur) = > {
        return str + cur;
    }, ' ')};Copy the code

Iv. Summary:

Time complexity
O ( N ) O(N) : iterates over the string s;

Spatial complexity
O ( N ) O(N) : just stores the string once