一. 知识普及

  既然是进阶，那肯定是要有一道困难得题目，既然是困难的题目，那肯定不简单，肯定要用到我们平时接触不到的知识。
  为了更好的理解困难题目的代码，我们先将几个函数及其用法。

1.1 atoi

1. 函数atoi是一个将数字字符串转化为数字的函数。
2. atoi的头文件为#include <stdlib.h>。
3. 定义函数为 int atoi(const char *nptr);
   代码演示：

#include <stdio.h>
#include <stdlib.h>int main(){char nstr[] = "12312";int n = atoi(nstr);printf("%d\n", n);
}

输出结果：

1.2 log

log()函数就是一个求数学对数logn的函数。
引入的头文件为#include <math.h>

通常log以10为底

#include <stdio.h>
#include <math.h>int main(){int x1 = log10(100);printf("%d\n", x1);//输出为2return 0;
}

而如果要求以m为底n为对数的值其写法如下：

#include <stdio.h>
#include <math.h>int main(){int m = 2;int n = 32;double x = log(n) / log(m);printf("%f\n", x);//输出为5.000000
}

1.3 pow

pow函数是一个求幂的函数

#include <stdio.h>
#include <math.h>int main(){double x = 2;float y = 10;int n = pow(x, y);printf("%d\n", n);//输出结果为1024
}

1.4 floor

floor()函数是cmath标头的库函数，用于查找给定数字的向上舍入(向下)值，它接受一个数字并返回不大于给定数字的最大整数值。
就是用来计算四舍五入的一个函数。

二. 进阶题解

168. Excel表列名称

168. Excel表列名称


分析：
  在前面的进制转化讲解中，我们得到，一个长度为n，设每一位为ai，则可以写成这样一组数：[ai-1,ai-2,…,a0]。其中0 <= i < n，1 <= ai <= 26，则其转化为十进制的公式为：

sum = ∑ai * 26 ^ i (0 <= i <= n - 1)

我们可以将a0分离出来后，并提出一个26得到：

sum = a0 + 26 * ∑ai * 26 ^ i (0 <= i <= n - 2)

在对其进行两边同时减一：

sum - 1= (a0 - 1) + 26 * ∑ai * 26 ^ i (0 <= i <= n - 2) 因为0 <= a0 - 1 <= 25，所以(a0 - 1) 是(sum - 1)除26的余数。 这样我们就知道，a0 = (sum - 1) % 26 + 1; sum' = (sum - a0) / 26 以此类推，知道sum = 0，我们就能把所有的a0,a1....an-1计算出来。

代码如下：

void reserve(char* ret, int retSize){int left = 0, right = retSize - 1;while(left < right){char temp = ret[left];ret[left] = ret[right];ret[right] = temp;left++;right--;}
}char * convertToTitle(int columnNumber){char* ret = malloc(8);int retSize = 0;while(columnNumber){int a0 = (columnNumber - 1) % 26;//因为这里+1后下面转化为字符又要-1，两者抵消了ret[retSize++] = a0 + 'A';columnNumber = (columnNumber- a0) / 26; }ret[retSize] = '\0';reserve(ret, retSize);return ret;
}

171. Excel 表列序号

171. Excel 表列序号



分析：
  这道题实际上很简单，直接套用低进制向高进制转化的公式即可。
代码如下：

//求幂
int squire(int x, int n){if(n == 0){return 1;}int v = squire(x, n / 2);return n % 2 == 0 ? v * v : v * v * x;
}int titleToNumber(char * columnTitle){int ret = 0;int len = strlen(columnTitle);for(int i = 0; i < len; i++){int n = columnTitle[i] - 'A' + 1;ret += n * squire(26, len - i - 1);}return ret;
}

当然，还有另一种写法，并且这种写法在之前的题目中也有讲过。

int titleToNumber(char * columnTitle){int ret = 0;int len = strlen(columnTitle);long k = 1;for(int i = len - 1; i >= 0; i--){int n = columnTitle[i] - 'A' + 1;ret += n * k;k *= 26;}return ret;
}

483. 最小好进制

483. 最小好进制


解析：
  我们假设整数n，在k进制下所有的数都为1，假设转化k进制后由m + 1位数，则

n = k ^ 0 + k ^ 1 + .... + k ^ m 我们先考虑两个特殊情况， 当m = 0时，n = 1，但题目给定n在[3,10⁸]，所有此情况不存在。 当m = 0时，n = k⁰ + k¹ =>k = n - 1 => k >= 2，所以后面的情况都满足条件。 现在我们要证明两个结论： 结论一：

由上面的公式我们可以发现它是一个等比数列，且a1=1，q = k
计算得：

n = (1 - k ^ (m + 1))/(1 - k) 通过交换得： k ^ (m + 1) = kn - n + 1 很明显，kn - n + 1 < kn，故k ^ (m + 1) < kn

通过化简得：

因为n属于[3,10⁸]，且k >= 2，最后得到0 < m < 60

结论二：k = [n ^ (1 / m)]
由第一条公式我们可知：

n = k ^ 0 + k ^ 1 + .... + k ^ m > k ^ m 在根据二项式定理，我们可以得到：

根据上式我们又能得到:

(k + 1) ^ m > k⁰ + k¹+...+k^m = n 综合上面得不等式，我们可以得到： k ^ m < n < (k + 1) ^ m 两边开方得： k < n ^ (1/ m) < k + 1 由这个公式我们可知，n ^ (1/ m)必然是一个小数，所以我们取整数部分k = [n ^ (1 / m)]

根据上面两个结论我们便可以开始写代码了。
代码如下：

char * smallestGoodBase(char * n){//字符串转数字long nVal = atol(n);//根据公式求最大数：log nValint mMax = floor(log(nVal) / log(2));char* ret = (char*)malloc(mMax + 1);for(int m = mMax; m > 1; m--){//根据推导出的公式模拟进制k=n的(1.0/m)次方int k = pow(nVal, 1.0 / m);long mul = 1, sum = 1;//模拟进制转换，将k进制转化为十进制for(int i = 0; i < m; i++){mul *= k;sum += mul;}//如果得到结果与给定结果相等，说明k为最小好进制if(sum == nVal){sprintf(ret, "%lld", k);return ret;}}//当在[2,n^(1.0 / mMax)]的范围内都没有的情况sprintf(ret, "%lld", nVal - 1);return ret;}