[解题报告](第20讲) 进制转换(二) - 进阶

2022-04-12 82

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： [解题报告](第20讲) 进制转换(二) - 进阶

零、写在前面

这是打卡的第二十天，今天题目还是有点难度的，不过就是题量下来了，可以沉淀一下之前的题目了，主要知识点在

《算法零基础100讲》(第20讲) 进制转换(二) - 进阶

https://blog.csdn.net/WhereIsHeroFrom/article/details/120876000

一、主要知识点

1.进制的转换(也就是辗转相除法)

while(columnNumber) {            
        num[ retSize++ ] = columnNumber % 26;
        columnNumber /= 26;
    }

二、课后习题

168. Excel表列名称

https://leetcode-cn.com/problems/excel-sheet-column-title/

主要思想

1.转化为26进制，由于1的影响我们需要再判断的时候加入余数为0的时候的借位

2.将生成的字符串反转

char * convertToTitle(int columnNumber){
    char *s = malloc(sizeof(char) * 256);   //申请返回空间
    int count = 0;
    while(columnNumber){            //转数组
        if(columnNumber % 26 != 0)
            s[count++] = columnNumber % 26 +'A' - 1;
        else {                      //等于0的时候借位
            s[count++] = 'Z';
            columnNumber --;
        }
        columnNumber /= 26;
    }
    s[count] = 0;               //加入结束符
    for(int i = 0;i < count/2;i++){        //反转字符串
        s[i] = s[i] ^ s[count - i - 1];
        s[count - 1 - i] = s[i] ^ s[count - 1 - i];
        s[i] = s[i] ^ s[count - i - 1];
    }
    return s;
}

结果分析

客官可还满意？

171. Excel 表列序号

https://leetcode-cn.com/problems/excel-sheet-column-number/

主要思想

有了第一题的思想，这道题就是洒洒水啦，注意一下需要+1就好了

int titleToNumber(char * columnTitle){
    int count = 0;                      //统计数字
    for(int i = 0;columnTitle[i];++i){
        count *= 26;
        count += columnTitle[i] - 'A' + 1;  //1的对应补偿
    }
    return count;
}

结果分析

客官可还满意？

483. 最小好进制

https://leetcode-cn.com/problems/smallest-good-base/

主要思想

这道题有一点复杂，因为包含了一点点数学

我们很容易得到当m>=1的时候有

m的个数明显是比k的可能情况少很多，便于循环查找

也就是并且当k>=2的时候且m>1的时候即

当m==1的时候，我们很容易得到 k = n -1。

题设条件告诉我们，k>=2,则有也就是用于判断m最大值

这里也可以看出来m小很多，而k是要从2到n；

我们按照上面的方式查找，找到以后返回就好了，注意转字符串的反转。

char * smallestGoodBase(char * n){
    long long nval = 0,k;
    for(int i = 0;n[i];++i){        //字符串转整形
        nval *= 10;
        nval += n[i] -'0';
    }
    int mmax = log(nval)/log(2);    //m位数的最大值向下取整
    for(;mmax > 1;mmax--){             //枚举m尝试找到k  
        k = pow(nval,1.0/mmax);         //k一定等于向下取整   m=1的时候不能这么计算
        long long temp = nval;
        while(temp){
            if(temp % k != 1)   break;
            temp /= k;
        }
        if(temp == 0) break;
    }
    char *ans = malloc(sizeof(char) * (mmax + 1));//创建返回函数
    int i = 0;
    if(mmax == 1)  k = nval - 1;        //如果mmax = 1 则k等于最大值-1
    while(k){
        ans[i++] = k % 10 + '0';
        k /= 10;
    }
    ans[i] = 0;             //插入结束符
    for(int j = 0;j < i / 2;j++){       //反转字符串
        ans[j] = ans[j] ^ ans[i - 1 - j];
        ans[i - 1 - j] = ans[j] ^ ans[i - 1 -j];
        ans[j] = ans[j] ^ ans[i - 1 - j];
    }
    return ans;
}