Check out more about algorithmic interviews here

Topic describes

Take a given string s and arrange it in a zigzag form from top down and left to right, based on the given number of rows, numRows.

For example, if the input string is “PAYPALISHIRING” and the number of rows is 3, it will be arranged as follows:

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 that transforms a string to 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 = output: “PINALSIGYAHRPI”

Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I
Copy the code

Example 3:

Input: s = “A”, numRows = 1

 

Tip:

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

Intuitive law solution

We can think of this as a simulation.

To print line I traversal, the first character of each line can be directly determined: the i-th character beginning with the original character.

Then calculate the offset of the next character in each line. Here we need to discuss separately:

  • For the first and last rows: the offset is fixed and does not change in the direction of Z

  • For other rows: The offset changes with the direction of Z

class Solution {
    public String convert(String s, int r) {
        int n = s.length();
        if (n == 1 || r == 1) return s;

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r; i++) {
            if (i == 0 || i == r - 1) {
                int j = i;
                int rowOffset = (r - 1) * 2 - 1;
                while (j < n) {
                    sb.append(s.charAt(j));
                    j += rowOffset + 1; }}else {
                int j = i;

                int topRow = i;
                int topOffset = topRow * 2 - 1;

                int bottomRow = r - i - 1;
                int bottomOffset = bottomRow * 2 - 1;

                boolean flag = true;
                while (j < n) {
                    sb.append(s.charAt(j));
                    j += flag ? bottomOffset + 1 : topOffset + 1; flag = ! flag; }}}returnsb.toString(); }}Copy the code

Time complexity: Print each character in S separately. The complexity is O(n)O(n)O(n)

Space complexity: O(1)O(1)O(1)

Mathematical law solution

In the usual practice, for this kind of finding the rule of the problem, when we use intuitive reasoning to deduce a solution, we can try to analyze from the perspective of mathematics.

In this case, for example, we can derive the law as “first term” and “tolerance formula” without loss of generality.

This often works to reduce some of the judgment.

Discussion by case:

  • For the first and last rows: arithmetic sequence with a tolerance of 2 * (n − 1), the first term is I

  • For the other rows: Two arithmetic sequences of tolerance 2 * (n − 1) are arranged alternately, starting with I and 2 * n − I − 2, respectively

class Solution {
    public String convert(String s, int r) {
        int n = s.length();
        if (n == 1 || r == 1) return s;

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r; i++) {
            if (i == 0 || i == r - 1) {
                int pos = i;
                int offset = 2 * (r - 1);
                while(pos < n) { sb.append(s.charAt(pos)); pos += offset; }}else {
                int pos1 = i, pos2 = 2 * r - i - 2;
                int offset = 2 * (r - 1);
                while (pos1 < n || pos2 < n) {
                    if (pos1 < n) {
                        sb.append(s.charAt(pos1));
                        pos1 += offset;
                    }
                    if(pos2 < n) { sb.append(s.charAt(pos2)); pos2 += offset; }}}}returnsb.toString(); }}Copy the code

Time complexity: Print each character in S separately. The complexity is O(n)O(n)O(n)

Space complexity: O(1)O(1)O(1)

conclusion

This “find the rule” of the simulation, and primary school olympiad questions are very similar. In order to improve their level, we need to adhere to two directions:

  1. Oneself draw a picture to find a rule on paper more, this kind of problem does not have what general solution

  2. Do more questions and try to get in touch with each “rule”

The last

This is the sixth article in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

Since the number of questions of LeetCode continues to increase with the weekly and biweekly competitions, in order to facilitate our statistical progress, we will calculate the progress according to the total number of questions at the beginning of the series as the denominator and the completed problems as the numerator. The current progress is 6/1916.

In order to facilitate you to debug and submit your code on the computer, I have set up a warehouse: Github address & Gitee address.

In the repository address, you can find the solution to the series, the corresponding code for the series, the link to the original LeetCode, and some other preferred solutions.


# Algorithms and data structures

# LeetCode antithesis

# Algorithmic interview