[LeetCode]Remove 9

这道题乍看之下有点麻烦，其实我们仔细想一下就可以明白，如果在十进制中把所有的9给去掉，然后把所有数字从小到大排列：

• 1, 2, 3, 4, 5, 6, 7, 8, 10 , 11, 12, 13, 14, 15, 16, 17, 18, 20...

这不正是九进制从小到大对应的每个数。那么你要找九进制中第k(十进制)大的数，只需要把k转化成九进制即可。这个很好理解，举个例子，九进制中第100(十进制)大的数，就是九进制中第121(100转化成九进制)大的数，也就是121。

禁止转化的问题，我们用除k取余法即可，时间复杂度为O(n)，n为输入数字的位数，代码如下：

	class Solution {
	public:
	int newInteger(int n) {
	int res = 0, base = 9, tens = 1;
	while(n)
	{
	int digit = n % base;
	res = digit * tens + res;
	n /= base;
	tens *= 10;
	}
	return res;
	}
	};

view raw Remove 9.cpp hosted with ❤ by GitHub