九日集训（每日打卡）第六天

九日集训（每日打卡）第六天

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. 有效三角形的个数
 
 
 
 
 
 
 
 

 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://www.54852.com/zaji/5671109.html