Leetcode_6 - ZigZag Conversion 解题报告

Link:https://leetcode.com/problems/zigzag-conversion/

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

这题的意思是做一个“之”字型的字符串转换,给定固定的行数,按照这个行数进行“之”字型排列,然后按每个横行顺序读取的方式返回一个结果字符串。

We observation "PAYPALISHIRING" the index bellow。

image

P(0) I(6) N(12)

A(1) L(5) S(7) I(11) G(13)

Y(2) A(4) H(8) R(10)

P(3) I(9)

1)Top row index is 0,6,12 and the step is 6,the bottom row index is 3,9 and the step is 6.The relation to "numRows=4" is (numRows-1)*2
2)The second row index is 1,5,7,11,13 and the step is 4,2,4,2
3)The third row index is 2,4,8,10 and the step is 2,4,2
4)The step row start is 6,4,2,6
5)So we found the law,the edge step is fixed 6,the inner adjacency step sum is 6.

Following is the code:

//use this  method to speed the  input stringauto speed=[]()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);    return nullptr;
}();
class Solution {public:  
    string convert(string s, int numRows) {  
        int m=s.size();        if(numRows==1 || numRows>=m){  
             return s;
        }        
        string ret="";        
        int base_step=(numRows-1)*2;        
        for(int i = 0; i < numRows; i++){            
            int step = base_step;            
            if(i != 0 && i != numRows - 1){  
                //Inner rows step start
                step = i * 2;
            }            
            int offset=i;            
            while(offset < m){
                ret+=s[offset];                
                if(step!=base_step){ 
                    //Inner rows need to change the step
                    step = base_step - step;
                }
                offset += step;
            }    
        }        
        return ret;
    }
};

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Powered By Z-BlogPHP 1.5.2 Zero

Copyright liuyang1.com. 转载文章,请注明出处。谢谢!