1 最大公約數

歐幾里得算法：兩個整數的最大公約數等于其中較小的那個數和兩數相除余數的最大公約數。

gcd(a,b)=gcd(b,a%b);	/* a>b*/

具體代碼實現如下：

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}

2 最小公約數

設a,b的最小公約數為lcm(a,b)。有定理：

lcm(a,b)*gcd(a,b)=a*b);

具體代碼實現：

int lcm(int a, int b) {return a * b / gcd(a, b);
}

3 進制轉換

比如將十進制num10轉為七進制num7。

如果是負數，我們可以先將其轉為正數，在前面添加個’-'號。
代碼：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>char * convertToBase7(int num){if(num == 0){return "0";}char *str = (char*)malloc(sizeof(char)*32);memset(str,0,sizeof(str));int index=30;int negative = 0;if(num<0){negative = 1;num = abs(num);}while(num!=0){str[index--] = num % 7+'0';//num = num - str[index];num = num / 7;//index++;}if(negative==1){str[index--]='-';//return str;}str[31]='\0';return str+index+1;
}int main(void)
{//int nums[]={10,9,2,5,3,7,101,18};//int count = countPrimes(2);printf("count = %s\n",convertToBase7(14));return 0;
}

4 階乘

統計階乘尾部0的個數

實現：

int trailingZeroes(int n){return n==0?0:n/5+trailingZeroes(n/5);
}

如果統計的是 N! 的二進制表示中最低位 1 的位置，只要統計有多少個 2 即可

5 字符串加法減法

二進制加法

給你兩個二進制字符串，返回它們的和（用二進制表示）。
輸入為 非空 字符串且只包含數字 1 和 0。
輸入: a = “11”, b = “1”
輸出: “100”

/* 將一個字符串反轉 */
void reserve(char* s) {int len = strlen(s);for (int i = 0; i < len / 2; i++) {char t = s[i];s[i] = s[len - i - 1], s[len - i - 1] = t;}
}char* addBinary(char* a, char* b) {/* 將兩個字符串反轉 */reserve(a);reserve(b);/* 獲取兩個字符串長度 */int len_a = strlen(a), len_b = strlen(b);int n = fmax(len_a, len_b);int carry = 0, len = 0;/* 結果的長度是a、b最大長度加2 */char* ans = (char*)malloc(sizeof(char) * (n + 2));for (int i = 0; i < n; ++i) {/* 如果i小于len_a，表示字符串a還有元素，如果有元素，是1則返回1，是0則返回0 */carry += i < len_a ? (a[i] == '1') : 0;carry += i < len_b ? (b[i] == '1') : 0;ans[len++] = carry % 2 + '0';/* carry進位處理 */carry /= 2;}/* 最后還有進位 */if (carry) {ans[len++] = '1';}ans[len] = '\0';/* 反轉 */reserve(ans);return ans;
}

6 多數投票問題

數組中出現次數多于n/2的元素

給定一個大小為 n 的數組，找到其中的多數元素。多數元素是指在數組中出現次數 大于 ? n/2 ? 的元素。
你可以假設數組是非空的，并且給定的數組總是存在多數元素。

因為找的元素次數大于? n/2 ? ，所以我們只需將數組排序，返回中間值即可：

int cmp(void *a,void *b)
{return *(int *)a-*(int *)b;
}
int majorityElement(int* nums, int numsSize){qsort(nums,numsSize,sizeof(int),cmp);return nums[numsSize/2];
}

7 相遇問題

改變數組元素使所有元素都相同

給定一個非空整數數組，找到使所有數組元素相等所需的最小移動數，其中每次移動可將選定的一個元素加1或減1。 您可以假設數組的長度最多為10000。
輸入:
[1,2,3]
輸出:
2
說明：
只有兩個動作是必要的（記得每一步僅可使其中一個元素加1或減1）：
[1,2,3] => [2,2,3] => [2,2,2]

這是個典型的相遇問題，移動距離最小的方式是所有元素都移動到中位數。理由如下：

設 m 為中位數。a 和 b 是 m 兩邊的兩個元素，且 b > a。要使 a 和 b 相等，它們總共移動的次數為 b - a，這個值等于 (b - m) + (m - a)，也就是把這兩個數移動到中位數的移動次數。

設數組長度為 N，則可以找到 N/2 對 a 和 b 的組合，使它們都移動到 m 的位置。

思路：先排序，然后計算移到中位數的位置所需的移動次數

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>int cmp(void *a,void *b)
{return *(int *)a-*(int *)b;
}int minMoves2(int* nums, int numsSize){qsort(nums,numsSize,sizeof(int),cmp);int left=0,right=numsSize-1;int count=0;while(left<=right){count +=nums[right]-nums[left];left++;right--;}return count;
}
int main(void)
{int nums[]={1,2,3};//int count = trailingZeroes(10);printf("count = %d\n",minMoves2(nums,3));return 0;
}