力扣00006.N字形变换

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 10 分钟
N字形变换、字符串、中等

题目描述

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = “PAYPALISHIRING”, numRows = 3
输出：”PAHNAPLSIIGYIR”

示例 2：

输入：s = “PAYPALISHIRING”, numRows = 4
输出：”PINALSIGYAHRPI”
解释：
P          I          N
A      L S      I G
Y A      H R
P          I

示例 3：

输入：s = “A”, numRows = 1
输出：”A”

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
  • 1 <= numRows <= 1000

解决方法

C++

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
class Solution {
public:
    std::string convert(std::string s, int numRows) {
        if (numRows <= 1 || s.length() <= numRows) {
            return s;
        }
        std::vector<std::string> rows(numRows);
        int row = 0;
        int step = 1;
        for (char c : s) {
            rows[row].push_back(c);
            if (row == 0) {
                step = 1; // 到达第一行，改变方向向下
            } else if (row == numRows - 1) {
                step = -1; // 到达最后一行，改变方向向上
            }
            row += step;
        }
        std::string result;
        for (const std::string& rowStr : rows) {
            result += rowStr;
        }
        return result;
    }
};

结果

执行用时 : 8 ms, 击败 91.30% 使用 C++ 的用户

内存消耗 : 10.46 MB, 击败 58.69% 使用 C++ 的用户

Java

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
public class Solution {
    public String convert(String s, int numRows) {
        if (numRows <= 1 || s.length() <= numRows) {
            return s;
        }
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }
        int row = 0;
        int step = 1;
        for (char c : s.toCharArray()) {
            rows[row].append(c);
            if (row == 0) {
                step = 1; // 到达第一行，改变方向向下
            } else if (row == numRows - 1) {
                step = -1; // 到达最后一行，改变方向向上
            }
            row += step;
        }
        StringBuilder result = new StringBuilder();
        for (StringBuilder rowStr : rows) {
            result.append(rowStr);
        }
        return result.toString();
    }
}

结果

执行用时 : 4 ms, 击败 86.05% 使用 Java 的用户

内存消耗 : 43.73 MB, 击败 20.70% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def convert(self, s, numRows):
        if numRows <= 1 or len(s) <= numRows:
            return s
        rows = [''] * numRows
        row = 0
        step = 1
        for char in s:
            rows[row] += char
            if row == 0:
                step = 1
            elif row == numRows - 1:
                step = -1
            row += step
        return ''.join(rows)

结果

执行用时 : 76 ms, 击败 29.33% 使用 Python 的用户

内存消耗 : 13.10 MB, 击败 75.91% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows <= 1 or len(s) <= numRows:
            return s
        rows = [''] * numRows
        row = 0
        step = 1
        for char in s:
            rows[row] += char
            if row == 0:
                step = 1
            elif row == numRows - 1:
                step = -1
            row += step
        return ''.join(rows)

结果

执行用时 : 48 ms, 击败 97.61% 使用 Python3 的用户

内存消耗 : 17.09 MB, 击败 14.32% 使用 Python3 的用户

C

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
char* convert(char* s, int numRows) {
    int n = strlen(s), r = numRows;
    if (r == 1 || r >= n) {
        return s;
    }
    int t = r * 2 - 2;
    int c = (n + t - 1) / t * (r - 1);
    char** mat = (char**)malloc(sizeof(char*) * r);
    for (int i = 0; i < r; i++) {
        mat[i] = (char*)malloc(sizeof(char) * c);
        memset(mat[i], 0, sizeof(char) * c);
    }
    for (int i = 0, x = 0, y = 0; i < n; ++i) {
        mat[x][y] = s[i];
        if (i % t < r - 1) {
            ++x;
        } else {
            --x;
            ++y;
        }
    }
    char* result = (char*)malloc(sizeof(char) * (n + 1));
    int pos = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (mat[i][j]) {
                result[pos++] = mat[i][j];
            }
        }
        free(mat[i]);
    }
    free(mat);
    result[n] = '\0';
    strcpy(s, result);
    free(result);
    return s;
}

结果

执行用时 : 44 ms, 击败 24.86% 使用 C 的用户

内存消耗 : 30.42 MB, 击败 13.58% 使用 C 的用户

