蜗牛慢慢爬 LeetCode 6. ZigZag Conversion [Difficulty: Medium]

题目

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);

翻译

此题坑爹在于关于zigzag的形式没有说清楚 然后在leetcode上负分较多
其实只要理解了zigzag的形式就好了

/*n=numRows Δ=2n-2 1 2n-1 4n-3 Δ= 2 2n-2 2n 4n-4 4n-2 Δ= 3 2n-3 2n+1 4n-5 . Δ= . . . . . Δ= . n+2 . 3n . Δ= n-1 n+1 3n-3 3n-1 5n-5 Δ=2n-2 n 3n-2 5n-4 */

Hints

Related Topics: String
一开始我的想法是用二维数组在遍历的时候把字符存到对应的位置 之后再join到一个字符串里面 这样挺直观的 但是python的话慢了一点
事实上我的代码有点硬推出每个字符的位置填上去的意思(囧) discuss中类似状态机改变index变化步长的方法显然更好

代码

Java

public String convert(String s, int nRows) {char[] c = s.toCharArray();int len = c.length;StringBuffer[] ss = new StringBuffer[nRows];for (int i = 0; i < ss.length; i++) ss[i] = new StringBuffer();int i = 0;while (i < len) {for (int idx = 0; idx < nRows && i < len; idx++)ss[idx].append(c[i++]);for (int idx = nRows-2; idx >= 1 && i < len; idx--)ss[idx].append(c[i++]);}for (int idx = 1; idx < ss.length; idx++)ss[0].append(ss[idx]);return ss[0].toString(); }

Python

class Solution(object):def convert(self, s, numRows):""":type s: str:type numRows: int:rtype: str"""l = len(s)if l<=1 or numRows<=1: return sk = numRows - 2n = l/(numRows+k)+1n = n*(k+1)zigzag = [['']*n for i in range(numRows)]for i in range(l):c = (2*numRows-2)*(i/(2*numRows-2))if (i-c)/numRows==0:zigzag[((i-c)%numRows)][(i/(2*numRows-2))*(k+1)] = s[i]else:zigzag[numRows-2-(i-c)%numRows][(i/(2*numRows-2))*(k+1)+((i-c)%numRows+1)] = s[i]ss =''for i in range(numRows):ss += ''.join(zigzag[i])return ss#better solution class Solution(object):def convert(self, s, numRows):if numRows==1or numRows>=len(s):return sL = ['']*numRowsindex, step = 0, 1for i in s:L[index] += iif index==0:step = 1elif index==numRows-1:step = -1index += stepreturn ''.join(L)

转载于:https://www.cnblogs.com/cookielbsc/p/7476102.html

总结

以上是生活随笔为你收集整理的蜗牛慢慢爬 LeetCode 6. ZigZag Conversion [Difficulty: Medium]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。