前言
文章出自專欄 ：《演算法零基礎100講》第13講
目錄
- 前言
- LeetCode 1979.找出陣列的最大公約數
- 分析
- 代碼實作
- LeetCode1819. 序列中不同最大公約數的數目
- 分析
- 代碼
LeetCode 1979.找出陣列的最大公約數
原題鏈接：找出陣列最大公約數
分析
題目給出一個陣列，求最大和最小值的最大公約數，
那首先要找到陣列中的最大值和最小值，
我的方法：
1.先利用快排對陣列排序，排完序第一個和最后一個數字就是最小值和最大值，
2. 利用輾轉相除法求這兩個數的最大公約數，
代碼實作
//輾轉相除法
//函式實作就是遞回形式
int Divisor(int a, int b)
{
return !b ? a : Divisor(b, a % b);
}
int mycmp(const void* p1, const void* p2)
{
const int* a = (const int*)p1;
const int* b = (const int*)p2;
return *a - *b;
}
int findGCD(int* nums, int numsSize)
{
//快排
qsort(nums, numsSize, sizeof(int), mycmp);
int min = nums[0];
int max = nums[numsSize - 1];
return Divisor(min, max);
}
LeetCode1819. 序列中不同最大公約數的數目
原題鏈接 ：1819. 序列中不同最大公約數的數目
分析
根據題意就要知道 需要列舉所有可能的最大公約數 ，若判斷 i 是不是某個子序列的最大公約數，就需要判斷陣列中存在的值與 i，2i, 3i 這些資料進行gcd判斷，若最后的最大公約數就是i， 那就記錄一次，
代碼
#define CAPACITY 200001
int Exist[CAPACITY];
//輾轉相除， 遞回方法求最大公約數
int gcd(int a, int b)
{
return !b ? a : gcd(b, a % b);
}
//比較兩個數中的最大值
int Max_Int(int a, int b)
{
return a > b ? a : b;
}
int countDifferentSubsequenceGCDs(int* nums, int numsSize)
{
//判空
if (NULL == nums) return 0;
//將陣列資料置為0
memset(Exist, 0, sizeof(Exist));
int max = 0, ans = 0;
//標記題目給出的陣列中的值，并且找出最大值
for (int i = 0; i < numsSize; ++i)
{
Exist[nums[i]] = 1;
max = Max_Int(max, nums[i]);
}
//列舉所有可能存在的最大公約數
for (int i = 1; i <= max; ++i)
{
int tmp = 0;
for (int j = i; j <= max; j += i)
{
if (Exist[j] != 0)
{
tmp = gcd(tmp, j);
}
}
//如果這個最大公約數等于i，就記錄一次
if (tmp == i)
{
ans++;
}
}
return ans;
}
感謝大家觀看~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/345668.html
標籤：其他