力扣(LeetCode)刷题，简单+中等题(第35期)
【摘要】 力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：解码异或后的排列
试题要求如下：
回答（C语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */int* decode(in...
力扣(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;
-
}
运行效率如下所示：
文章来源: handsome-man.blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：handsome-man.blog.csdn.net/article/details/116640463
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）