[数据结构与算法]力扣算法题入门--持续更新

1:

这里核心的就是插入元素使被插元素及其以后元素往后移,
再就是如何利用循环终止后移

int* createTargetArray(int* nums, int numsSize, int* index, int indexSize, int* returnSize){
    int i,j,ins,num,len=0;
    int *ret = (int *)malloc(sizeof(int)*numsSize);
    for(i=0;i<numsSize;++i)
    {
        ins=index[i];
        num=nums[i];
        for(j=len;j>ins;--j)//当插入位置在数组中已有元素时
        {
            ret[j]=ret[j-1];//先把前一个移到后一个
        }
        ret[ins]=num;//再把空位置重新赋值
        ++len;
        
    }
    *returnSize = len;
    return ret;
}

2:

这道题核心是将数组分奇偶排列,奇为x,偶为y,所以咱们可以对下标取余就完成这道题;或者用位运算,奇数位1是1,偶数位1是0来选择.

int* shuffle(int* nums, int numsSize, int n, int* returnSize){             // (2)
    int i;
    int *ret = (int *)malloc( sizeof(int) * numsSize );                    // (3)
    for(i = 0; i < numsSize; ++i) {                                        // (4)
        if(i & 1) {//位运算,为1则上,0则else
            ret[i] = nums[n + i/2];
        }else {
            ret[i] = nums[(i+1)/2];
        }
    }
    *returnSize = numsSize;                                                // (5)
    return ret;                                                            // (6)
}

3:

这道题的核心是使偶数在前奇数在后,由上面提到的位运算和一个排序算法(先让偶数放在前面,再让奇数放在后面).

int fp(int x) {
    return x & 1;#位运算
}

int cmp(const void *a, const void *b) {
    return fp(*(int *)a) - fp(*(int *)b);#按偶数在前,奇数在后排序
}

int* sortArrayByParity(int* nums, int numsSize, int* returnSize){
    int i;
    int *ret = (int *)malloc( sizeof(int) * numsSize );#开辟一个新数组  
    for(i = 0; i < numsSize; ++i) {
        ret[i] = nums[i];                                
    }
    qsort(ret, numsSize, sizeof(int), cmp);              
    *returnSize = numsSize; #返回数组长度                             
    return ret;
}

4:

这道题的核心是将数先转为时间形式,再全部转为分钟从小到大排序并求相邻两数最小值(虽然题上说任意最小值,可排序完之后就是最小值),当然还得考虑时间差一天的情况,那就加上1440(24*60)

int min(int a,int b)
{
    return a < b ? a : b ;//返回最小值
}
int findMinDifference(char ** timePoints, int timePointsSize){
    int *ret = (int *)malloc(sizeof(int)*timePointsSize);
    int i,a,b;
    for(i=0;i<timePointsSize;++i)
    {
        sscanf(timePoints[i],"%d:%d",&a,&b);//将字符串格式化成对应整数
        ret[i]=a*60 + b;//将时间换为分钟形式
    }
    qsort(ret,timePointsSize,sizeof(int),cmp);//排序
    int j,minus=1440;//这里的1440=24*60,就是时间差最大为1440
    for(j=1;j<timePointsSize;++j)
    {
        minus=min(minus,ret[j]-ret[j-1]);//调用min函数选择相邻两数差最小值
    }
    minus = min(minus,ret[0]-ret[timePointsSize-1]+1440);//这一步是考虑到时间循环时的时间差一天
    return minus;

}

5:

这道题的核心就是分情况讨论坐船,看代码注释就一目了然啦~

int cmp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}
int numRescueBoats(int* people, int peopleSize, int limit){
    qsort(people,peopleSize,sizeof(int),cmp);//先排序
    int l=0,r=peopleSize-1,count=0;//利用快排算法思想,定义左和右哨点
    while(l<=r)
    {
        if(people[l]+people[r]>limit)//让最重的与最轻的坐一条船,如果超重的话就让重的那个坐一条船
        {
            count++;//计数
            r--;//左移
        }
        else if (l==r)//左等于右,只剩一个人时直接加一条船
        {
            count++;
            break;
        }
        else
        {
            count++;//满足两人一条船就l右移,r左移
            l++;
            r--;
        }
    }
    return count;
}