gcd算法其实就是著名的欧几里德算法,大家感觉是不是很高大上呢,没那么可怕啦,大家应该都学过,
其实就是一个求两个正整数最大公约数的算法,即辗转相除法。
最重要的等式莫过于（核心中的核心）：
gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0) a mod b就是a 除以 b取余
int gcd(int a,int b)//求最大公约数
{
return b==0?a:gcd(b,a%b);
}这就行了？ 对，这就可以实现求最大公约数了，仔细看看这个代码，其实原理是一样的，就是辗转相除，只不过以另外一种递归的形式出现在大家面前，也更便于大家的记忆，当然也是省去了代码量。
<script>
/**
* @param {string} str1
* @param {string} str2
* @return {string}
*/
var gcdOfStrings = function (str1, str2) {
// 有公因子的字符串，必定是由若干个相同公共字符串组成的
// 因此他们互加必相等,如果不等,则不满足要求
if (str1 + str2 !== str2 + str1) return ''
// 定义一个gcd算法
const gcd = (a, b) => (0 === b ? a : gcd(b, a % b))
// 调用gcd算法得出最大公约数，根据公约数截取公因子字符串
return str1.substring(0, gcd(str1.length, str2.length))
};
console.log(gcdOfStrings("ABCABC", "ABC"))
</script>
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/149640.html
