剑指Offer - 面试题17:打印从1到最大的n位数

简介: 剑指Offer - 面试题17:打印从1到最大的n位数

题目

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


分析

暴力法

打印的最小值为1,打印的最大值=10n-1。我们可以一次循环遍历,从i开始遍历到10n-1; 时间复杂度O(n),空间复杂度O(1)。

C

#include<stdio.h>
void PrintToMaxOfNDigits(int n)//打印函数
{
  if(n < 0)
  {
    return ;
  }
  int max = pow(10, n) - 1;
  int i = 0;
  for(i = 0; i < max; i++)
  {
    printf("%d\n", i);
  }
}
int main()
{
  PrintToMaxOfNDigits(3);
  return 0;
}


忽略了最大的一个问题,如果n很大时,int就放不下了,这个时候只能放在字符串中,那么问题就转换成了如何将数据存入字符串和如何从字符串中输入避免前置0。


数组存储

创建一个int型数组,长度n+1,数据从n下标开始存到1,下标0留着最后一次进位,只要发现下标0的位置变成1就停止循环。

C

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
void PrintToMaxOfNDigits(int n)//打印函数
{
  if(n < 0)
  {
    return ;
  }
  int* m = (int*)calloc(n + 1, sizeof(int));
  if (NULL == m)
  {
    perror("申请空间失败!\n");
    return;
  }
  int i = n;
  int j = 0;
  int flag = 0;//0表示是前置0不输出,  1就可以输出了
  while (m[0] == 0)
  {
    i = n;
    while (1) //必须加一次
    {
      if (m[i] != 9)
      {
        m[i] += 1;
        break;
      }
      else
      {
        m[i] = 0;
        i--;
      }
    }
    flag = 0;
    for (j = 1; j < n + 1; j++)//输出
    {
      if (m[j] == 0 && flag == 1)
      {
        printf("%d", m[j]);
      }
      else if(m[j] != 0)
      {
        flag = 1; //之后的0就可以输出了
        printf("%d", m[j]);
      }
    }
    printf("\n");
  }
}
int main()
{
  PrintToMaxOfNDigits(2);
  return 0;
}


递归法

上述用数组思维存储超大数,可以用递归实现。最少1位,最高n位。

C

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int count = 1;
void Print(int* a, int len)//输出数组中存放的字符串
{
  bool flag = false;//判断是否为前置0
  for (int i = 1; i < len; i++)
  {
    if (flag == false && a[i] != 0) 
    {
      flag = true;
    }
    if (flag == true)
    {
      printf("%d", a[i]);
    }
  }
  printf("\t");
  if (count % 10 == 0)
  {
    printf("\n");
  }
  count++;
}
void Recursion(int* a, int len, int index)//递归
{
  if(index == len)
  {
    Print(a, len);
    return;
  }
  int i = 0;
  for (i = 0; i < 10; i++)
  {
    a[index] = i;
    Recursion(a, len, index + 1);
  }
}
void Print1ToMaxOfNDigits(int n)
{
  if (n < 0)
  {
    return;
  }
  int* a = (int*)calloc(n + 1, sizeof(int));
  Recursion(a, n + 1, 1);
  free(a);
  return ;
}
int main()
{
  Print1ToMaxOfNDigits(2);
  return 0;
}


本章完!

目录
相关文章
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面