C#

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
public class Solution {
    public string Convert(string s, int numRows) {
        if (numRows <= 1 || s.Length <= numRows) {
            return s;
        }
        int n = s.Length;
        int t = numRows * 2 - 2;
        int c = (n + t - 1) / t * (numRows - 1);
        char[,] mat = new char[numRows, c];
        int x = 0, y = 0;
        for (int i = 0; i < n; ++i) {
            mat[x, y] = s[i];
            if (i % t < numRows - 1) {
                ++x;
            } else {
                --x;
                ++y;
            }
        }
        string result = "";
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < c; j++) {
                if (mat[i, j] != '\0') {
                    result += mat[i, j];
                }
            }
        }
        return result;
    }
}

结果

执行用时 : 88 ms, 击败 49.10% 使用 C# 的用户

内存消耗 : 58.23 MB, 击败 42.19% 使用 C# 的用户

JavaScript

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
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if (numRows <= 1 || s.length <= numRows) {
        return s;
    }
    let n = s.length;
    let t = numRows * 2 - 2;
    let c = Math.ceil(n / t) * (numRows - 1);
    let mat = new Array(numRows).fill().map(() => new Array(c).fill(''));
    let x = 0, y = 0;
    for (let i = 0; i < n; ++i) {
        mat[x][y] = s[i];
        if (i % t < numRows - 1) {
            ++x;
        } else {
            --x;
            ++y;
        }
    }
    let result = '';
    for (let i = 0; i < numRows; i++) {
        for (let j = 0; j < c; j++) {
            if (mat[i][j] !== '') {
                result += mat[i][j];
            }
        }
    }
    return result;
};

结果

执行用时 : 156 ms, 击败 21.61% 使用 JavaScript 的用户

内存消耗 : 64.30 MB, 击败 8.54% 使用 JavaScript 的用户

TypeScript

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
function convert(s: string, numRows: number): string {
    if (numRows <= 1 || s.length <= numRows) {
        return s;
    }
    const n: number = s.length;
    const t: number = numRows * 2 - 2;
    const c: number = Math.ceil(n / t) * (numRows - 1);
    const mat: string[][] = Array.from({ length: numRows }, () => Array(c).fill(''));
    let x: number = 0,
        y: number = 0;
    for (let i = 0; i < n; ++i) {
        mat[x][y] = s[i];
        if (i % t < numRows - 1) {
            ++x;
        } else {
            --x;
            ++y;
        }
    }
    let result: string = '';
    for (let i = 0; i < numRows; i++) {
        for (let j = 0; j < c; j++) {
            if (mat[i][j] !== '') {
                result += mat[i][j];
            }
        }
    }
    return result;
}

结果

执行用时 : 156 ms, 击败 11.05% 使用 TypeScript 的用户

内存消耗 : 63.39 MB, 击败 5.23% 使用 TypeScript 的用户

PHP

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
class Solution {
    /**
     * @param String $s
     * @param Integer $numRows
     * @return String
     */
    function convert($s, $numRows) {
        if ($numRows <= 1 || strlen($s) <= $numRows) {
            return $s;
        }
        $n = strlen($s);
        $t = $numRows * 2 - 2;
        $c = ceil($n / $t) * ($numRows - 1);
        $mat = array_fill(0, $numRows, array_fill(0, $c, ''));
        $x = 0;
        $y = 0;
        for ($i = 0; $i < $n; ++$i) {
            $mat[$x][$y] = $s[$i];
            if ($i % $t < $numRows - 1) {
                ++$x;
            } else {
                --$x;
                ++$y;
            }
        }
        $result = '';
        for ($i = 0; $i < $numRows; $i++) {
            for ($j = 0; $j < $c; $j++) {
                if ($mat[$i][$j] !== '') {
                    $result .= $mat[$i][$j];
                }
            }
        }
        return $result;
    }
}

结果

执行用时 : 276 ms, 击败 6.98% 使用 PHP 的用户

内存消耗 : 35.56 MB, 击败 6.98% 使用 PHP 的用户

