211以下就别天天想着进大厂了
老鬼约 3 分钟刚刷到个贴子，说“211以下的就别天天想着进大厂了”，评论区那叫一个热闹🙄。
作为程序员我想说，这种论调真的是老生常谈，甚至有点误导。学历确实是敲门砖，尤其是刚毕业那几年，但真不是唯一标准。很多大厂要的是你能不能干活、能不能解决问题，不是你是不是清北复交。面试官在看你项目经验和编码能力的时候，压根不在意你是985还是双非。
网友有的说得也现实，说“学历不够就靠简历硬打”，我挺认同的。你要真想进大厂，那就得做点能拿得出手的项目、Leetcode 刷上千题也不是没人干过💻。靠实力拼出来的比比皆是，别拿出身当挡箭牌。【备注:文末可领最新资料】
算法题：最小好进制
我当时在小区门口等电梯，手里还提着菜，想了想，诶，这题以前不是力扣上刷到过吗？好像挺有意思的，说白了其实就是给你一个数字n，让你找一个最小的进制k(>=2)，让n用k进制表示的时候，全是1，比如11，13这些。你仔细琢磨下，有点像小时候玩巴掌数，1、11、111这种，只不过是进制不一样。
其实这题一上来，最暴力的方法是啥？就是从2开始挨个试，看n能不能拆成k进制下全是1的形式。可你要是直接这么搞，n大点分分钟超时，尤其Java整数一大，计算很快就慢下来。
不过我后来才发现有个思路贼巧，就是说你假设n可以写成m个1的形式，比如说 111...1(k进制m个1)，那其实就是个等比数列的和，数学老师应该都讲过的吧？反正我高中的时候没少抄作业哈哈，公式就是：(k^m - 1) / (k - 1) = n，明白吧？这m其实就是位数，最少2位。
你再想，k肯定越大越好试出来全1的可能性就越小，所以你可以反着来，对m从大往小试。大概最多到log2(n)+1，Java用Math.log来算就行，懒得自己推。
说到这儿，晚上在家我就写了段Java代码，边写边想着明天得给组里的小李也讲讲，这货老说算法难，每天就在那刷短视频，我服了...
public String smallestGoodBase(String n){
long num = Long.parseLong(n);
for (int m = (int)(Math.log(num + 1) / Math.log(2)); m >= 2; m--) {
long k = getBase(num, m);
if (k != -1) {
return String.valueOf(k);
}
}
return String.valueOf(num - 1);
}
privatelonggetBase(long n, int m){
long left = 2, right = (long)Math.pow(n, 1.0/(m-1)) + 1;
while (left <= right) {
long mid = left + (right - left) / 2;
long sum = 1, cur = 1;
for (int i = 1; i < m; i++) {
if (sum > n / mid) {
sum = n + 1;
break;
}
cur *= mid;
sum += cur;
}
if (sum == n) return mid;
elseif (sum < n) left = mid + 1;
else right = mid - 1;
}
return -1;
}
你看，那个for循环其实就是等比数列倒着试位数，然后每次用二分法去找合适的k，这样效率高一点，避免暴力超时。小李老问我为啥要用二分，你们懂吧，试一个数n的m次方，直接递推太慢了，二分就跟猜拳一样快。
哦对，还有一点，Java那个long类型一定要小心溢出，尤其是乘法那里，别一不小心溢了全WA了，跟前两天在公司给测试写的代码一样，刚上线就被打回来了，气得我直接去抽根烟压压惊。
反正这题要点就是别想着挨个枚举k，从位数（m）去考虑，试出来就快多了，真写不出来也别太焦虑，拿个纸算一下等比数列就知道怎么回事了。
-END-
我为大家打造了一份RPA教程，完全免费：https://www.songshuhezi.com/rpa.html