当前位置:网站首页>力扣(LeetCode)刷题,简单题(第24期)

力扣(LeetCode)刷题,简单题(第24期)

2020-12-06 11:08:14 不脱发的程序猿

目录

第1题:两个列表的最小索引总和

第2题:反转字符串中的元音字母

第3题:整数反转

第4题:将有序数组转换为二叉搜索树

第5题:第N个泰波那契数

第6题:数组序号转换

第7题:质数排序

第8题:日期之间隔几天

第9题:—年中的第几天

第10题:复写零


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

第1题:两个列表的最小索引总和

试题要求如下:

 

解答思路:

哎,暴力破解。

回答(C语言):

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** findRestaurant(char ** list1, int list1Size, char ** list2, int list2Size, int* returnSize){
    int minNum = list1Size > list2Size ? list2Size : list1Size;
    char **res = (char **)malloc(sizeof(char *) * minNum);
    int index = INT_MAX;
    int num = 0;

    for (int i = 0; i < list1Size; i++){
        for (int j = 0; j < list2Size; j++) {
            if (strcmp(list1[i], list2[j]) == 0){
                if (i + j < index){
                    index = i + j;
                    res[0] = list1[i];
                    num = 1;
                }
                else if (i + j == index){
                    res[num] = list1[i];
                    num++;
                }
            }
        }
    }

    *returnSize = num;
    return res;
}

运行效率如下所示:


第2题:反转字符串中的元音字母

试题要求如下:

解答思路:

元音字母:a[ei]、e[i:]、i[ ai]、o[eu]、u[ju:]。

回答(C语言):

bool isAEIOU(char c){
    return (c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='A'||c=='E'||c=='I'||c=='O'||c=='U');
}

char * reverseVowels(char * s){
    int len = strlen(s);
    if(len<2) return s;
    
    int head=0, tail=len-1;

    while(tail>head){
        if(isAEIOU(s[head])&&isAEIOU(s[tail])){
            char temp;
            temp = s[head];
            s[head] = s[tail];
            s[tail] = temp;
            head++, tail--;
        }
        else{
            if(!isAEIOU(s[head]))head++;
            if(!isAEIOU(s[tail]))tail--;
        }
    } 
    
    return s;
}

运行效率如下所示:


第3题:整数反转

试题要求如下:

回答(C语言):

#define isOverLength 0

int reverse(int x){
    long lRet = 0;
    while(0 != x){
        lRet = lRet * 10 + x % 10;
        x = x / 10;
    }

    if((int)lRet != lRet){
        return isOverLength;
    }

    return (int)lRet;
}

运行效率如下所示:


第4题:将有序数组转换为二叉搜索树

试题要求如下:

解答思路:

递归法:定位根节点、根节点左边作为左支递归处理、根节点右边作为右支递归处理。

回答(C语言):

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

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    int     iRoot       = 0;
    struct TreeNode*    pCurNode    = NULL;

    //1,结束条件
    if((NULL == nums) || (0 == numsSize)) return NULL;

    //2,初始化
    pCurNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

    //3,定位根节点
    iRoot = numsSize / 2;

    //4,递归处理左右支
    pCurNode->val = nums[iRoot];
    pCurNode->left = sortedArrayToBST(&nums[0], iRoot);
    pCurNode->right = sortedArrayToBST(&nums[iRoot + 1], numsSize - iRoot - 1);
    return pCurNode;
}

运行效率如下所示:


第5题:第N个泰波那契数

试题要求如下:

回答(C语言):

int tribonacci(int n){
    if(n==0) return 0;
    if(n==1||n==2) return 1;

    int dp[n+1];
    
    dp[0]=0;
    dp[1]=1;
    dp[2]=1;

    for(int i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
    }
    
    return dp[n];
}

运行效率如下所示:


第6题:数组序号转换

试题要求如下:

解答思路:

