惠州网站优化建设,销售网,在哪个网站做推广效果更佳,小本本教你做网站其实是求a、b#xff08;ab#xff09;最大公约数。 #xff08;leetcode 1979. 找出数组的最大公约数#xff09; 方法一#xff1a;遍历#xff0c;遍历的思想就是从2开始到b(或者b/2)结束#xff0c;如果其中某个数都能被两者整除#xff0c;那该数就是最大公约…其实是求a、bab最大公约数。 leetcode 1979. 找出数组的最大公约数 方法一遍历遍历的思想就是从2开始到b(或者b/2)结束如果其中某个数都能被两者整除那该数就是最大公约数。
nums[a,b]
A_max max(nums)
B_min min(nums)
int greatestCommonDivisor 1;
for i in range(2,b1):if A_max%i0 and B_min%i0:greatestCommonDivisor i方法二辗转相除法 定理两个正整数a、bab的最大公约数就是b和a%ba除以b的余数的最大公约数。 边界是当余数为0时最大公约数为另一个数。
class Solution:def findGCD(self, nums: List[int]) - int:def gcd(a,b): #abif b0:return aelse:return gcd(b, a%b)BigNum, SmallNum max(nums), min(nums)return gcd(SmallNum, BigNum%SmallNum)方法三更相减损法 定理两个正整数a、bab的最大公约数就是b和a-b的最大公约数。 边界是当差为0时最大公约数为另一个数。
class Solution:def findGCD(self, nums: List[int]) - int:BigNum, SmallNum max(nums), min(nums)def gcd(a,b):if a b:return aelif a b:return gcd(b, a-b)else:return gcd(a, b-a)return gcd(SmallNum, BigNum)方法四结合辗转相除法和更相减损法主要是取模操作可以用移位替代分情况讨论 如果a和b都是偶数那么gcd(a,b)2*gcd(a/2,b/2)2*gcd(a1,b1) 如果a是偶数b是奇数那么gcd(a,b)gcd(a/2,b)gcd(a1,b) 如果a是奇数b是偶数那么gcd(a,b)gcd(a,b/2)gcd(a,b1) 如果a和b都是奇数那么gcd(a,b)gcd(a,a-b),然后此时a-b一定是偶数又可以进行移位操作。
class Solution:def findGCD(self, nums: List[int]) - int:BigNum, SmallNum max(nums), min(nums)def gcd(a,b):if a b:return aelse:#与1做按位操作判断奇偶if ~a1 and ~b1:return 2*gcd(a1,b1)elif ~a1 and b1:return gcd(a1,b)elif a1 and ~b1:return gcd(a,b1)else:return gcd(b, a-b)return gcd(BigNum, SmallNum)
