关于算法:6-Z字形变换LeetCodeC语言

办法一：

执行用时: 76 ms，在所有 C 提交中击败了23.00%的用户
内存耗费: 6.4 MB，在所有 C 提交中击败了60.00%的用户

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *zStr(char *str, int numRows)
{
  int k = 0;
  int len = strlen(str);
  if (numRows < 2) {
        return str;
  }
  char *resStr = (char *)malloc((len + 1) * sizeof(char));
  for (int row = 0; row < numRows; row++)
  {
    for (int i = 0; i < len; i++)
    {
      // 通过观察Z形字符串，能够发现以下法则：将其以2 * numRows - 2个数归为一组，每一组的下标对其这组数字个数求余
      // 可失去两组后果：一组与row相等（即Z形字符串的行的下标，从0开始），一组与row的和等于numRows - 2
      // 上面从第一行开始循环，将第一行符合条件的元素搁置到新数组，其后每行顺次进行，直到将所有元素搁置到新数组
      if (i % (2 * numRows - 2) == row || i % (2 * numRows - 2) == 2 * numRows - 2 - row)
      {
        resStr[k++] = str[i];
      }
    }
  }
  resStr[len] = '\0';
  return resStr;
}

int main(void)
{
  char *str = "nfgszvcsdx";
  int numRows = 5;
  char *retStr = zStr(str, numRows);
  int i = 0;
  while (retStr[i] != '\0')
  {
    printf("%c", retStr[i]);
    i++;
  }
  printf("\n");
}

这个办法事件复杂度为O(numRows*n)，n为字符串长度，numRows为字符串长度。
空间复杂度为O(n)。
办法二：
执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户
内存耗费：6.6 MB, 在所有 C 提交中击败了44.94%的用户

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *convert(char *str, int numRows)
{
  int k = 0;
  int len = strlen(str);
  char *resStr = (char *)malloc((len + 1) * sizeof(char));
  // 非凡状况：行数小于2，或者字符串长度不大于行数，则间接返回字符串
  // 因为此时要么只有一行，要么只有一列
  if (numRows < 2 || len <= numRows)
  {
    return str;
  }
  for (int row = 0; row < numRows; row++)
  {
    // 将每一个numRows指定的行的行首字符存储到返回字符
    resStr[k++] = str[row];
    for (int i = row; i < len;)
    {
      // 在每一个numRows行，寻找原字符串中相应的元素下标

      // 每行第二个元素下标与第一个元素下标具备以下关系：j = i + 2numRows - 2 - 2row
      // 非凡状况：最初一行第一个和第二个元素是重合的，因而上面的表达式为： i += 0 -> i，即i没变
      i += 2 * (numRows - row - 1);
      // 非凡状况：最初一行第一个和第二个元素是重合的，因而，不须要计算，
      // 在这里排除最初一行：numRows - row > 1
      if (numRows - row > 1 && i < len) {
        resStr[k++] = str[i];
      }
      // 每行第二个元素和第三个元素下标具备以下关系：j = i + 2row
      // 非凡状况：最初一行第一个和第二个元素是重合的，因而第三个元素与第一个元素下标合乎此关系
      i += 2 * row;
      if (row > 0 && i < len)
      {
        resStr[k++] = str[i];
      }
    }
  }
  resStr[k] = '\0';
  return resStr;
}

int main(void)
{
  char *str = "nfaskofncklasnfclas";
  int numRows = 5;
  char *retStr = convert(str, numRows);
  int i = 0;
  while (retStr[i] != '\0')
  {
    printf("%c", retStr[i]);
    i++;
  }
  printf("\n");
}

此办法工夫复杂度为O(n)，n为字符串长度。尽管循环时嵌套的，然而最终循环的次数是n次，将n个字符全副搁置到新数组。
空间复杂度为O(n)，n为字符串长度。