【解题报告】《LeetCode零基础指南》(第七讲) 贪心(2)

简介: 【解题报告】《LeetCode零基础指南》(第七讲) 贪心(2)

324. 摆动排序 II

324. 摆动排序 II


题目描述


给你一个整数数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。


思路


先排序,然后把小元素倒序插入到0 2 4 等偶数位置。大元素倒序插入1 3 5奇数位置就好了。


int cmp(int *a, int *b){return *a > *b ? 1 : -1;}
void wiggleSort(int* nums, int numsSize){
    int ans[numsSize];
    for(int i = 0; i < numsSize;i++)  //复制数组
        ans[i] = nums[i];
    qsort(ans, numsSize, sizeof(int), cmp);
    int ansnum = (numsSize + 1)/2-1;
    for(int i = 0;i < numsSize; i+=2)//倒序插入
        nums[i] = ans[ansnum--];
    ansnum = numsSize - 1;
    for(int i = 1;i < numsSize; i+=2)//倒序插入
        nums[i] = ans[ansnum--];
}

455. 分发饼干

455. 分发饼干


题目描述


假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。


思路


这就是田忌赛马的思想,用最小的饼干满足对应的人,就可以得到最大的数量。


int cmp(int *a, int *b){return *a > *b ? 1 : -1;}
int findContentChildren(int* g, int gSize, int* s, int sSize){
    qsort(g, gSize, sizeof(int), cmp);
    qsort(s, sSize, sizeof(int), cmp);
    int numOfChildren = gSize, numOfCookies = sSize, ans = 0;
    for(int i = 0,j = 0;i < numOfChildren && j < numOfCookies;i++,j++){
        while(j < numOfCookies && g[i] > s[j])  j++;
        if(j < numOfCookies)    ans++;
    }
    return ans;
}


1827. 最少操作使数组递增

1827. 最少操作使数组递增


题目描述


给你一个整数数组 nums (下标从 0 开始)。每一次操作中,你可以选择数组中一个元素,并将它增加 1 。


比方说,如果 nums = [1,2,3] ,你可以选择增加 nums[1] 得到 nums = [1,3,3] 。

请你返回使 nums 严格递增 的 最少 操作次数。

我们称数组 nums 是 严格递增的 ,当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。

思路


如果后面的比前面的小就把它变成前面的数字加1就好了


int minOperations(int* nums, int numsSize){
    int ans = 0;
    for(int i = 1;i < numsSize;i++)
        if(nums[i] <= nums[i - 1])   ans+= nums[i-1]+1 - nums[i],nums[i] = nums[i - 1] +1;
    return ans;
}


945. 使数组唯一的最小增量

945. 使数组唯一的最小增量


题目描述


给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i,并将 nums[i] 递增 1。

返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。

思路


排完序之后和上面那道题一毛一样。。。


int cmp(int *a, int *b){return *a > *b ? 1 : -1;}
int minIncrementForUnique(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    int ans = 0;
    for(int i = 1;i < numsSize;i++)
        if(nums[i] <= nums[i - 1])   ans+= nums[i-1]+1 - nums[i],nums[i] = nums[i - 1] +1;
    return ans;
}


945. 使数组唯一的最小增量

945. 使数组唯一的最小增量


题目描述


给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i,并将 nums[i] 递增 1。

返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。

思路


排完序之后和上面那道题一毛一样。。。

int cmp(int *a, int *b){return *a > *b ? 1 : -1;}
int minIncrementForUnique(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    int ans = 0;
    for(int i = 1;i < numsSize;i++)
        if(nums[i] <= nums[i - 1])   ans+= nums[i-1]+1 - nums[i],nums[i] = nums[i - 1] +1;
    return ans;
}


611. 有效三角形的个数

611. 有效三角形的个数

题目描述


给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。


思路


听说有人过不去这题0.0,主要问题是需要不让指针回溯。啥意思呢?就是在i不变j增长的时候,k的值绝对不会比上次的结果小。

需要注意k-j可能是个0.。。。然后就好了


int cmp(int *a,int *b){return *a > *b ? 1 : -1;}
int triangleNumber(int* nums, int numsSize){
    int ans = 0;
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i = 0;i < numsSize - 2;i++){
        int k = i + 1;
        for (int j = i + 1;nums[j] && j < numsSize - 1; ++j) {
            while (k + 1 < numsSize && nums[k + 1] < nums[i] + nums[j]) {
                ++k;
            }
            ans += (k - j) > 0 ? (k - j) : 0;
        }
    }
    return ans;
}


相关文章
|
C语言 UED 索引
【解题报告】《LeetCode零基础指南》(第九讲) 二级指针(1)
【解题报告】《LeetCode零基础指南》(第九讲) 二级指针(1)
【解题报告】《LeetCode零基础指南》(第九讲) 二级指针(1)
【解题报告】《LeetCode零基础指南》(第八讲) 二维数组(2)
【解题报告】《LeetCode零基础指南》(第八讲) 二维数组(2)
【解题报告】《LeetCode零基础指南》(第八讲) 二维数组(2)
|
人工智能 C语言 UED
【解题报告】《LeetCode零基础指南》(第八讲) 二维数组(1)
【解题报告】《LeetCode零基础指南》(第八讲) 二维数组(1)
【解题报告】《LeetCode零基础指南》(第八讲) 二维数组(1)
|
算法 API C语言
【解题报告】《LeetCode零基础指南》(第六讲) C排序API(1)
【解题报告】《LeetCode零基础指南》(第六讲) C排序API(1)
【解题报告】《LeetCode零基础指南》(第六讲) C排序API(1)
|
C语言 UED
【解题报告】《LeetCode零基础指南》(第五讲) 指针(1)
【解题报告】《LeetCode零基础指南》(第五讲) 指针(1)
【解题报告】《LeetCode零基础指南》(第五讲) 指针(1)
|
存储 UED 索引
【解题报告】《LeetCode零基础指南》(第四讲) 一维数组(1)
【解题报告】《LeetCode零基础指南》(第四讲) 一维数组(1)
【解题报告】《LeetCode零基础指南》(第四讲) 一维数组(1)
【解题报告】《LeetCode零基础指南》(第三讲) 循环(1)
【解题报告】《LeetCode零基础指南》(第三讲) 循环(1)
【解题报告】《LeetCode零基础指南》(第三讲) 循环(1)
【解题报告】《LeetCode零基础指南》(第三讲) 循环(2)
【解题报告】《LeetCode零基础指南》(第三讲) 循环(2)
【解题报告】《LeetCode零基础指南》(第三讲) 循环(2)
|
C语言 UED
【解题报告】《LeetCode零基础指南》(第二讲) 函数(1)
【解题报告】《LeetCode零基础指南》(第二讲) 函数(1)
【解题报告】《LeetCode零基础指南》(第二讲) 函数(1)
【解题报告】《LeetCode零基础指南》(第九讲) 二级指针(2)
【解题报告】《LeetCode零基础指南》(第九讲) 二级指针(2)