The requirements are as follows:

Answer (C language) :

/** * 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;
}
Copy the code

The operating efficiency is as follows:

Question 2:Different binary search trees

The requirements are as follows:

Answer:

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];
}
Copy the code

The operating efficiency is as follows:

Question 3:Perfect for

The requirements are as follows:

Answer:

I * I <=num; I * I <=num;

Answer (C language) :

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;
}
Copy the code

The operating efficiency is as follows:

Question 4:The maximum xOR value of two numbers in an array

The requirements are as follows:

Answer:

Answer (C language) :

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;
        // Put all pre^k(a_j) in the hash table
        for (int i = 0; i < numsSize; i++) {
            // If you want to keep only the bits from the highest bit to the KTH bit
            // Just move it k bits to the right
            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); }}// Currently x contains bits from the highest bits up to the k+1 bits
        // We set the KTH binary position of x to 1, i.e., x = x*2+1
        int x_next = x * 2 + 1;
        bool found = false;

        / / the enumeration 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 {
            // If no a_i and a_j satisfy the equation, then the KTH bit of x must be 0
            // this is x = x*2
            x = x_next - 1; }}return x;
}
Copy the code

The operating efficiency is as follows:

Question 5:Middle order traversal of binary trees

The requirements are as follows:

Answer:

Middle order traversal of binary trees: traversal of the tree in the same way that we visit the left subtree — root node — right subtree, and traversal of the left or right subtree in the same way until we have traversed the entire tree. Therefore, the whole traversal process naturally has the nature of recursion, we can directly use recursive function to simulate this process.

Answer (C language) :

/** * 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;
}
Copy the code

The operating efficiency is as follows:

Question 6:Guess the number size

The requirements are as follows:

Answer:

Enter mid into guess function and adjust the search boundary according to the return value. I used [left, mid] and [mid+1, right] here. Return mid when hit.

Answer (C language) :

/** * 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;
}
Copy the code

The operating efficiency is as follows:

Question 7:The third largest number

The requirements are as follows:

Answer (C language) :

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++) {
        /* Find the first number that differs from tmp1 and store it in tmp2; * Then find numbers different from TMP1 and store them in Tmp3; * if (nums[I]! = tmp1 && tmp1 == tmp2) { tmp2 = nums[i]; } else { tmp3 = nums[i]; } * When nums[I] is equal to tmp1, there is no need to judge, * but the above code still executes tmp3 = nums[I], which results in an error. * /
        if(nums[i] ! = tmp1) {if(tmp1 == tmp2) {
                tmp2 = nums[i];
            } else{ tmp3 = nums[i]; }}/* Compare the current number with first, second, third; * Third becomes second, second becomes first, and first becomes the current; * First > current number > second: third becomes second, second becomes the current number; * second > current number > third: third becomes the current number; * if the current value == first, second, and third, the value does not need to be updated. */
        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 and tmp2 equals the value comparison whether tmp3 respectively * if have equal TMP values, show that there are only two new number in the array, returns the first * * here or return to the third tmp3 must be compared with the other two, because tmp3 is the last change, * if tmp3 also changed, That means there are three different values. * /
    if(tmp1 == tmp3 || tmp2 == tmp3) {
        return first;
    } else {
        returnthird; }}Copy the code

The operating efficiency is as follows:

Question 8:Backward traversal of a binary tree

The requirements are as follows:

Answer (C language) :

/** * 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;
}
Copy the code

The operating efficiency is as follows:

Question 9:N The maximum depth of a fork tree

The requirements are as follows:

Answer (C language) :

/** * 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) { // Find the maximum depth of the subtreem = c; }}returnd + m; }}Copy the code

The operating efficiency is as follows:

Question 10:Number of words in a string

The requirements are as follows:

Answer:

Determines the end of a word: the current character is not a space and the next character is a space or an end character.

Answer (C language) :

int countSegments(char * s){
    int cnt = 0;

    while (*s) {
        if(*s ! =' ' && (*(s + 1) = =' ' || *(s + 1) = ='\ 0'))
            cnt++;
        s++;
    }
    return cnt;
}
Copy the code

The operating efficiency is as follows: