第六天!!!!
————————————————————————————————————————
学习内容：贪心算法
贪心算法的定义：不追求整体的最优，力求部部最优，这就是贪心
————————————————————————————————————————
课后习题：
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;
}
——————————————————————————————————————————————————
今日分析：
体验了一波贪心，其实就是体验了一种思路，考虑问题的思路，还要加油，还有四级，还有女朋友!!!!!嘿嘿嘿!!!!