Simulation questions

Topic describes

Arrange a given string s in a z-shape from top to bottom and left to right, numRows, according to the given number of rows.

For example, if the input string is “PAYPALISHIRING” with 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:

Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"Copy the code

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: PINALSIGYAHRPICopy the code

Example 3:

Input: s = "A", numRows = 1 output: "A"Copy the code

Tip:

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

Source: LeetCode

Train of thought

The key idea in this simulation is coordinate transformation, which involves mapping the coordinates of two strings.

Assuming that the input string is S and the output string is P, there are two mapping ideas. One is to traverse S from the first subscript to find the subscript corresponding to P. The second idea is to iterate over p from the first index, looking for the corresponding index in the string s. The second way is a little bit more computable.

If you look at the “forward” pattern of string S, you can see that the characters in the string are either moving down or diagonally up. For the string P, it is responsible for printing each line of Z character by character.

The calculation rules are as follows:

  1. forzAny ordinances of phiiThe start character of the line, which corresponds to the stringsThe firstiA character.
  2. forzType, as long as thezMove to the right once in the font, either by moving down and then slanting up, or by moving up and then slanting down.
  3. The first linezFor type characters, always moving one bit to the right is done by moving down and then slanting up.
  4. For at the end of the linezFor type characters, always moving one bit to the right is done by moving down and then slanting up.
  5. For others that are neither the first nor the last rowzFor type characters, starting from the first column, the movement rule of moving to the right is first down and then slanting up, and the next step is first slanting up and then down alternately.

Using the rules described above, you can write code that simulates z-motion logic. By scanning the z character line by line, the corresponding character can be written to p.

Swift code:

class Solution {
    func convert(_ s: String._ numRows: Int) -> String {
        guard numRows > 1 else { return s }
        let cs = s.cString(using: .ascii)!
        let count = cs.count
        var ans: [CChar] = Array(repeating: 0, count: count)

        var i1 = 0
        var i0 = 0
        var row = 0
        // mark whether the next move is down or up
        var down = true 
        while i1 < count - 1 {
            ans[i1] = cs[i0]
            i1 + = 1
            // Calculate the corresponding offset index for different movement modes
            i0 + = down ? (numRows-row-1)*2 : row*2
            if i0 > = count - 1 {
                row + = 1
                i0 = row
                down = row = = numRows - 1 ? false : true
            } else if row ! = 0 && row ! = numRows - 1 {
                down.toggle()
            }
        }

        return String(cString: ans)
    }
}
Copy the code