【剑指offer】面试题12：打印1到最大的n位数

2019-11-06 07:29:36

字体：大中小

来源：转载

供稿：网友

整体结构

void PRint1ToMaxOfDigits(int n){ if (n <=0)//对于n=0也需要限制，因为无法跳出循环，造成死循环 { return; } char *number = new char[n + 1]; memset(number, '0', n + 1); number[n] = '/0'; while (!Increment(number))//当空间第一位进位时，循环结束 { PrintNumber(number); } delete[]number; number = NULL;}

字符串模拟加法：

bool Increment(char *number){ bool isOverflow = false; int nTakeOver = 0; int nLength = strlen(number); //从最低位开始加 for (int i = nLength - 1; i >= 0;--i) { int nSum = number[i] - '0' + nTakeOver; if (i == nLength - 1) { ++nSum; } if (nSum >= 10) { if (i == 0) { isOverflow = true; } else { nSum -= 10; nTakeOver = 1; number[i] = '0' + nSum; } } else { number[i] = '0' + nSum; break; } } return isOverflow;}

出于真实角度，若字符串前面几个字符为‘0’,我们不需要将他们打印

void PrintNumber(char *number){ bool isBeginning0 = true; int nLength = strlen(number); for (int i = 0; i < nLength - 1; ++i) { if (isBeginning0&&number[i] != 0) { isBeginning0 = false; } if (!isBeginning0) { printf("%c", number[i]); } } printf("/t");}

测试：

int main(){ Print1ToMaxOfDigits(2); return 0;}

这里写图片描述

//换种思路把思路转成数字排列的解法，递归让代码更简单//全排列用递归很容易表达，数字的每一位都可能是0~9中的每一个数//n位所有十进制数其实就是n个从0到9的全排列，也就是说把每一位的0~9排列一遍，就得到了所有的十进制数，只是我们在打印的时候，数字排在前面的0我们不打印出来罢了void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index);void Print1ToMaxOfNDigits(int n){ if (n <= 0) { return; } char *number = new char[n + 1]; number[n] = '/0'; for (int i = 0; i < 10; ++i) { number[0] = i + '0'; Print1ToMaxOfNDigitsRecursively(number, n, 0); } delete[] number;}void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index){ if (index == length - 1) { PrintNumber(number); return; } for (int i = 0; i < 10; ++i) { number[index + 1] = i + '0'; Print1ToMaxOfNDigitsRecursively(number, length, index + 1); }}

上一篇：1889 kotomi and function

下一篇：BZOJ 3522 DFS+DP

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注