力扣(LeetCode)刷题，简单+中等题(第35期)

偏执的太偏执、 2023-01-20 02:57 133阅读 0赞

力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。

# 第1题：[解码异或后的排列][Link 1] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70][]

**回答（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;
    }

**运行效率如下所示：**

![20210511101238171.png][]

--------------------

# 第2题：[不同的二叉搜索树][Link 2] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 1][]

**解题思路：**

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];
    }

**运行效率如下所示：**

![20210512094606354.png][]

--------------------

# 第3题：[完美数][Link 3] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 2][]

**解题思路：**

本题思路就是简单的将因子相加，但是注意循环变量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;
    }

**运行效率如下所示：**

![20210514095331223.png][]

--------------------

# 第4题：[数组中两个数的最大异或值][Link 4] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 3][]

**解题思路：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 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;
    }

**运行效率如下所示：**

![20210516122745228.png][]

--------------------

# 第5题：[二叉树的中序遍历][Link 5] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 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;
    }

**运行效率如下所示：**

![20210516123909142.png][]

--------------------

# 第6题：[猜数字大小][Link 6] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 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;
    }

**运行效率如下所示：**

![20210516143223643.png][]

--------------------

# 第7题：[第三大的数][Link 7] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 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;
        }
    }

**运行效率如下所示：**

![20210516151120941.png][]

--------------------

# 第8题：[二叉树的后序遍历][Link 8] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 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;
    }

**运行效率如下所示：**

![20210516154741259.png][]

--------------------

# 第9题：[N 叉树的最大深度][N] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 9][]

**回答（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;
    	}
    }

**运行效率如下所示：**

![20210516155352435.png][]

--------------------

# 第10题：[字符串中的单词数][Link 9] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 10][]

**解题思路：**

判定一个单词结束：当前字符非空格且下一字符为空格或结束符。

**回答（C语言）：**

int countSegments(char * s){
        int cnt = 0;
    
        while (*s) {
            if (*s != ' ' && (*(s + 1) == ' ' || *(s + 1) == '\0'))
                cnt++;
            s++;
        }
        return cnt;
    }

**运行效率如下所示：**

![20210516160010674.png][]

[Link 1]: https://leetcode-cn.com/problems/decode-xored-permutation/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70]: /images/20221021/4f9ca2eeb7ea44358d93a108af9698d5.png
[20210511101238171.png]: /images/20221021/5b5fae212c6b4259ac8f6e98974f2964.png
[Link 2]: https://leetcode-cn.com/problems/unique-binary-search-trees/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 1]: /images/20221021/229e6a2b43844e9ea8112227ae17079f.png
[20210512094606354.png]: /images/20221021/87bc0d13ced74d2c83e89316c274e250.png
[Link 3]: https://leetcode-cn.com/problems/perfect-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 2]: /images/20221021/180a118c99354d9ea3b2849668f9b03f.png
[20210514095331223.png]: /images/20221021/07197fd65a5049bbbdcf1ac648a907d6.png
[Link 4]: https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 3]: /images/20221021/991915d93e4949039cf387be6a7e3a84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 4]: /images/20221021/d544f7b567324d62ac6fafe299f1c07e.png
[20210516122745228.png]: /images/20221021/e724ac82a8044486a029a40ca8715d68.png
[Link 5]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 5]: /images/20221021/ab949db03c2b4cfcbef0cdb918641490.png
[20210516123909142.png]: /images/20221021/082f01b185aa46d2be11666dff4913d4.png
[Link 6]: https://leetcode-cn.com/problems/guess-number-higher-or-lower/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 6]: /images/20221021/00164a4cf3e04a0bb961de6451d04b2e.png
[20210516143223643.png]: /images/20221021/a587ec2783bc4f24850c57e9f77a95ae.png
[Link 7]: https://leetcode-cn.com/problems/third-maximum-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 7]: /images/20221021/d1ea1ac52c704c208d85283531e32515.png
[20210516151120941.png]: /images/20221021/7cfef27a282a468686164671e7719387.png
[Link 8]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 8]: /images/20221021/59f681377d0e480ca9d1ccbf1fb32f51.png
[20210516154741259.png]: /images/20221021/aa8812b14e704899aa31dd07415f7a42.png
[N]: https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 9]: /images/20221021/c108406e290b4ac3b45f169508c244d6.png
[20210516155352435.png]: /images/20221021/6d795b50b9af46f9846480b94e863b29.png
[Link 9]: https://leetcode-cn.com/problems/number-of-segments-in-a-string/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 10]: /images/20221021/db7996a438c249bd9f9bf2a7ca16b787.png
[20210516160010674.png]: /images/20221021/ecac0bec335b4bc68ba19eccff0aafed.png