directory

Problem 1: the KTH largest element in an array

Problem 2: String multiplication

Problem 3: Longest repeating subarray

Problem 4: valid perfect squares

Problem 5: Minimum time to access all points

Problem 6: Sum of paths

Problem 7: Diving board

Problem 8: Decompress the code list

Problem 9: Hamming distance

Problem 10: judge whether arithmetic series can be formed

LeetCode brushes the questions regularly, with 10 questions in each period. Comrades with heavy business can look at the ideas I share, which are not the most efficient solutions, but for mutual improvement.

Problem 1: the KTH largest element in an array

The requirements are as follows:

Answer (C language) :

int cmp(const void *a,const void*b)
{
    return* (int *)a > *(int *)b;
}
int findKthLargest(int* nums, int numsSize, int k){
    qsort(nums,numsSize,sizeof(int),cmp);
    return nums[numsSize-k];
}
Copy the code

The operating efficiency is as follows:

Problem 2: String multiplication

The requirements are as follows:

Answer:

See also: Lico official

Answer (C language) :

char * multiply(char * num1, char * num2)
{
    int length1 = strlen(num1);
    int length2 = strlen(num2);
    int totalLength = length1 + length2;    // Gets the total number of significant digits of the multiplied string
    
    int charIndex = 0;  // Define the responsible index field
    int valueIndex = 0;
    
    int *value = (int *)malloc(sizeof(int) * totalLength);
    memset(value, 0.sizeof(int) * totalLength);
    
    char *result = (char *)malloc(sizeof(char) * (totalLength + 1));
    
    for(int i = length1  - 1; i >= 0; i--)
    {
        for(int j = length2 - 1; j >= 0; j--)
        {
            value[i + j + 1] += (num1[i] - '0') * (num2[j] - '0'); }}for(int i= totalLength - 1; i > 0; i--)                 // Get the number above each position and process the carry
    {
        value[i - 1] += value[i] / 10;
        value[i] %= 10;
    }
    
    while(value[valueIndex] == 0 && valueIndex < totalLength - 1 ) 
    {
        valueIndex++;   // Ignore the extra zeros, but not the highest and only zeros
    }
    while(valueIndex < totalLength)
    {
        result[charIndex++] = value[valueIndex++] + '0';
    }
    
    result[charIndex] = '\ 0';   // Completes the terminator of the string by default
    
    return result; 
}
Copy the code

The operating efficiency is as follows:

Problem 3: Longest repeating subarray

The requirements are as follows:

Answer:

Dynamic programming.

Answer (C language) :

int findLength(int* A, int ASize, int* B, int BSize) {
    int dp[ASize + 1][BSize + 1];
    memset(dp, 0.sizeof(dp));
    int ans = 0;

    for (int i = ASize - 1; i >= 0; i--) {
        for (int j = BSize - 1; j >= 0; j--) {
            dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
            ans = fmax(ans, dp[i][j]); }}return ans;
}
Copy the code

The operating efficiency is as follows:

Problem 4: valid perfect squares

The requirements are as follows:

Answer:

Perfect square means multiplying yourself by an integer, such as 1*1, 2* 2,3 *3, etc., and so on. A number is called a perfect square if it can be expressed as the square of an integer.

Perfect squares can be found by summing up odd numbers starting from 1,

1 = 1;

4 = 1 + 3;

9 = 1 + 3 + 5;

16 = 1 + 3 + 5 + 7;

.

Answer (C language) :

bool isPerfectSquare(int num){
    if (num == 0) return false;

    int i = 1;

    while ( num > 0){
        num -= i;
        i += 2;
    }
    
    return num == 0 ? true : false;
}
Copy the code

The operating efficiency is as follows:

Problem 5: Minimum time to access all points

The requirements are as follows:

Answer:

Think of the problem as analyzing the distance between two points:

1. There is a distance between the x value and the y value

2. Because you can only walk vertically and horizontally or diagonally, the best way to walk is

(1) If the distance between x and Y is greater than that between two points, walk sideways until the distance between xy and y is equal

(2) If the y distance is greater than the X distance, walk vertically until the xy distance is equal

3, xy distance is equal, directly oblique walk, this distance is x or Y distance, directly add

Answer (C language) :

int minTimeToVisitAllPoints(int** points, int pointsSize, int* pointsColSize){
   int sum = 0;/ / the sum
   int a = 0,b = 0;// Two points x, y distance
   
   for(int i = 0; i < pointsSize- 1; i++){ a =abs(points[i][0]-points[i+1] [0]);
       b = abs(points[i][1]-points[i+1] [1]);
       sum += abs(a-b);
       if(a>b) sum += b;
       else sum += a;
   }

   *pointsColSize=sum;
   return sum;
}
Copy the code

The operating efficiency is as follows:

Problem 6: Sum of paths

The requirements are as follows:

Answer (C language) :

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; *}; * /

typedef struct TreeNode TN;
bool hasPathSum(struct TreeNode* root, int sum){
    if(root == NULL)
        return false;
    if(root->val == sum && root->left == NULL && root->right == NULL)
        return true;
    if(hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val))
        return true;
    return false;
}
Copy the code

The operating efficiency is as follows:

Problem 7: Diving board

The requirements are as follows:

Answer:

1, if k=0k=0, no diving board can be built, so return empty array.

2, if shorter and longer are equal, then the length of the diving board is unique, equal to the shorter* K.

Answer (C language) :

int* divingBoard(int shorter, int longer, int k, int* returnSize) {
    if (k == 0) {
        *returnSize = 0;
        return NULL;
    }

    if (shorter == longer) {
        int* p = (int*)malloc(sizeof(int));
        *p = shorter * k;
        *returnSize = 1;
        return p;
    }
    
    *returnSize = k + 1;
    int* lengths = (int*)malloc(sizeof(int) * (k + 1));
    for (int i = 0; i <= k; ++i) {
        lengths[i] = shorter * (k - i) + longer * i;
    }
    return lengths;
}
Copy the code

The operating efficiency is as follows:

Problem 8: Decompress the code list

The requirements are as follows:

Answer (C language) :

/** * Note: The returned array must be malloced, assume caller calls free(). */
int* decompressRLElist(int* nums, int numsSize, int* returnSize){
    int size=0;
    int *returned=calloc(5000.sizeof(int));

    for(int i = 0,k = 0; i < numsSize; i +=2){
        size=nums[i]+size;
        for(int j = 0; j < nums[i]; j++){ returned[k++]=nums[i+1];
        }
    }
    
    *returnSize=size;
    return returned;
}
Copy the code

The operating efficiency is as follows:

Problem 9: Hamming distance

The requirements are as follows:

Answer (C language) :

int hammingDistance(int x, int y){
    int cnt = 0, n = 32;

    while(n--){
        if((x & 1) ^ (y & 1))
            cnt++;
        x >>= 1;
        y >>= 1;
    }
    
    return cnt;
}
Copy the code

The operating efficiency is as follows:

Problem 10: judge whether arithmetic series can be formed

The requirements are as follows:

Answer (C language) :

int cmp(const void *a, const void *b)
{
    return* ((int*)a) - *((int*)b);
}

bool canMakeArithmeticProgression(int* arr, int arrSize){
    qsort(arr, arrSize, sizeof(int), cmp);

    int minus = arr[1] - arr[0];
    
    for (int i = 0; i < arrSize; i++) {
        if(arr[i] ! = (arr[0] + i * minus)) {
            return false; }}return true;
}
Copy the code

The operating efficiency is as follows: