乐趣区

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

jiezi

办法一：

执行用时: 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 为字符串长度。

退出移动版