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