打印1到最大的n位数

这道题是面试过可能会遇到的手写代码题。如n为3时,那么需要打印1到999。需要注意的是当输入的n很大时,最大的n位数是不能通过int或者long long int来表示,此时可以使用字符数组来存储。

思路一: 1到n位最大数值采用字符数组存储。数值的高位存储在字符数组的低地址位。

#include <string.h>

#include <iostream>
using namespace std;

//利用case语句使字符++  
char CharPlus(char a)  
{  
    char b;  
    switch ( a )  
    {  
    case '0': b = '1';  break;  
    case '1': b = '2';  break;  
    case '2': b = '3';  break;  
    case '3': b = '4';  break;  
    case '4': b = '5';  break;  
    case '5': b = '6';  break;  
    case '6': b = '7';  break;  
    case '7': b = '8';  break;  
    case '8': b = '9';  break;  
    case '9': b = '0';  break;  
    default:  cout<<"error"<<endl;  
    }  
    return b;  
}  

bool Increment(char* numchar,int len)  
{  
    bool flag = false;  
    if ( numchar[0] == '9' )                        //用于判断越界情况处理      
        flag=true;
    for (len = len-1; len >= 0; len-- )             //从数字低位开始更新
    {  
        numchar[len] = CharPlus( numchar[len] );    //更新该位上的数字  
        if ( numchar[len] != '0' )                  //判断是否向高位进位,如果该为由9->0,则向高位进位
            break;  
        if ( flag && numchar[0]=='0' )              //数值最高位从'9'变为'0'时,数值溢出,结束递增
            return false;  
    }  
    return true;  
}  

//打印输出时,要符合一般习惯,把前面的0去掉,从左开始打印 
void PrintNum(char* numchar){  
    int i = 0;  
    bool flag = false;  
    while(numchar[i++] == '0');//找到数值从高位到低位第一个不为'0'的位置
    --i;  
    while ( numchar[i] != '\0' ){  
        cout<<numchar[i]; 
        i++;  
    }  
    cout<<endl;  
}  

void Print1ToMaxOfNDigits(int n){  
    if ( n <= 0 ){  
        cout<<n<<" is illegal"<<endl;  
        return;  
    }
    char * numchar = new char[n+1];  
    memset( numchar,'0',sizeof(char)*(n+1) );         
    numchar[n] = '\0';                  //先对字符串数组初始化  

    while ( Increment(numchar,n) )      //字符串数组++,如果已经是最大则返回false  
    {  
        PrintNum(numchar);              //打印出该数字  
    }  
    delete[] numchar;  
}  

int main(){
    Print1ToMaxOfNDigits(1);
}

这种做法便于理解,但是代码却有点冗长。要在面试短短几十分钟内写完整,确实有点难度。这锻炼了考生的耐心程度。一般面试时,写的代码都不会很长,大概50行左右。因此,我们可以换思路去考虑问题。

思路二: 换思路,n位所有十进制数其实就是n个0-9的数全排列的过程,只是排在前面的0我们不打印出来。

全排列可以用递归去写,递归结束条件是我们已经设置了数字的最后一位。

void Print1ToMaxOfNDigitsRecursively(char* numchar, int length, int index)  
{  
    if ( index == length -1)  
    {  
        PrintNum(numchar);  
        return;  
    }  
    for ( int i = 0; i < 10; i++ )  
    {  
        numchar[index+1] = i +'0';  
        Print1ToMaxOfNDigitsRecursively(numchar, length, index+1);  
    }  

}  
void Print1ToMaxOfNDigits(int n)  
{  
    if ( n <= 0 )  
    {  
        cout<<n<<" is illegal"<<endl;  
        return;  
    }  
    char * numchar = new char[n+1];  
    numchar[n] = '\0';                  //先对字符串数组初始化  

    for ( int i = 0; i < 10; i++ )  
    {  
        numchar[0] = i + '0';  
        Print1ToMaxOfNDigitsRecursively(numchar,n,0);  
    }  

    delete[] numchar;  
}  

测试用例 功能测试(输入1、2、3……)

特殊输入测试(输入-1,0)。

考点: 考查解决大数问题的能力; 时间空间复杂度尽可能好; 能否用递归做。

总结: 如果面试题是关于n位的整数并且没有限定n的取值范围,或者是输入任意大小的整数,那么这个题目很有可能是需要考虑大数问题。字符串是一个简单、有效的表示大数的方法。


参考文献

[1]http://blog.csdn.net/zhaojinjia/article/details/8776639. [2]剑指offer.何海涛.电子工业出版社

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

8020
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继...

9910
来自专栏小樱的经验随笔

HUST 1586 数字排列

1586 - 数字排列 时间限制:1秒 内存限制:128兆 91 次提交 36 次通过 题目描述现有n个k位的数字,你的任务是重新安排数字每一位的位置,使得...

304120
来自专栏backend技术总结

PHP浮点数

上面输出的结果是57, 而不是58, 为什么呢, 因为 你看似有穷的小数, 在计算机的二进制表示里却是无穷的(鸟哥的原话),0.58用二进制后, 重新计算出来的...

25850
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-06.总结二维数组,面向对象

1:二维数组(理解) (1)元素是一维数组的数组。 (2)格式: A:数据类型[][] 数组名 = new 数据类型[m][n]; B:数据类型[][]...

30340
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

13310
来自专栏程序员叨叨叨

5.2 数组类型

在着色程序中,数组通常的使用目的是:作为从外部应用程序传入大量参数到 Cg 的顶点程序中的形参接口,例如与皮肤形变相关的矩阵数组,或者光照参数数组等。

6810
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(06-10打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

12720
来自专栏趣谈编程

快速排序(基础版)

17130
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

11720

扫码关注云+社区

领取腾讯云代金券