LeetCode6: ZigZag Conversion

Welcome to my personal website

LeetCode:https://leetcode-cn.com/problems/zigzag-conversion/

LeetCodeCn:https://leetcode-cn.com/problems/zigzag-conversion/

Topic describes

Arranges a given string in a zigzagging pattern from top to bottom and left to right according to the given number of lines.

For example, if the input string is “LEETCODEISHIRING” with 3 rows, it will look like this:

L C I R

E T O E S I I G

E D H N

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

The sample

  • Example 1:

    • Enter: s = “LEETCODEISHIRING”, numRows = 3
    • Output: “LCIRETOESIIGEDHN”

  • Example 2:

    • Enter: s = “LEETCODEISHIRING”, numRows = 4
    • Output: “LDREOEIIECIHNTSG”

Problem solving – induction

The idea is to iterate through the string once, generating the contents of each line directly from the resulting relationships.

Diagram related ideas

The following diagram shows the elements of a string of length 23 with 5 rows

We can split it into three parts setp(split step) = 2 * (numRows – 1), so we can also use length(s string length)/step to figure out how many parts we split

We continue to split for the first part, and we can see that the first and last rows have only one element, and the middle row with two elements, the sum of the steps of the two elements.

However, when we conclude the next group, we find that the sum of the two elements in the non-first row is not simply the step size, because the data in the non-first row is shifted by the step length. After induction, we can find that the value of the second element (15) in the non-first row is equal to the value of the first element in the next group (16) minus the number of current rows (1).

It’s pretty clear how to do this, but remember to increase the length by step as you loop through the inner layer. In non-leading-trailing lines, the second element needs to be verified to be less than length

Code implementation

public String convert(String s, int numRows) {
      if (numRows == 1) {return s;
      }
      int length = s.length();
      StringBuffer result = new StringBuffer();
      int step = 2 * (numRows - 1);

      for (int i = 0; i < numRows; i++) {
          for (int j = 0; j + i < length; j += step) {
              result.append(s.charAt(j + i));
              if(i ! =0&& i ! = numRows -1&& j + step - i < length){ result.append(s.charAt(j + step - i )); }}}return result.toString();

  }
Copy the code

You are welcome to pay attention to the relevant code and put forward suggestions for improvement