Jamzen的技术博客
0%

LeetCode.Z字形变换

发表于 分类于 Valine：

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为3时，排列如下：
L   C     I     R
 E T O E S  I  I  G
  E     D    H    N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。

  • 示例 1:
    输入: s = “LEETCODEISHIRING”, numRows = 3
    输出: “LCIRETOESIIGEDHN”

  • 示例 2:
    输入: s = “LEETCODEISHIRING”, numRows = 4
    输出: “LDREOEIIECIHNTSG”

解法一：找规律O(n)解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
object ZStringTransform {
     def main(args: Array[String]): Unit = {
          println(solution1("A", 2))
     }

     /**
      * O(n)
      */
     def solution1(str: String, line: Int): String = {
          if (line == 1) {
               return str
          }
          val map = mutable.Map[Int, String]()

          for (i <- 0 until line) {
               map += (i -> "")
          }

          val max = 2 * (line - 1)

          for (i <- 0 until line) {
               var start = i
               var begin = if (max - i * 2 == 0) i * 2 else max - i * 2
               while (start < str.length) {
                    map += (i -> (map.get(i).get + str.charAt(start)))
                    start = start + begin
                    begin = if (max - begin == 0) max else max - begin
               }
          }

          val arr = new Array[String](line)
          for (i <- 0 until line) {
               arr(i) = map.get(i).get
          }
          arr.mkString("")
     }

}

解法二：flag标识上下移动，O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * O(n)
 */
def solution2(str: String, line: Int): String = {
     if (line <= 1) {
          return str
     }

     val map = mutable.Map[Int, String]()
     for (i <- 0 until line) {
          map += (i -> "")
     }

     var index = 0
     var flag = true
     for (i <- 0 until str.size) {
          map += (index -> (map.get(index).get + str.charAt(i)))
          if (flag) {
               index += 1
          } else {
               index -= 1
          }

          if (index == line) {
               flag = !flag
               index = line - 2
          }

          if (index == -1) {
               flag = !flag
               index = index + 2
          }
     }
     val arr = new Array[String](line)
     for (i <- 0 until line) {
          arr(i) = map.get(i).get
     }
     arr.mkString("")
}