力扣(LeetCode)刷题，简单题(第13期)

目录

第1题：字符的最短距离

第2题：棒球比赛

第3题：判定是否互为字符重排

第4题：岛屿的周长

第5题：两个数组的交集

第6题：计算质数

第7题：旋转数组

第8题：二叉树的层平均数

第9题：修建二叉搜索树

第10题：分糖果

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

第1题：字符的最短距离

试题要求如下：

解答思路：

从左向右遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 i - prev。

从右想做遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 prev - i。

这两个值取最小就是答案。

回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* shortestToChar(char * S, char C, int* returnSize){
    int tmp1,tmp2;
    int len = strlen(S);
    int* ret = (int *)malloc(len * sizeof(int));

    for(int i = 0; i < len; i++)
    {
        tmp1 = 0;
        for(int j = i; j >= 0; j--)
        {
            if (S[j] != C) {
                if (j == 0) {
                    tmp1 = len;
                } else {
                    tmp1++;
                }
            } else {
                break;
            }
        }

        tmp2 = 0;
        for(int j = i; j < len; j++)
        {
            if (S[j] != C) {
                if (j == len-1) {
                    tmp2 = len;
                } else {
                    tmp2++;
                }
            } else {
                break;
            }
        }

        ret[i] = tmp1 < tmp2 ? tmp1 : tmp2;
    }

    *returnSize = len;
    return ret;
}

运行效率如下所示：

第2题：棒球比赛

试题要求如下：

解答思路：

堆栈思想。

回答（C语言）：

int calPoints(char ** ops, int opsSize){
    int arr[1000]={0};
    int score = 0,i = 0,j = 0;

    while(i < opsSize){
        switch(ops[i][0]){
            case 'C':
                arr[j-1]=0;
                j-=2;
                break;

            case 'D':
                arr[j]=arr[j-1]*2;
                break;

            case '+':
                arr[j]=arr[j-1]+arr[j-2];
                break;

            default:
                //字符串类型转整数类型
                arr[j]=atoi(ops[i]);
                break;
        }

        j++;
        i++;
    }

    for(int i=0;ival;
    count[index]++;
    (*head) = fmax(*head, index);
    helper(root->left, sum, count, index+1, head);
    helper(root->right, sum, count, index+1, head);
 }

double* averageOfLevels(struct TreeNode* root, int* returnSize){
    int NUM = 10000;
    double* sum = (double*)calloc(NUM, sizeof(double));
    double* count = (double*)calloc(NUM, sizeof(double));

    int head = 0;
    helper(root, sum, count, 0, &head);
    double* ret = (double*)malloc((head+1)*sizeof(double));
    for(int i=0; ival < L)
    {
        return trimBST(root->right, L, R);
    }

    if (R < root->val)
    {
        return trimBST(root->left, L, R);
    }

    root->left = trimBST(root->left, L, R);
    root->right = trimBST(root->right, L, R);

    return root;
}

运行效率如下所示：

第10题：分糖果

试题要求如下：

回答（C语言）：

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

int distributeCandies(int* candies, int candiesSize){
    int cou = 0;

    qsort(candies, candiesSize, sizeof(int), cmpfunc);
    
    for(int i = 0,j = 1;i < candiesSize-1;i++,j = i+1){
        if(candies[i] != candies[j]){
            cou++;
        }
    }

    cou++;

    if(cou < candiesSize/2){
        return cou;
    }

    return candiesSize/2;
}

运行效率如下所示：