共计 1465 个字符，预计需要花费 4 分钟才能阅读完成。
最近去面试了，面了几家公司，粗浅意识到一个情理，越是根底的问题越重要，越能考查一个人的技术功底与逻辑思维。比方咱们接下来要说的 求两个数的最大公约数 的问题。这类简略的算法题目个别会呈现在面试环节，面试官要求你当场手撕的那种。
言归正传，首先咱们要晓得面试官出 求两个数的最大公约数 这个题目的目标是什么。知己知彼，能力百战不殆嘛。这个问题首先考查的是 候选人的数学功底，就是看你知不知道一些求公约数的算法，比方辗转相除法、更相减损法等；其次就是考查你的代码能力了，看你能不能把算法用代码写进去，写的代码有没有 bug，注没留神边界的解决等等。上面咱们别离来看一下，不同的候选人会有什么样的体现。
第一种，数学功底不扎实的，不晓得目前已有的求公约数的办法，那预计只能写出上面这种代码了。
// 暴力求解
private static int getCommonDivisor(int m,int n){
// 非法参数的解决
if(m <= 0 || n <= 0){return -1;}
int min = Math.min(m,n);
int res = 1;
for(int i = 1;i <= min;i ++){if(m % i == 0 && n % i == 0){res = i;}
}
return res;
}这种就是暴力求解，不做过多解释了。面试官显然不会称心这种代码。
第二种，晓得一些求公约数的算法，然而无奈用代码实现，这种属于代码功力不够的，预计只能回家等告诉了。
第三种，晓得求公约数的算法，并且能写出代码的。比如说通知面试官晓得 更相减损法 能够求解，基本原理是 以较大的数减较小的数，接着把所得的差与较小的数比拟，并以大数减小数。持续这个操作，直到所得的减数和差相等为止。个别这时候面试官就会示意称许，而后让你代码实现下，接着你就写出了如下的代码：
// 更相减损法
private static int getCommonDivisor2(int m,int n){
// 非法参数的解决
if(m <= 0 || n <= 0){return -1;}
while(m != n){if(m > n){m = m - n;}else{n = n - m;}
}
return m;
}怎么样，是不是很简洁！
当然，你也能够用辗转相除法实现，其基本原理是 两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。代码如下:
// 辗转相除法
// 两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数
private static int getCommonDivisor3(int m,int n){
// 非法参数的解决
if(m <= 0 || n <= 0){return -1;}
if(m < n){
int temp = m;
m = n;
n = temp;
}
int c = m % n;
while(c != 0){
m = n;
n = c;
c = m % n;
}
return n;
}个别状况下，能说出最相熟的一种办法并给出其具体实现就能够了，这道题目根本就过关了。
最初，其实求最大公约数的办法还有很多，比方质因数分解法、短除法等等，大家感兴趣的话能够多去理解下，扩大下本人的思维。
感觉文章有用的话，点赞 + 关注 呗，好让更多的人看到这篇文章，也激励博主写出更多的好文章。更多对于 算法、数据结构和计算机基础知识 的内容，欢送扫码关注我的原创公众号「超悦编程」。
举荐浏览
为什么有红黑树？什么是红黑树？看完这篇你就明确了
《深入浅出话数据结构》系列之什么是 B 树、B+ 树？为什么二叉查找树不行？
都 2020 年了，据说你还不会归并排序？手把手教你手写归并排序算法
为什么会有多线程？什么是线程平安？如何保障线程平安？
《一文说透数据结构》系列之什么是堆？看这一篇就够了
