Algorithm interview Replay: Z-transform (bytes)

Today, I would like to share with you a problem that many people have had a headache – Z shape change.

01. Examples of topics

Er… Do not know whether I am blind, it is N yao (bar jing do not disturb, just say)

L   C   I   R
E T O E S I I G
E   D   H   N
Copy the code

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

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 ="LEETCODEISHIRING"NumRows = 3 output:"LCIRETOESIIGEDHN"
Copy the code

Example 2:

Enter: s ="LEETCODEISHIRING"NumRows = 4 output:"LDREOEIIECIHNTSG"L D R E O E I I E C I H N T S GCopy the code

02. Topic analysis

This is a “primary school topic” that I highly praise, because it does not have any complicated thinking logic, only need step by step, can be solved smoothly. What’s hard is that it’s extremely error-prone.

Since the end goal was to change the order of the strings, and there was no restriction on using extra space, we decided not to duplicate the wheel and tried to manipulate the string with some structure.

If we use the data from Example 2 for analysis, enter the string S as “LEETCODEISHIRING” and numRows as 4. The graph will look something like this:

The point is, our goal is to print by row, so there has to be something to store each row, right? Since you only need to store each row of data, you can just use an array. (Of course, there’s nothing wrong with having a map to save it. It’s just a little boring.)

So the question is, how big is the array set? In other words, numRows is the size of our array. The graph looks something like this:

Now that I have the container, and the original string is listed, what does it look like? Put the original string in the container. How to put? Just go back and forth based on the numRows size (that is, from 0 to n-1, and then n-1 to 0). Please see the following figure for details:

This is a really long picture, but if you look at it you can see that every 2n minus 2 is a period. Here, there should be no one will question this is a primary school topic… After placing all the strings, it looks something like this:

Finally, let’s make the array line up and start eating the fruit:

If you can’t see clearly, try this:

According to the analysis, we get the code (haven’t turned the go brand for a long time) :

//go
func convert(s string, numRows int) string {
    if numRows == 1{
		return s
	}
	var b = []rune(s)
	var res = make([]string, numRows)
	var length = len(b)
	var period = numRows * 2 - 2
	for i := 0; i < length; i ++ {var mod = i % period
		if mod < numRows {
			res[mod] += string(b[i])
		} else {
			res[period - mod] += string(b[i])
		}
	}
	return strings.Join(res, "")}Copy the code

Execution Result:

The above code highlights two points:

First: using a rune, which is actually a go usage for Unicode or UTF-8 characters, is nothing special.

Second: lines 12-15 mean that, during the cycle, numrows-1 goes straight ahead and the rest backwards. (That’s the long picture above)

In order to take care of Java friends, give a Java version:

//java
class Solution {
    public static String convert(String s, int numRows) {
        if (numRows == 1) return s;
        String[] arr = new String[numRows];
        Arrays.fill(arr, "");
        char[] chars = s.toCharArray();
        int len = chars.length;
        int period = numRows * 2 - 2;
        for (int i = 0; i < len; i++) {
            int mod = i % period;
            if (mod < numRows) {
                arr[mod] += chars[i];
            } else {
                arr[period - mod] += String.valueOf(chars[i]);
            }
        }
        StringBuilder res = new StringBuilder();
        for (String ch : arr) {
            res.append(ch);
        }
        returnres.toString(); }}Copy the code

As in the Go example, the key to the code is the procedure for calculating the trajectory (10-17). Here is another way to calculate the trajectory:

//java
class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        String[] arr = new String[numRows];
        Arrays.fill(arr, "");
        int i = 0, flag = -1;
        for (char c : s.toCharArray()) {
            arr[i] += c;
            if (i == 0 || i == numRows - 1) flag = -flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for (String ch : arr) {
            res.append(ch);
        }
        returnres.toString(); }}Copy the code

Reverse the track by using a flag bit. (The essence is the same)

03,

The meaning of this topic is to investigate the ability of coding, and the thinking process itself is not complicated. As soon as some students see this kind of problem, they want to calculate by two-dimensional array, but they have fallen into the trap of the problem (do not believe you try, two-dimensional array error rate must be far better than one-dimensional array). Of course, this problem can also be implemented without the help of extra space, the core logic is exactly the same, I suggest you go down to practice yourself.

So, did you learn today’s quiz question? Leave your thoughts in the comments!

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download