1.1913. 两个数对之间的最大乘积差
硬算 没有负数情况 感觉题比较垃圾
class Solution { public: int maxProductDifference(vector& nums) { sort(nums.begin(),nums.end()); int n = nums.size() - 1; return (nums[n] * nums[n-1] - nums[0] * nums[1]); } };
2.976. 三角形的最大周长
昨天的
class Solution { public: int largestPerimeter(vector& nums) { sort(nums.begin(),nums.end()); int n = nums.size() - 1; for(int i = n;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
排序以后相邻元素组队
class Solution { public: int arrayPairSum(vector& nums) { sort(nums.begin(),nums.end()); int ans = 0; for(int i = 0;i
4.881. 救生艇
昨天最后一题
class Solution { public: int numRescueBoats(vector& people, int limit) { sort(people.begin(),people.end()); int ans = 0; int i = 0,j = people.size() - 1; while(i <= j){ if(people[j] + people[i] <= limit) i++; j--; ans++; } return ans; } };
5.324. 摆动排序 II
首先用快选,选出中位数 时间: 空间:
其次把数分为三类
- 第一类:大于mid 2
- 第二类:等于mid 1
- 第三类:小于mid 0
排序成 00000 111111 222222 时间: 空间:
然后让 第一类数 '2' 放到奇数位置
其他两类填到剩余位置
class Solution { public: void wiggleSort(vector& nums) { int n = nums.size(); auto midptr = nums.begin() + n / 2; nth_element(nums.begin(),midptr,nums.end()); int mid = * midptr; #define A(i) nums[(i * 2 + 1) % (n | 1)] for(int i = 0,j = 0,k = n - 1;i <= k;){ if(A(i) > mid) swap(A(i++),A(j++)); else if(A(i) < mid) swap(A(i),A(k--)); else i++; } } };
6.455. 分发饼干
- 分别将孩子的贪心指数和饼干尺寸都从小到大排序。
- 定义 和 从 0 开始,代表尝试将第 块饼干分配给第 个孩子。若 =gi" src="https://latex.codecogs.com/gif.latex?sj%3E%3Dgi" />,则答案加 1, 和 都向后移动;否则 向后移动。
class Solution { public: int findContentChildren(vector& g, vector & s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int ans = 0; for (int i = 0, j = 0; i < g.size() && j < s.size(); j++) if (s[j] >= g[i]) { ans++; i++; } return ans; } };
这几天实习没时间写,下面的等实习结束补
7.1827. 最少 *** 作使数组递增
8.945. 使数组唯一的最小增量
9.611. 有效三角形的个数
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)