力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：解码异或后的排列
试题要求如下：
回答（C语言）：
/** * 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缩小范围。
回答（C语言）：
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题：数组中两个数的最大异或值
试题要求如下：
解题思路：
回答（C语言）：
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题：二叉树的中序遍历
试题要求如下：
解题思路：
二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
回答（C语言）：
/** * 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返回即可。
回答（C语言）：
/** * 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题：第三大的数
试题要求如下：
回答（C语言）：
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题：二叉树的后序遍历
试题要求如下：
回答（C语言）：
/** * 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 叉树的最大深度
试题要求如下：
回答（C语言）：
/** * 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题：字符串中的单词数
试题要求如下：
解题思路：
判定一个单词结束：当前字符非空格且下一字符为空格或结束符。
回答（C语言）：
int countSegments(char * s){ int cnt = 0; while (*s) { if (*s != ' ' && (*(s + 1) == ' ' || *(s + 1) == '\0')) cnt++; s++; } return cnt; }
运行效率如下所示：