Swift

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
class Solution {
    func convert(_ s: String, _ numRows: Int) -> String {
        if numRows <= 1 || s.count <= numRows {
            return s
        }
        let n = s.count
        let t = numRows * 2 - 2
        let c = Int(ceil(Double(n) / Double(t)) * Double(numRows - 1))
        var mat = Array(repeating: Array(repeating: Character(" "), count: c), count: numRows)
        var x = 0
        var y = 0
        for (i, char) in s.enumerated() {
            mat[x][y] = char
            if i % t < numRows - 1 {
                x += 1
            } else {
                x -= 1
                y += 1
            }
        }
        var result = ""
        for i in 0..<numRows {
            for j in 0..<c {
                if mat[i][j] != " " {
                    result.append(mat[i][j])
                }
            }
        }
        return result
    }
}

结果

执行用时 : 172 ms, 击败 16.22% 使用 Swift 的用户

内存消耗 : 28.77 MB, 击败 5.40% 使用 Swift 的用户

Kotlin

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
class Solution {
    fun convert(s: String, numRows: Int): String {
        if (numRows <= 1 || s.length <= numRows) {
            return s
        }
        val n = s.length
        val t = numRows * 2 - 2
        val c = ((n + t - 1) / t) * (numRows - 1)
        val mat = Array(numRows) { CharArray(c) { ' ' } }
        var x = 0
        var y = 0
        for (i in s.indices) {
            mat[x][y] = s[i]
            if (i % t < numRows - 1) {
                ++x
            } else {
                --x
                ++y
            }
        }
        var result = ""
        for (i in 0 until numRows) {
            for (j in 0 until c) {
                if (mat[i][j] != ' ') {
                    result += mat[i][j]
                }
            }
        }
        return result
    }
}

结果

执行用时 : 276 ms, 击败 29.79% 使用 Kotlin 的用户

内存消耗 : 39.07 MB, 击败 14.89% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  String convert(String s, int numRows) {
    if (s.length == 1 || numRows == 1 || s.length < numRows) {
      return s;
    }
    List<String> rows = List.filled(numRows, '');
    int index = 0;
    int currentRow = 0;
    int zigzagLength = 2 * numRows - 2;
    while (index < s.length) {
      rows[currentRow] += s[index];
      if (index % zigzagLength < numRows - 1) {
        currentRow++;
      } else {
        currentRow--;
      }
      index++;
    }
    return rows.join();
  }
}

结果

执行用时 : 368 ms, 击败 37.50% 使用 Dart 的用户

内存消耗 : 149.43 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func convert(s string, numRows int) string {
    if numRows <= 1 || len(s) <= numRows {
        return s
    }
    rows := make([]string, numRows)
    index, step := 0, 1
    for i := 0; i < len(s); i++ {
        rows[index] += string(s[i])
        if index == 0 {
            step = 1
        } else if index == numRows-1 {
            step = -1
        }
        index += step
    }
    result := ""
    for _, row := range rows {
        result += row
    }
    return result
}

结果

执行用时 : 8 ms, 击败 68.58% 使用 Go 的用户

内存消耗 : 7.21 MB, 击败 27.36% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# @param {String} s
# @param {Integer} num_rows
# @return {String}
def convert(s, num_rows)
    return s if num_rows <= 1 || s.length <= num_rows
    rows = Array.new(num_rows, "")
    index, step = 0, 1
    s.each_char do |char|
        rows[index] += char
        if index == 0
            step = 1
        elsif index == num_rows - 1
            step = -1
        end
        index += step
    end
    rows.join
end

结果

执行用时 : 96 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.76 MB, 击败 -% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
object Solution {
  def convert(s: String, numRows: Int): String = {
    if (numRows <= 1 || s.length <= numRows) {
      return s
    }
    val rows = Array.fill(numRows)("") // 创建一个包含 numRows 个空字符串的数组
    var index = 0
    var step = 1
    for (char <- s) {
      rows(index) += char.toString
      if (index == 0) {
        step = 1
      } else if (index == numRows - 1) {
        step = -1
      }
      index += step
    }
    rows.mkString
  }
}

结果

