This is the 30th day of my participation in the August Text Challenge.More challenges in August

Z transformation (Item No. 6)

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 = 3Output:"PAHNAPLSIIGYIR"
Copy the code

Example 2:

Enter: s ="PAYPALISHIRING", numRows = 4Output:"PINALSIGYAHRPI"P I N A L S I G Y A H R P ICopy the code

Example 3:

Enter: s ="A", numRows = 1Output:"A"
Copy the code

Tip:

  • 1 <= s.length <= 1000
  • sConsists of letters (lowercase and uppercase),', ' 和 '. 'composition
  • 1 <= numRows <= 1000

link

Leetcode-cn.com/problems/zi…

explain

This one, this one is classic.

I personally feel that the title is not very easy to understand, what is the word Z?

After looking at the example for a long time, I understood that the original Z was first rotated 90 degrees clockwise and then inverted by mirror image.

To be honest, who would have thought of that, if you hadn’t looked at the examples and analyzed them like crazy, you wouldn’t have thought of all right, this is a great problem, it takes about 20 minutes just to read the question.

Figure out the meaning of the question and look at the arrangement of the letters. In fact, there are two steps:

  1. Photograph in a vertical line from top to bottom

  2. And then you go from bottom to top, left to right and you get a slanted line with the number of columns minus 1, which is the second argument minus 1. For every step you take, you move one position up and one position to the right

These two steps can actually form a cycle, starting from the first step, after the first step to the second step, the second step to the end is actually the beginning of the first step, then continue to take the first step, until the position is finished.

Now that we’ve figured out these two steps, it’s actually a little bit easier to figure out the solution to this problem.

Make two variables, one to store the current column, and the other to store the direction, because the direction of the first step is up, and the direction of the second step is down. Update the direction at the end of the second step, do the reverse, and update the column data at each step of the second step, ensuring that the data goes from bottom up and left to right during the second step.

So how do you store the data? Take an array, the length of which is the second argument, the number of rows, and then insert more and more data into it, resulting in the same data structure as in the explanation.

A join is the final answer.

Of course, this is a relatively simple solution, which has O(n) space complexity. If you then use a value to iterate over the current string, that is, to access the letter by position, you can use O(1) space complexity to solve the problem, which is explained in detail in the answer.

Your own answers (in line order)

var convert = function(s, numRows) {
  if (s.length === 1) return s
  const rows = new Array(numRows).fill(' ')
  let curRow = 0
  let goingDown = false
  for (const char of s) {
    rows[curRow] += char
    if (curRow === 0 || curRow === numRows - 1) { goingDown = ! goingDown } curRow += goingDown ?1 : -1
  }
  return rows.join(' ')};Copy the code

The code is written along the same lines and doesn’t need much introduction.

Because the loop does not use index, directly for… Of will do.

At the end of step 1 and step 2, just take the inverse value of goingDown instead of assigning it to true or false.

That’s pretty much it. That’s it.

A better way (row access)

To tell the truth, I have thought of this solution, but unfortunately did not write it out, and finally refer to the official answer.

Take a look at the code 👇 :

var convert = function(s, numRows) {
  if (numRows === 1) return s
  let res = ' '
  const len = s.length
  const cycleLen = 2 * numRows - 2
  for (let i = 0; i <numRows; i++) {
    for (let j = 0; j + i < len; j+=cycleLen) {
      res += s[j + i]
      if(i && i ! == (numRows -1) && (j + cycleLen - i) < len) {
        res += s[j + cycleLen - i]
      }      
    }    
  }
  return res
};
Copy the code

It’s a little bit confusing, but it’s fine, just row by row.

How to access by row?

So let’s start with the first row, and sweep from left to right, what’s the interval of each element? How much is the difference between the first row or the adjacent elements of each row?

Here we can discuss three cases:

  1. First row element

    This is probably the best thing to figure out, which is 2 * numrows-2, so you just need to figure out how many elements there are in the first row as you go through the loop and add them

  2. Last row element

    2 * numrows-2 + I; 2 * numrows-2 – I; 2 * numrows-2 – I;

  3. Other elements

    2 * numrows-2 + numrows-1 = numrows-2 + numrows-1

These three cases, 👆, can be grouped into two cases, which are the two places in the code where res is assigned.

To tell the truth, here is really not easy to understand, and more around, the author’s code is also looking at the official solution in the C++ code a little bit of translation, if still can not understand you can click here to refer to the official solution, try ~





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)