{"id":3923,"date":"2018-09-12T08:54:49","date_gmt":"2018-09-12T15:54:49","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3923"},"modified":"2018-09-12T18:57:49","modified_gmt":"2018-09-13T01:57:49","slug":"leetcode-6-zigzag-conversion","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-6-zigzag-conversion\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 6. ZigZag Conversion"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

The string\u00a0\"PAYPALISHIRING\"<\/code>\u00a0is 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>\n

P   A   H   N\r\nA P L S I I G\r\nY   I   R\r\n<\/pre>\n
And then read line by line:\u00a0\"PAHNAPLSIIGYIR\"<\/code><\/p>\n
Write the code that will take a string and make this conversion given a number of rows:<\/p>\n
string convert(string s, int numRows);<\/pre>\n
Example 1:<\/strong>
\n<preclass=”crayon:false”>Input:<\/strong> s = “PAYPALISHIRING”, numRows = 3 Output:<\/strong> “PAHNAPLSIIGYIR”<\/p>\n
Example 2:<\/strong><\/p>\n
Input:<\/strong> s = \"PAYPALISHIRING\", numRows =\u00a04\r\nOutput:<\/strong>\u00a0\"PINALSIGYAHRPI\"\r\nExplanation:<\/strong>\r\n\r\nP     I    N\r\nA   L S  I G\r\nY A   H R\r\nP     I<\/pre>\n
Solution: Simulation<\/strong><\/h1>\n
Store the zigzag results for each row and then output row by row.<\/p>\n
Time complexity: O(n)<\/p>\n
Space complexity: O(n)<\/p>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  string convert(string s, int nRows) {\r\n    if (nRows == 1) return s;\r\n\r\n    vector<string> ss(nRows);\r\n    int l = s.length();\r\n    int x = 0, y = 0, i = 0;\r\n    bool down = true;\r\n    while (i < l) {\r\n      ss[y] += s[i];\r\n      if (down) {\r\n        ++y;\r\n        if (y == nRows) {\r\n            down = false;\r\n            y -=2;\r\n        }\r\n      } else {\r\n        --y;\r\n        if (y < 0) {\r\n            down = true;\r\n            y = 1;\r\n        }\r\n      }\r\n      i++;\r\n    }\r\n\r\n    string ans;\r\n    for(const string& r : ss)\r\n      ans += r;\r\n    return ans;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
Problem The string\u00a0“PAYPALISHIRING”\u00a0is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,47],"tags":[93,177,401,4,400],"class_list":["post-3923","post","type-post","status-publish","format-standard","hentry","category-simulation","category-string","tag-conversion","tag-medium","tag-row","tag-string","tag-zigzag","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3923","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3923"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3923\/revisions"}],"predecessor-version":[{"id":3939,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3923\/revisions\/3939"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3923"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3923"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3923"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}