Leetcode 50 day question brushing plan (day 5 - longest palindrome substring 10.50-13:00)

Tips ： When the article is finished , Directories can be generated automatically , How to generate it, please refer to the help document on the right

---

Preface

Refueling pinch ~

One 、 subject

Z Font conversion

Will a given string s According to the given number of rows numRows , From top to bottom 、 Left to right Z Font arrangement .

For example, the input string is “PAYPALISHIRING” The number of rows is 3 when , Arranged as follows ：

P   A   H   N
A P L S I I G
Y   I   R

after , Your output needs to be read line by line from left to right , Generate a new string , such as ：“PAHNAPLSIIGYIR”.

Please implement this function to transform a string into a specified number of lines ：

string convert(string s, int numRows);

Example

Example 1：

Input ：s = “PAYPALISHIRING”, numRows = 3
Output ：“PAHNAPLSIIGYIR”
Example 2：
Input ：s = “PAYPALISHIRING”, numRows = 4
Output ：“PINALSIGYAHRPI”
explain ：
P I N
A L S I G
Y A H R
P I
Example 3：

Input ：s = “A”, numRows = 1
Output ：“A”

Tips

1 <= s.length <= 1000
s By the English letters （ Lowercase and upper case ）、‘,’ and ‘.’ form
1 <= numRows <= 1000

Two 、 Ideas

1. The garbage

Rats can do nothing but simulate with two-dimensional arrays , The simulation is also full of loopholes , Venerable lay 了
Here are some bug
①“ One has “ Immutability ” The object of , Is an object that cannot be changed after its creation . for example , You cannot change a string by assigning a value to a position in the string .” The return value of the function connected as a string is the new string , Instead of changing the original string ： s_join=s_join.join(re_list[i]) or "".join(res)
②python If the length of the string slice is not enough, cut it to the end , No mistake.
③ First, pay attention to the size of the original list ; Second, pay attention to the starting and ending conditions , Otherwise beyond index Error of

2. bosses

See one-dimensional array simulation I'm just stupid My mother asked me why I knelt and watched the computer whine QAQ
In fact, it is in the figure , The spacing between each line of characters is not important , There is no need to maintain the structure between columns , Just divide the characters into each line

https://leetcode.cn/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/

class Solution:
    def convert(self, s: str, numRows: int) -> str:
    	# If there is only one line z, Directly output the original string 
        if numRows < 2: return s
        # A few lines z Just create a few strings , The first i A string represents the i That's ok , Strings are stored in a one-dimensional list 
        res = ["" for _ in range(numRows)]
        #i On behalf of the line , That is the first. i A string ,flag Indicates direction ,-1 Means up ,1 It means down 
        i, flag = 0, -1
        # Traverse s The characters in 
        for c in s:
        	# Save one character in the current line each time 
            res[i] += c
            # When i=0（ First line ） or i=numRows - 1（ Biko ） when ,flag reverse 
            if i == 0 or i == numRows - 1: flag = -flag
            #i to update 
            i += flag
        # Return results 
        return "".join(res)

3、 ... and 、 Code

1.python（ Two dimensional array simulation ）

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # String length 
        n=len(s)
        if(numRows==1):
            return s
        # The length of each group of characters 
        step=2*numRows -2
        # List generation has numRows A two-dimensional list of rows , The list element is an empty string 
        re_list=[["" for j in range((n//step + 1)*(numRows - 1)+1)] for i in range(numRows)]
        # Which group 
        group=0

        # Traversing all strings , The step length is the length of the Group 
        for i in range(0,n,step):
            # This group of strings 
            temp=s[i:i+step]+'0'
            # The starting position of this group （ Column ）, Subscript from zero 
            start=group*(numRows-1)
            # Traverse each string in this group ,j Is the subscript of this group of strings 
            for j in range(step):
                # Judge whether it is over , Be sure to pay attention to the boundary conditions ！
                if(temp[j]=='0'):
                    break

                # Put it upright 
                if(j<numRows):
                    re_list[j][start]+=temp[j]
                # Put it sideways 
                else:
                    # And the absolute value of the horizontal and vertical coordinates of the last element 
                    abs_len = j-numRows+1
                    # Lock coordinates 
                    re_list[numRows-1-abs_len][start+abs_len]+=temp[j]

            # One group has been placed 
            group+=1
        # Output by line 
        re_str=""
        for i in range(numRows):
            s_join=""
            s_join=s_join.join(re_list[i])
            re_str+=s_join
        return re_str

2.c++（ One dimensional array simulation ）

class Solution {
    
public:
    string convert(string s, int numRows) {
    
        // There is only one line , Go straight back to 
        if(numRows==1){
    
            return s;
        }
        // Store results 
        string re[numRows];
        for(int i = 0;i<numRows;i++){
    
            re[i]="";
        }
        // String length 
        int n=s.length();
        int row=0;
        int flag=-1;

        // Traversal string 
        for(int i=0;i<n;i++){
    
            re[row]+=s[i];
            if(row==0 || row==numRows-1){
    
                flag=-flag;
            }
            row+=flag;
        }
        // result 
        string re_str;
        for(int i = 0;i<numRows;i++){
    
            re_str+=re[i];
        }
        return re_str;
    }    
};