[学习报告]《LeetCode零基础指南》(第七讲) 贪心---gyro v1.0

• 0. 知识概念
• 1. 解题报告
• • Q1. 1913. 两个数对之间的最大乘积差
  • Q2. 976. 三角形的最大周长
  • Q3. 561. 数组拆分 I
  • Q4. 881. 救生艇
  • Q5:324. 摆动排序 II
• 思考总结（think&summary）：

1. 贪心算法：不断转化问题，寻求问题的局部最优解。并不能保证数学上的整体绝对最优，而是保证工程上的整体最优。
2. 步步贪心
   先特殊，后一般；首先要先考虑特殊情况
   第一步

（1） 明确到底什么是最优解？

————即用 数学化&定量化所解问题的目的值&要求，约束值&要求，逻辑化&结构化的策略重新描述问题，
让问题进一步的清晰和具体。

1）数学化&定量化：转述问题，强调问题中的目的：结果数值。约束：条件数值
分析问题 目的值：求哪个数值—结果数值 目的要求：max,min等
约束值：限制条件—条件数值 约束要求：<,>=,>,<==等
e.g. 背包问题的重量有限，价值最大？
————目的值&要求：价值&最大
————约束值&要求：重量&小于
e.g. 救生艇问题？
————目的值&要求：船数量&最少
————约束值&要求：（1）人数&小于2（2）人重量&小于船载荷
e.g. 三角形最大周长问题？
————目的值&要求：周长&最大
————约束值&要求：任意两边之和&小于第三边
e.g. 1913. 两个数对之间的最大乘积差
————目的值&要求值：数对乘积差&最大
————约束值&要求值：4个数配对&任意

2）逻辑化&结构化：指所求问题，要求按一定的逻辑排序之类的。需要明确其逻辑和结构。
理解问题，抓住关键将问题的表述用结构化的数据来表述。

第二步

明确什么是子问题的最优解？
–施加影响，改变结构

第三步

分别求出子问题的最优解再堆叠出全局最优解？

分别求出子问题的最优解再堆叠出全局最优解？

题目见：《LeetCode零基础指南》(第七讲) 贪心

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];

}

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

int largestPerimeter(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);

    int i;
    
    for(i=0;inums[i])
        return nums[i+1]+nums[i+2]+nums[i];
    }

    return 0;

}

  
    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 i;
        int sum = 0;
        for(i = 0;i < numsSize;i = i+2)
        {
            sum +=*(nums+i);
        }
        return sum;
  

}

  

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

int numRescueBoats(int* people, int peopleSize, int limit){
    
    qsort(people,peopleSize,sizeof(int),cmp);

    int cnt_ship=0;
    int l=0,r=peopleSize-1;
    

    while( l <= r )
    {
        if( l == r)
        {
            cnt_ship++;
            break;
        }
        else if(people[l]+people[r]>limit)
        {
            cnt_ship++;l++;
        }
        else 
        {
            cnt_ship++;l++;r--;
        }
    }

    return cnt_ship;

}

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

void wiggleSort(int* nums, int numsSize){

    qsort(nums,numsSize,sizeof(int),cmp);
    
    int *ans = (int *)malloc(sizeof(int)*numsSize); 
    int i;
    for(i=0;i 
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}

void wiggleSort(int* nums, int numsSize){

    qsort(nums,numsSize,sizeof(int),cmp);
    
    int *ans = (int *)malloc(sizeof(int)*numsSize); 
    int i,r;
    for(i=0;i 
Q6:
 
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,j=0,cnt=0;
    for(i=0;i=g[i])
            {
                cnt++;
                j++;
                break;
            }
            else
            {
                j++;
            }
        }
        if(j==sSize)
        {
            break;
        }
    }
    

 return cnt;
}
 
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=gSize-1,j=sSize-1,cnt=0;
    while(i>=0&&j>=0)
    {
        
        if(s[j]>=g[i])
        {
            j--;
            i--;
            cnt++;
        }
        else{
            i--;
        }
    }
    

 return cnt;
}
 
Q7：1827. 最少操作使数组递增
 
在这里插入代码片
 
思考总结（think&summary）： 
(1)程序书写时，眼睛盯着屏幕，专注，小心，不要出现错，漏，反等；（2）贪心算法，就是转化问题，将复杂的问题分解转化为可以具体的，简单的问题，步步贪心。
 （3）工程上最优接近而不等于数学上最优。