先用二维数组把arr中的数值和下标存储起来,然后对这个二维数组的第1维排序,从前往后,直接修改存储的下标对应的数值即可。

回答(C语言):

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void *a, const void *b)
{
    return ((int *) a)[0] - ((int *) b)[0];
}

int *arrayRankTransform(int *arr, int arrSize, int *returnSize)
{
    *returnSize = arrSize;

    if (arrSize == 0)
    {
        return arr;
    } else if (arrSize == 1)
    {
        arr[0] = 1;
        return arr;
    }
    int dis[arrSize][2];
    int i, k;

    for (i = 0; i < arrSize; i++)
    {
        dis[i][0] = arr[i];
        dis[i][1] = i;
    }

    qsort(dis, arrSize, sizeof(dis[0]), cmp);

    k = 1;
    arr[dis[0][1]] = 1;
    for (i = 1; i < arrSize; i++)
    {
        if (dis[i][0] > dis[i - 1][0])
        {
            k++;

        }
        arr[dis[i][1]] = k;
    }
    return arr;
}

运行效率如下所示:


第7题:质数排序

试题要求如下:

解答思路:

质数有m个,非质数有n个,结果为m!*n!。

注意:计算阶乘int 型会溢出 用long int;不要用科学计数法表示。

回答(C语言):

const long long int m=1000000007;

int prime(int n){
    if(n==1)return 0;

    for(int i=2;i<(n/2)+1;i++)
        if(n%i==0)return 0;

    return 1;
}
int numPrimeArrangements(int n){
        int i,p=0,q;
        long long int jq=1,jp=1;

        for(i=1;i<=n;i++) if(prime(i)==1)p++;//i是质数

        q=n-p;

        for(i=1;i<=q;i++) jq=(jq*i)%m;
        for(i=1;i<=p;i++)jp=(jp*i)%m;

        return (jp*jq)%m;
}

运行效率如下所示:


第8题:日期之间隔几天

试题要求如下:

回答(C语言):

int isleap(int y){
    return y%4==0 && y%100!=0 || y%400==0;
}

int tab[]={-1,31,28,31,30,31,30,31,31,30,31,30,31};

int getdate(char *date){ 
    int y,m,d,r=0;
    sscanf(date, "%d-%d-%d", &y,&m,&d);
    for(int i=1970; i<y;i++)
        if(isleap(i)) r+= 366;
        else r+= 365;
    for(int i=1;i<m;i++){
        r+=tab[i];
        if(i==2 && isleap(y)) r+=1;
    }
    r+=d;
    
    return r;
}

#define intfabs(x) ((x)<0?-(x):(x))

int daysBetweenDates(char * date1, char * date2){
    return intfabs(getdate(date1)-getdate(date2) );
}

运行效率如下所示:


第9题:—年中的第几天

试题要求如下:

回答(C语言):

int dayOfYear(char * date){
    int year=0,month=0,day=0,result=0,i;
    int days[12]={31,28,31,30,31,30,31,31,30,31,30,31};

    for(i=0;i<4;i++) year=year*10+date[i]-48;
    for(i=5;i<7;i++) month=month*10+date[i]-48;
    for(i=8;i<10;i++) day=day*10+date[i]-48;

    if(year%4==0&&year%100!=0||year%400==0) days[1]=29;
    for(i=0;i<month-1;i++) result=result+days[i];
    result=result+day;
    
    return result;
}

运行效率如下所示:


第10题:复写零

试题要求如下:

回答(C语言):

void duplicateZeros(int* arr, int arrSize){
     for(int i = 0;i < arrSize;i++){
         if(arr[i] == 0){
            for(int j = arrSize-2;j >= i;j--)
                arr[j+1] = arr[j];
            i++;
         }
     }  
}

运行效率如下所示:

版权声明
本文为[不脱发的程序猿]所创,转载请带上原文链接,感谢
http://handsome-man.blog.csdn.net/article/details/108375279