执行用时 : 516 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 55.05 MB, 击败 87.50% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
    pub fn convert(s: String, num_rows: i32) -> String {
        if num_rows <= 1 || s.len() as i32 <= num_rows {
            return s;
        }
        let mut rows: Vec<String> = vec![String::new(); num_rows as usize];
        let mut index = 0;
        let mut step = 1;
        for ch in s.chars() {
            rows[index as usize].push(ch);
            if index == 0 {
                step = 1;
            } else if index == num_rows - 1 {
                step = -1;
            }
            index += step;
        }
        rows.join("")
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.37 MB, 击败 9.00% 使用 Rust 的用户

Racket

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
40
41
42
43
44
45
46
47
(define (convert s num-rows)
  (define (make-log char row)
    `(log ,char ,row))
  (define (log? log)
    (symbol=? (car log) 'log))
  (define (log-char log)
    (cadr log))
  (define (log-row log)
    (if (log? log)
        (caddr log)
        (error log)))
  (define (construct-result log-list)
    (define (iterator row)
      (if (>= row num-rows)
          ""
          (string-append
           (foldl (lambda (current accumulator)
                    (string-append accumulator
                                   (string (log-char current))))
                  ""
                  (filter (lambda (current)
                            (= row (log-row current)))
                          log-list))
           (iterator (+ row 1)))))
    (iterator 0))
  (define (construct-log-list rest-string state row col)
    (if (null? rest-string)
        '()
        (if (symbol=? 'down state)
            (if (= (- num-rows 1) row)
                `(,(make-log (car rest-string) row) .
                  ,(construct-log-list (cdr rest-string) 'up
                                       (- row 1) (+ col 1)))
                `(,(make-log (car rest-string) row) .
                  ,(construct-log-list (cdr rest-string) 'down
                                       (+ row 1) col)))
            (if (= 0 row)
                `(,(make-log (car rest-string) row) .
                  ,(construct-log-list (cdr rest-string) 'down
                                       (+ row 1) col))
                `(,(make-log (car rest-string) row) .
                  ,(construct-log-list (cdr rest-string) 'up
                                       (- row 1) (+ col 1)))))))
  (if (or (= 1 num-rows) (> num-rows (string-length s)))
      s
      (construct-result
       (construct-log-list (string->list s) 'down 0 0))))

结果

执行用时 : 368 ms, 击败 -% 使用 Racket 的用户

内存消耗 : 12368 MB, 击败 -% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
defmodule Solution do
  @spec convert(s :: String.t(), num_rows :: integer) :: String.t()
  def convert(s, 1) do
    s
  end
  def convert(s, num_rows) when is_binary(s) and is_integer(num_rows) and num_rows > 1 do
    group_size = num_rows * 2 - 2
    offset = gen_offset([], 0, 0, num_rows) |> Enum.reverse() |> List.to_tuple()
    ss = String.split(s, "", trim: true)
    mp = gen_map(0, ss, offset, group_size, num_rows, %{})
    len = length(ss)
    w = div(len, group_size)
    w = w * (num_rows - 1)
    r = rem(len, group_size)
    w =
      cond do
        r == 0 -> w
        r < num_rows -> w + 1
        true -> w + (r - num_rows + 1)
      end
    gen_str_i(0, num_rows, "", w, mp)
  end
  defp gen_offset(offset, x, y, num_rows) do
    cond do
      y < num_rows - 1 && x == 0 ->
        gen_offset([{x, y} | offset], x, y + 1, num_rows)
      x < num_rows - 1 ->
        gen_offset([{x, y} | offset], x + 1, y - 1, num_rows)
      true ->
        offset
    end
  end
  defp gen_map(_, [], _, _, _, mp), do: mp
  defp gen_map(step, [head | tail], offset, group_size, num_rows, mp) do
    r = div(step, group_size)
    i = rem(step, group_size)
    op = elem(offset, i)
    gen_map(
      step + 1,
      tail,
      offset,
      group_size,
      num_rows,
      Map.put(mp, {r * (num_rows - 1) + elem(op, 0), elem(op, 1)}, head)
    )
  end
  defp gen_str_i(step, num_rows, str, w, mp) do
    if step <= num_rows - 1 do
      gen_str_i(step + 1, num_rows, gen_str_j(0, str, w, mp, step), w, mp)
    else
      str
    end
  end
  defp gen_str_j(step, str, w, mp, i) do
    j = step
    if step <= w do
      if Map.has_key?(mp, {j, i}) do
        nc = Map.get(mp, {j, i})
        gen_str_j(step + 1, str <> nc, w, mp, i)
      else
        gen_str_j(step + 1, str, w, mp, i)
      end
    else
      str
    end
  end
end

结果

执行用时 : 748 ms, 击败 100.00% 使用 Elixir 的用户

内存消耗 : 70.40 MB, 击败 100.00% 使用 Elixir 的用户