题目:

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

代码:

看了半天,都没怎看懂题目。查了一下,原来:

Zigzag:即循环对角线结构(

0       8       16      
1     7 9     15 17      
2   6   10   14   18      
3 5     11 13     19      
4       12       20      

这样子的话,就不算麻烦了,只要正确的字符串操作,把每个元素加在正确的位置就好。

于是,共有numRows行,所以定义一个保护numRows元素的数组,用来保存每一行的字符串。

观察规律,第一列从0写到numRows-1,之后从后往前,及numRows-2到0开始逐渐添加。输出并不需要考虑宽度,所以对字符串来说,之后往后加就好

//凑了半天,总算凑出来了

def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        i = 0
        j = 0
        gap = numRows-2
        temp= ['' for x in range(numRows)]
        while i<len(s):
            while(j<numRows):
                if(i>=len(s)):break
                temp[j] += str(s[i])
                j += 1
                i += 1
            j=gap
            while(j>0):
                if(i>=len(s)):break
                temp[j] += str(s[i])
                j -= 1
                i += 1
        result = ''
        for y in temp:result += y

return result

//网上查的,好像更直观   
    def convert2(self, s, nRows):
        if nRows==1: return s
        tmp=['' for i in range(nRows)]
        index=-1; step=1
        for i in range(len(s)):
            index+=step
            if index==nRows:
                index-=2; step=-1
            elif index==-1:
                index=1; step=1
            tmp[index]+=str(s[i])
        return ''.join(tmp)

测试了多次,两个速度差不多,必定时间复杂度和空间复杂度都一样:

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAOkAAABLCAIAAAAagTdRAAAGDElEQVR4nO1c3dGjMAykrhREPVRDMynmu4cEkKWVLZnMHJrZfbpThPXjxXFgPy9/BFETy/9OgCAmQe4SVUHuElVB7hJVMeLue3stH7y292Hc1+XEuivXy6CcrwGMpxxQjnrZ5ag20JXlICUvECwzmLx7udOQ4wObf+OJmixsZ6Bw7RkjCjTMUxcaKhO2Lmbsc3dfm9n9/HNfr+j7+h3o84/L6QrXksHzNA4yooiDL4ejhQP9vbeXqPJIOJy81yUn+r4ur3XVtdkxbZMviNzitceNMBDyxHMULxN2HhpBk7vcFdmIe8iU01Zq+gKH7jbL3iN6qAh3w4EkrhaFk8dd8oJ4XAEVOU1W3tna40b4gakdz1GwTAFBTmBETe5x94yzr8vy2rY2Ne9borkpX9t+rPRt/70aRI7qThtxF33HxQJB73DynS7Z6Og7xc0TNfn4hjZ7mHDtQaMNhDydOUqVGUkLNnnMXUP99/Za5EDuutswrr9wYuv7os4WufxPJpcJ9IW89cPJO11Cca5VKrTuOk02qeZqz627JhDaFqo5SpTZK8duE1STR3uGpVmq111FVzHBuit/4A2+5dEG03H3e60HiQbSEx9PHnYJeMoF0i6U/j7SnVi4kxje4UnuxhYd8UmmzNM0vA9Rk4e/1cw3eO/njD9zgbbCKYIXdzo4+CpwAqH2xZPH+5xunqMFqddkHTNV+8y6Ox7Ty3K87oaIq/I4mjzzjEzeWUcE/fBJboLCnmC71l7rXS7CXGOEA5mVYip5Fd7xFCH7Yw6aDGdjUPuUcTAmnKNwmbDz4+kIPSMjiOeC3CWqgtwlqoLcJaqC3CWqgtwlqoLcJapiSgMZ94wbD6t6+28fM0pv9XJLP2m0gTwNpPwIqAuHyYfVktiTmMGEBjLumTIGlXhHNK2vk29Qe8rGNmehIwRyR5snHtO5PCgKJSYxoYEMe8aNX3S526yQihaCElAf5ilXvjbnBWu/9gm1ZM+TSGNSAxnxjBvNMCeAEs/T1zmyTDyu5qaROw5rb9bioNSz50mkMaGBjHrGje0wKIC8AGxiLvEGUAwOFt3v1UruOKh9Si3Z9STSyGsg455x4xdDJZ6jr/MVg1CmpHedbyR39PPUY8LLYUU9TyKNvAby/ET/33rGjR/ElXits/O7CRMXLMRwKJznPbVkx5NIY/IZGfj5cusZWVyJ18QDT8OQgtHYodC0dYN5/lItyUX3LvhugqgKcpeoCnKXqApyl6gKcpeoCnKXqApyl6gKngPplxlM3r3caYgjQtKeqMnoiXe49ozRebTezxO9eB+WeeO1AM+B/LutbEyqOoGAE45pm3xBvT2M1R43wkDIE89RvEzYeWgETeY5kC0mlI05VafHFVBRR9WpXi5nao8b4QemdjxHwTIFkGSq0WCZJvMcSKeAcPKdLtnonoAT5omabEWh2dqDRqA+BZ7OHKXKjKQFm8xzIAWmlI1Ol1AcLOD0S8dNNqnmas+tu0O9FJijRJm9cuw2QTWZ50AKm0owmHxU1SkXSLtQ+vtId2LhTmJ4hye5G1t0xCeZMk/T8D5ETeY5kIcTamks+QlV52hB6jVZx0zVPrPujsf0shyvuyHiqjyOJvMcSLAgTiWvwjueImR/zEGT4WwMap8yDsaEcxQuE3Z+PB2hZ2QE8VyQu0RVkLtEVZC7RFWQu0RVkLtEVZC7RFU8+hxIbMQKzMtbvfHSftB4M/mwsf9n+0QKTz4HMikOVKI79Vz8VDta493k32Eh34XO+28iiOefAwneMyNxoCE6lOd5xh8kfwzZ1ZT0SyVSePg5kNhoxYFAdAflecj4o+SDBXjaQiKN558DCdZdSaDvH22gnc254ZQ0s8YfJZ9YdHt2IoznnwNpBVZyv7use190Fxj4F8mH9VCyZVx7b+H550CmxIHuCN0fS3eTzxOX1P0BipwDKfa3SBzYJHEYoTzP0ezdST4h5OMjsl+C7yaIqiB3iaogd4mqIHeJqiB3iaogd4mqIHeJqiB3iaogd4mqIHeJqiB3iaogd4mqIHeJqiB3iaogd4mqIHeJqiB3iar4B2VahtoPv4pdAAAAAElFTkSuQmCC" alt="" />

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKQAAABDCAIAAACdljksAAAFOklEQVR4nO1bS5ajMAzkXByI83CR2XKZHIZZdAf0qZIFk0nntVSrPEeWZJdtsAtPfxplMO2NMmiyC6HJLoQmuxCa7EJosgtBk/1Y5+kL8/p4Fm7LdGDZjOlZIM2k7Vl+2oLqIrb6A6Yk3Z7F3ierjizFH0e5aNNRneSJfWYLUSCc0pVmWkiyt+Vw8Vjn75/botr+5evrx2nk8LSUJkdtXB16e6yzyOjZEPlbRzROWItI8tsyzcuCGiUiwjxZ9GQhDARTYl0HeslDkH2SIUeTqC4MDiuasR8qtn6GbIGTOJsHjMxbxMJFNIjSIE82XpOFrAHemOcghrfHSfbhYFumaV5X0aPfi4x1wkKKPjZTa0Q2W8qU9WOd53V7WmtT5TNokU8erUVn0/3DAuX5L2T7QCwl5jP8Y993T/bBjowku2w4sxmHtrfjjEFXPEvUqIlWC9IiFP1cgUhWaMa4PF8ws3eZLk3pQpISehmf1LK3bMatcYZCBg8Na84brJ3YPn2ssx7+NCXYImCp37nw4oKeHbaxryBbLN08JVAdzBAH84Lmlt/ovQiE5GPLjwLaYLmEoDaYB2iQEn6ghNH5pHFc55a66zMbvY/HMzvD9J7ZeskxJt4JFfi74FkbPAhVdRGHbHN0oHxKximxBP0IN0QoT+zzVmH4uoKrs14akN341WiyC6HJLoQmuxCa7EJosguhyS4Ee4KW2a5Ze7CDZdvCadnCQBmflyxBod6WhnvqCwAbehzoB8FmdqAs7Ts9PtFCXMrnWZj3mbXE1QfyWqwSEkAtdaTjvR2Y7ITciA4PqZpJfYrCvM+0Ja6eIButAsn+MOrw55M9mNZYZIzUTOZTd1LSZ94Sp8Q0Si8ywg83cH8gLXUg2r4fgOzxgCQiI1czE2pA3ueV6EFKz39dWkoEkpCaiioKtVQe6O1wZGceWZHIeDgxcuJIH8z7vBp9UMjXm9ECp2pQLTUI9G5YsrFGuS36oRWIjKAI+nSFeZ/XovNCr1E+S/2zYYBAS+WB3g4vcRKNjX7OCD4BcJa5zr/mM2M5KMQapdXHc4/deOv1AUzvfahSCk12ITTZhdBkF0KTXQhNdiE02YXQtzhBB6hbEcHuOe6QK4WBwOoOOfLNtOhbnMZH3+KUHOnEaMZ+qIT3slKyqmILGmknuEUsXESDOaEleV47lB90XZQSzyE84e1bnCZpsDbAhwXK81/I9oFYSsxn+Me+732L8/QfT1w0Y1yeL5jZu0yXpnQhSYm+xbmLASmA3wnixr6CbLF085RAdTBDHPoWJ8gTTxr0KdTVTzRG0ZMfdKF5M2J671uck+0ks3/As8oVQp+3CsPXFVyd9dKA7MavRpNdCE12ITTZhdBkF0KTXQhNdiHcvcWJduTx57hDSQ5XhwIrVPSyhXpbqo4HMy3PdwgJ9HO4d4tzoKk5peyaJKerSzaO2za+OlQzoSU8vcpe6yJg0T+B4hP3bnEKMIXATeS8JIePQ9nNQKdyODXTBKLnlyAQOKojrSDq8OeTfWFoA+Vh8md+efkWVCcCq6oeqpkmENUoXaDsdCfRB6Lt+3HrFucBpnskVYdx9UBgBWsnUTNpIKEfoED2zFlqKqpoED0tVPxv3LrFeRjSBsQfpaSrc4HVVudqZhToaCwMlF/gIi1VB/pR3LvFORqqow+YstWJwIqqB5/H0EB6EvtAo48BRtFBoB/FrVucWFODW6e8JId3XkBgHeue+mXJWkKNEiq5Vx678dbrA5je+1ClFJrsQmiyC6HJLoQmuxCa7EJosgvhLyYpRHTceeTqAAAAAElFTkSuQmCC" alt="" />

最新文章

  1. CRUD操作
  2. spring+redis
  3. mysql 报错max_allowed_packet处理办法
  4. logstash 添加nginx日志
  5. Javascript图表插件HighCharts用法案例
  6. [译]学习IPython进行交互式计算和数据可视化(三)
  7. 富有表现力的javascript
  8. Spring框架学习之第9节
  9. URAL 2048 History 蔡勒公式
  10. 荣誉,还是苦逼?| 也议全栈工程师和DevOps
  11. Gulp实战(二)
  12. xcode5.1上真机调试报告No architectures to compile for...的解决办法
  13. 在线程中建立Form遇到的问题
  14. Spring的 classpath 通配符加载配置文件
  15. 201521123084 《Java程序设计》第12周学习总结
  16. 吐槽CSDN--想赚钱想疯了--强行升级皮肤--增加广告位
  17. css3实现水平垂直居中
  18. ChIP-seq基本流程及工具
  19. [PHP] 算法-复制复杂链表的PHP实现
  20. 【机器学习基础】SVM实现分类识别及参数调优(二)

热门文章

  1. HDOJ 4747 Mex
  2. 【C语言入门教程】2.1 数据类型(5种基本数据类型),聚合类型与修饰符
  3. Ubuntu 14 编译安装 XDebug - 2.3.3 For PHP - 5.4.45
  4. mysql 按距离今日时间最近排序
  5. 为 Github 创造 Integration
  6. 14个Xcode中常用的快捷键操作(转)
  7. [codevs1155][KOJ0558][COJ0178][NOIP2006]金明的预算方案
  8. 【笔记】CSS高级选择器:nth-child()
  9. jtable插件api
  10. InputStream,String相互转化