Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📢 preface

  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 6th day 🎈!
  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻

🌲 Example of original problem

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);
Copy the code

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
  • S consists of lowercase and uppercase letters,’,’ and ‘.’
  • 1 <= numRows <= 1000

🌻C# method: sort by row

When numRows>=3, diff = 4 +(numRows -3)2; The subscript for each row is row RTH. Each group should have two numbers except for the first and last lines. The first number of each group is aligned with the first line, The subscript difference is also diff and the subscript difference between the second and the first in each group is j = diff – 2r, because every time you increase the number of rows, you increase the number of rows below each vertical column, and you increase the number of rows up

public class Solution {
    public string Convert(string s, int numRows) {
        if (string.IsNullOrEmpty(s))
                return "";
            if (s.Length == 1)
                return s[0].ToString();
            if (numRows == 1)
                return s;
            int index = 0;
            char[] result = new char[s.Length];
            if (numRows == 2)
            {
                int halfLen = s.Length % 2= =0? s.Length / 2  :s.Length /2 +1;
                for (int i = 0, j = 1; i < s.Length;)
                {
                    if (i < s.Length){
                        result[index] = s[i];                        
                    }
                    if (j < s.Length&&index+halfLen<s.Length){
                        result[index+halfLen] = s[j];
                    }
                    index++;
                    i += 2;
                    j += 2;
                }
                return new string(result);
            }

            int diff = 4 + (numRows - 3) * 2;
            int r = 0; 
            while (r < numRows)
            {
                if (r == 0 || r == numRows - 1)
                {
                    for (intk = r; k < s.Length; k += diff) { result[index++] = s[k]; }}else
                {
                    int j = diff - 2 * r;
                    for (int k = r; k < s.Length; k += diff)
                    {
                        result[index++] = s[k];
                        if (k + j < s.Length)
                            result[index++] = s[k + j];
                    }
                }
                r++;
            }
            return new string(result); }} Link: HTTPS://leetcode-cn.com/problems/zigzag-conversion/solution/zxing-bian-huan-cjie-fa-80ms-shi-jian-10-ebr2/
Copy the code

Result the execution result is successful. The execution time is 92ms, and the memory consumption is 26.6MB

🌻Java method: Sort by row

By iterating over the string from left to right, we can easily determine which line the character is in the zigzagging pattern.

Algorithm We can use \text{min}(\text{numRows}, \text{len}(s))min(numRows,len(s))) lists to represent the non-empty lines in the z-shape pattern. Iterate ss from left to right, adding each character to the appropriate line. You can use the current row and current direction variables to track the appropriate row. The current direction changes only when we move up to the top row or down to the bottom row.

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

        if (numRows == 1) return s;

        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++)
            rows.add(new StringBuilder());

        int curRow = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows.get(curRow).append(c);
            if (curRow == 0 || curRow == numRows - 1) goingDown = ! goingDown; curRow += goingDown ?1 : -1;
        }

        StringBuilder ret = new StringBuilder();
        for (StringBuilder row : rows) ret.append(row);
        returnret.toString(); }} Link: HTTPS://leetcode-cn.com/problems/zigzag-conversion/solution/z-zi-xing-bian-huan-by-leetcode/
Copy the code

Result the execution result is successful. The execution time is 6ms, and the memory consumption is 38.8MB

Complexity analysis

Time complexity: O(n) Space complexity: O(n)

💬 summary

  • Today is the sixth day of buckle algorithm clocking! Today’s problem is a little difficult, with the help of force buckle god problem solution looked along while!
  • This paper uses C# and Java programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!