Ex17 打印从1到最大的n位数

题目描述

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

解题思路

好吧，LeetCode这一题和《剑指Offer》上的题目差别有点儿大，没什么好说的。

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *
printNumbers (int n, int *returnSize)
{
  if (n <= 0)
    return NULL;
  *returnSize = 0;
  for (; n; --n)
    *returnSize = *returnSize * 10 + 9;
  int *rtn = (int *)malloc (*returnSize * sizeof (int));
  for (int i = 0; i < *returnSize; ++i)
    {
      rtn[i] = i + 1;
    }
  return rtn;
}

结果

执行结果：通过

执行用时：120 ms, 在所有 C 提交中击败了27.03%的用户

内存消耗：17.6 MB, 在所有 C 提交中击败了13.27%的用户

备注

按照《剑指Offer》的题目描述，再书写以下代码。主要的思路是将从1打印到N位数的最大数的这个过程转换为全排列的过程。当然，其中要注意：

• 用字符数组；
• 第一位不能是0。

全排列的递归写法：每一位都是0～9的一个数，然后设置下一位。递归结束的条件是已经设置了数字的最后一位。

void print_array (char *array, int length);
void print_numbers_recursive (int cur_length, int length, char *array);

void
PrintNumbers2 (int n)
{
  if (n <= 0)
    return;
  char *array = (char *)malloc ((n + 1) * sizeof (char));
  memset (array, '0', n);
  array[n] = '\0';
  for (int i = 0; i < n; ++i)
    {
      print_numbers_recursive (0, i + 1, array);
    }
  free (array);
}

void
print_numbers_recursive (int cur_length, int length, char *array)
{
  if (cur_length == length)
    {
      print_array (array, length);
      return;
    }
  for (char c = '0'; c <= '9'; ++c)
    {
      if (c == '0' && cur_length == 0)
        continue;
      array[cur_length] = c;
      print_numbers_recursive (cur_length + 1, length, array);
    }
}

void
print_array (char *array, int length)
{
  for (int i = 0; i < length; ++i)
    {
      printf ("%c", array[i]);
    }
  printf ("\t");
}