Z字形变换

006_ZigZag_Conversion

1. 按列处理&

这是我顺着直觉写出来的代码,果然又长又臭,建议不要看

  class Solution:
      def convert(self, s: str, numRows: int) -> str:
        if numRows ==1:
          return s
        s =list(s)[::-1]
        counter = 0
        flag = True
        location = [None]*len(s)
        for i in range(len(s)):
          location[i] = counter
          if flag:
            counter+=1
          else:
            counter-=1
          if counter>=numRows:
            counter = numRows-2
            flag = False
          elif counter<0:
            counter=1
            flag =True

        area = [[] for i in range(numRows)]
        str=""
        for i in range(len(s)):
          area[location[i]].append(s.pop())
        for i in range(numRows):
          for j in range(len(area[i])):
            str+=area[i][j]
        return str

执行用时: 196 ms, 在ZigZag Conversion的Python3提交中击败了16.91% 的用户

内存消耗: 13.2 MB, 在ZigZag Conversion的Python3提交中击败了8.23% 的用户


2.优化方法1

我一贯的作风,把标准答案上的c++代码,重写了一边,其实就是对方法1的优化

  • 去除构建loction列表的中间环节,找到位置以后直接连接到对应行
  • 把存储行内容的列表改为字符串,就可减少最后的列表字符连接环节

我写完决定再也不在脑子不清醒的时候刷LeetCode了,前面是写的啥玩意儿,完全是弟弟行为.

  class Solution {
  public:
      string convert(string s, int numRows) {

          if (numRows == 1) return s;

          vector<string> rows(min(numRows, int(s.size())));
          int curRow = 0;
          bool goingDown = false;

          for (char c : s) {
              rows[curRow] += c;
              if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
              curRow += goingDown ? 1 : -1;
          }

          string ret;
          for (string row : rows) ret += row;
          return ret;
      }
  };
  class Solution:
      def convert(self, s: str, numRows: int) -> str:
        if numRows ==1: return s

        cur_row = 0
        going_down = -1
        rows = [""]*min(numRows,len(s))

        for i in s:
          rows[cur_row]+=i
          if cur_row == 0 or cur_row == numRows -1:
            going_down *= -1
          cur_row +=going_down

        result =""
        for i in rows:
          result+=i
        return result

执行用时: 128 ms, 在ZigZag Conversion的Python3提交中击败了60.64% 的用户

内存消耗: 13.1 MB, 在ZigZag Conversion的Python3提交中击败了8.23% 的用户


3. 按行处理

通过找结果中每行的字符在原字符串中的索引,可以找到通项公式,然后就能很方便的按行处理了

优势在于可以不用使用额外的列表来存储数据了

令n=numRows-1, m为(0,n)的一个整数,开始分析通项公式:

  • 第0行: $2 \times i \times n $
  • 第m行: $\left\lfloor\frac {i+1}2 \right\rfloor \times 2 \times n + (-1)^{i+1} \times m$
  • 第n行: $2 \times i \times n + n$

(ps: 可能会无法加载上面的公式,试了stackoverflow上所有方法,浏览器还是加载不了MathJax.js,望大神赐教)

最多显示成这样:(连在一起的地方就是差个加号….)

  • 第0行:
  • 第m行:
  • 第n行:
- 第0行: <img src="https://www.zhihu.com/equation?tex=2 \times i \times n" />
- 第m行: <img src="https://www.zhihu.com/equation?tex=\left\lfloor\frac {i+1}2 \right\rfloor \times 2 \times n + (-1)^{i+1} \times m" />
- 第n行: <img src="https://www.zhihu.com/equation?tex=2 \times i \times n + n" />

这可真是个小机灵鬼想出来的办法

代码结果仍然不理想,虽然不用使用额外的列表,但在生成结果字符串时,还是占用了比较大的空间

class Solution:
    def convert(self, s: str, numRows: int) -> str:
      if numRows ==1 or numRows >len(s): return s

      result = ""
      i = 0
      # row0
      n = numRows-1
      while len(s) > 2*i*n:
        result+=s[2*i*n]
        i+=1
      # rowM
      for m in range(1,n):
        i = 0
        while len(s) > (i+1)//2 * 2*n+((-1) ** i)*m:
          result+=s[(i+1)//2 * 2*n+((-1) ** i )*m]
          i+=1
      # rowN
      i = 0
      while len(s) > (2*i+1)*n:
        result+=s[(2*i+1)*n]
        i+=1
      return result

执行用时: 172 ms, 在ZigZag Conversion的Python3提交中击败了24.85% 的用户

内存消耗: 13.2 MB, 在ZigZag Conversion的Python3提交中击败了8.23% 的用户

本文总字数: 2515