诺亚方舟——第六天

第六天!!!!
————————————————————————————————————————
学习内容:贪心算法
贪心算法的定义:不追求整体的最优,力求部部最优,这就是贪心
————————————————————————————————————————
课后习题:
1.力扣 1913.两个数对之间的最大乘积差
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int maxProductDifference(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    return nums[numsSize-1]*nums[numsSize-2]-nums[0]*nums[1];

}
2.力扣 976.三角形的最大周长
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int largestPerimeter(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i=numsSize-1;i>=2;i--)
    {
        if(nums[i]<nums[i-1]+nums[i-2])
            return nums[i]+nums[i-1]+nums[i-2];
    }
    return 0;
}
3.力扣 561.数组拆分 I
这道题真的要好好说说思路!!!
思路:
首先你要排序,你为什么要排序呢,是因为你很贪心,既然他不让你要数组中最大的元素,你就要第二大。
来个例子好理解一点,比如一个数组[1,3,2,4]—>[1,2,3,4] 你要这么看 [(1,2,3),4]你要不了4,你就要括号里最大的(贪心),
也就是3,接下来再进行[1,2],要1,就是排序后把它分成了相同的子问题,然后求解。
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int arrayPairSum(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    int sum=0;
    for(int i=0;i<numsSize;i+=2)
    {
        sum+=nums[i];
    }
    return sum;
}
4.力扣 881.救生艇
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;
    int ship=0;
    while(l<=r)
    {
        if(l==r)
        {
            ship++;
            break;
        }
        else if(people[l]+people[r]>limit)
        {
            ship++;
            r--;
        }
        else
        {
            l++;
            r--;
            ship++;
        }
    }
    return ship;

}
5.力扣 324.摆动排序 ll
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
void wiggleSort(int* nums, int numsSize){
    int *ret=(int *)malloc(sizeof(int)*numsSize);
    for(int i=0;i<numsSize;i++)
    {
        ret[i]=nums[i];
    }
    qsort(ret,numsSize,sizeof(int),cmp);
    int j=numsSize-1;
    for(int i=1;i<numsSize;i+=2)
    {
        nums[i]=ret[j--];
    } 
    for(int i=0;i<numsSize;i+=2)
    {
        nums[i]=ret[j--];
    }

}
6.力扣 455.分发饼干
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int findContentChildren(int* g, int gSize, int* s, int sSize){
    qsort(g,gSize,sizeof(int),cmp);
    qsort(s,sSize,sizeof(int),cmp);
    int i=0,j=0;
    int child=0;
    while(i<gSize&&j<sSize)
    {
        if(g[i]<=s[j++])
        {
            child++;
            i++;
        }

    }
    return child;
}
7.力扣 1827.最少操作使数组递增
执行时间(960ms)
int minOperations(int* nums, int numsSize){
    int count=0;
    for(int i=1;i<numsSize;)
    {
        if(nums[i-1]>=nums[i]){
            nums[i]++;
            count++;
        }
        else
            i++;
    }
    return count;

}

执行时间(12ms)
int minOperations(int* nums, int numsSize){
    int i;
    int ans = 0, pre = nums[0] + 1;
    for(i = 1; i < numsSize; ++i) {
        if(pre < nums[i]) {
            pre = nums[i] + 1;      // (1)
        }else {
            ans += pre - nums[i];   // (2)
            ++pre;
        }
    } 
    return ans;
}
8.力扣 945.使数组唯一的最小增量
执行用时:(216ms)
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int minIncrementForUnique(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    int count=0;
    for(int i=1;i<numsSize;i++)
    {
        if(nums[i-1]>=nums[i])
        {
            count+=nums[i-1]-nums[i]+1;
            nums[i]=nums[i-1]+1;
        }
    }
    return count;

}
9.力扣 611.有效三角形的个数(这下面也不知道对不对,反正时间超限,不知道for会超 ,while没事)
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int triangleNumber(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    int i,j,k;
    int count=0;
    for(i=0;i<numsSize-2;i++)
    {
        for(j=i+1;j<numsSize-1;j++)
        {
            for(k=j+1;k<numsSize;k++)
            {
                if(nums[i]+nums[j]<=nums[k]){
                    break;
                }
                
            }
            count+=k-j-1;
        }
    }
    return count;

}
——————————————————————————————————————————————————
今日分析:
    体验了一波贪心,其实就是体验了一种思路,考虑问题的思路,还要加油,还有四级,还有女朋友!!!!!嘿嘿嘿!!!!

上一篇:HTML5 3D翻书效果(双面效应)


下一篇:python中列表的排序方法操作总结分享