力扣(LeetCode)定期刷題，每期10道題，業務繁重的同志可以看看我分享的思路，不是最高效解決方案，隻求互相提升。
第1題：解碼異或後的排列
試題要求如下：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* decode(int* encoded, int encodedSize, int* returnSize) {
int n = encodedSize + 1;
int total = 0;
for (int i = 1; i <= n; i++) {
total ^= i;
}
int odd = 0;
for (int i = 1; i < n - 1; i += 2) {
odd ^= encoded[i];
}
int* perm = malloc(sizeof(int) * n);
*returnSize = n;
perm[0] = total ^ odd;
for (int i = 0; i < n - 1; i++) {
perm[i + 1] = perm[i] ^ encoded[i];
}
return perm;
} 運作效率如下所示：
第2題：不同的二叉搜尋樹
解題思路：
int numTrees(int n) {
int G[n + 1];
memset(G, 0, sizeof(G));
G[0] = G[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
} 第3題：完美數
本題思路就是簡單的将因子相加，但是注意循環變量i不能到num，是以用i*i<=num縮小範圍。
bool checkPerfectNumber(int num){
int count=0;
if(num==1)return false;
for(int i=2;i*i<=num;i++){
if(num%i==0)
count+=i+num/i;
}
return count+1==num?true:false;
} 第4題：數組中兩個數的最大異或值
const int HIGH_BIT = 30;
struct HashTable {
int key;
UT_hash_handle hh;
};
int findMaximumXOR(int* nums, int numsSize) {
int x = 0;
for (int k = HIGH_BIT; k >= 0; --k) {
struct HashTable* hashTable = NULL;
// 将所有的 pre^k(a_j) 放入哈希表中
for (int i = 0; i < numsSize; i++) {
// 如果隻想保留從最高位開始到第 k 個二進制位為止的部分
// 隻需将其右移 k 位
int x = nums[i] >> k;
struct HashTable* tmp;
HASH_FIND_INT(hashTable, &x, tmp);
if (tmp == NULL) {
tmp = malloc(sizeof(struct HashTable));
tmp->key = x;
HASH_ADD_INT(hashTable, key, tmp);
}
}
// 目前 x 包含從最高位開始到第 k+1 個二進制位為止的部分
// 我們将 x 的第 k 個二進制位置為 1，即為 x = x*2+1
int x_next = x * 2 + 1;
bool found = false;
// 枚舉 i
for (int i = 0; i < numsSize; i++) {
int x = x_next ^ (nums[i] >> k);
struct HashTable* tmp;
HASH_FIND_INT(hashTable, &x, tmp);
if (tmp != NULL) {
found = true;
break;
}
}
if (found) {
x = x_next;
} else {
// 如果沒有找到滿足等式的 a_i 和 a_j，那麼 x 的第 k 個二進制位隻能為 0
// 即為 x = x*2
x = x_next - 1;
}
}
return x;
} 第5題：二叉樹的中序周遊
二叉樹的中序周遊：按照通路左子樹——根節點——右子樹的方式周遊這棵樹，而在通路左子樹或者右子樹的時候我們按照同樣的方式周遊，直到周遊完整棵樹。是以整個周遊過程天然具有遞歸的性質，我們可以直接用遞歸函數來模拟這一過程。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void inorder(struct TreeNode* root, int* res, int* resSize) {
if (!root) {
return;
}
inorder(root->left, res, resSize);
res[(*resSize)++] = root->val;
inorder(root->right, res, resSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int* res = malloc(sizeof(int) * 501);
*returnSize = 0;
inorder(root, res, returnSize);
return res;
} 第6題：猜數字大小
此題使用二分查找，将mid輸入guess函數，根據傳回值調整查找邊界，我這裡用的是【left，mid】和【mid+1，right】，命中時将mid傳回即可。
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* int guess(int num);
*/
int guessNumber(int n){
int left=1;
int right=n;
while(left<right){
int mid= left+(right-left)/2;
if(guess(mid)<0)right=mid;
else if(guess(mid)>0) left=mid+1;
else return mid;
}return left;
} 第7題：第三大的數
int thirdMax(int* nums, int numsSize){
int i;
int first = INT_MIN, second = INT_MIN, third = INT_MIN;
int tmp1 = nums[0], tmp2 = nums[0], tmp3 = nums[0];
for(i = 0; i < numsSize; i++) {
/* 先找到第一個與tmp1不同的數，存入tmp2；
* 之後找到與tmp1不同的數，都存入tmp3中;
* 這裡必須将tmp1 == tmp2的判斷放在第二層，若是放在第一層邏輯出現錯誤
* if (nums[i] != tmp1 && tmp1 == tmp2) {
tmp2 = nums[i];
} else {
tmp3 = nums[i];
}
* 當nums[i]等于tmp1時，就不需要判斷了，
* 但是上面的代碼還是會執行tmp3 = nums[i]，這就導緻錯誤。
*/
if(nums[i] != tmp1) {
if(tmp1 == tmp2) {
tmp2 = nums[i];
} else {
tmp3 = nums[i];
}
}
/* 比較目前的數與first、second、third的大小;
* 目前數 > first時：third變為second、second變為first、first變為目前數;
* first > 目前數 > second時：third變為second、second變為目前數;
* second > 目前數 > third時：third變為目前數;
* 其中目前數 == first、second、third時不需要更新三者的值.
*/
if(nums[i] > first) {
third = second;
second = first;
first = nums[i];
} else if(nums[i] < first && nums[i] > second) {
third = second;
second = nums[i];
} else if(nums[i] < second && nums[i] > third) {
third = nums[i];
}
}
/* tmp1和tmp2分别與tmp3的值比較是否相等
* 若有相等的tmp值,表明數組中隻有兩種新的數，傳回first
* 否則傳回third
* 這裡必須将tmp3與其他兩個相比較，因為tmp3是最後改變的，
* 若tmp3也改變了，就說明有三個不同的值。
*/
if(tmp1 == tmp3 || tmp2 == tmp3) {
return first;
} else {
return third;
}
} 第8題：二叉樹的後序周遊
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void postorder(struct TreeNode *root, int *res, int *resSize) {
if (root == NULL) {
return;
}
postorder(root->left, res, resSize);
postorder(root->right, res, resSize);
res[(*resSize)++] = root->val;
}
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = malloc(sizeof(int) * 2001);
*returnSize = 0;
postorder(root, res, returnSize);
return res;
} 第9題：N 叉樹的最大深度
/**
* Definition for a Node.
* struct Node {
* int val;
* int numChildren;
* struct Node** children;
* };
*/
int maxDepth(struct Node* root)
{
if (root == NULL)
{
return 0;
}
else {
int d = 1, m = 0;
for (int i = 0; i < root->numChildren; i++)
{
int c = maxDepth(root->children[i]);
if (m < c) { // 找子樹的最大深度
m = c;
}
}
return d + m;
}
} 第10題：字元串中的單詞數
判定一個單詞結束：目前字元非空格且下一字元為空格或結束符。
int countSegments(char * s){
int cnt = 0;
while (*s) {
if (*s != ' ' && (*(s + 1) == ' ' || *(s + 1) == '\0'))
cnt++;
s++;
}
return cnt;
}