Leetcode medium question sharing (5)

Z Font conversion

subject ：

 

Encountered this kind of problem has horizontal and vertical , I first thought of the solution of two-dimensional array ：

be supposed to Z The font , In fact, it's more like a repeating cycle on one , So we are thinking about how many characters are needed for each cycle ：

hypothesis rowNum=3, So in the middle 1 individual , All in all 4 individual

hypothesis rowNum=4, So in the middle 2 individual , All in all 6 individual

hypothesis rowNum=5, So in the middle 3 individual , All in all 8 individual

So obviously , All you need is 2*rowNum-2 individual .

 

We can see this up and down as a cycle , We consider the space occupation of a loop in a two-dimensional array

Let's assume that the length of this array is length：

int length = s.length();

numRows A row ：

int numOfRec = 2*numRows-2;

The occupation of vertical columns can be considered from numRows Descending to 0 One of the forLoop, In general, we mainly consider the number of cycles in the vertical column ：

int numCols = (length+numOfRec-1)/numOfRec*(numRows-1);

Then all we need to do is traverse and add a two-dimensional array ：

 // Fill in below first numRows Characters , Then fill in from the bottom left to the top right 
    public static String convert(String s, int numRows) {

        int length = s.length();
        if (numRows==1 || numRows>=length){
            return s;
        }

        //  The number of characters required for a cycle 
        int numOfRec = 2*numRows-2;

        // Number of columns 
        int numCols = (length+numOfRec-1)/numOfRec*(numRows-1);

        // Create a 2D array 
        char[][] cars = new char[numRows][numCols];

        // Traverse and insert a two-dimensional array 
        for (int i = 0, x = 0, y = 0; i < length ; ++i) {
            cars[x][y]=s.charAt(i);
            if (i%numOfRec<numRows-1){
                ++x;
            }else{
                --x;
                ++y;
            }
        }


        // Traverse the output 
        StringBuilder res = new StringBuilder();
        for (int j = 0; j < numRows; j++) {
            for (int i = 0; i < numCols; i++) {
                char c = cars[j][i];
                if (c!='\u0000'){
                    res.append(c);
                }
            }
        }
        return res.toString();
    }

        This problem is intuitively a two-dimensional array + The use of recycling , There is some violence in solving problems . The difficulty that needs to be considered is the duality of two-dimensional arrays for The loop will cause a timeout , To this extent, it should be simplified .

  Although the result passed, I was not very satisfied , Let's optimize it later