贪心day4

前言

💫你好，我是辰chen，本文旨在准备考研复试或就业
💫文章题目大多来自于 leetcode，当然也可能来自洛谷或其他刷题平台
💫欢迎大家的关注，我的博客主要关注于考研408以及AIoT的内容
🌟 仅给出C++版代码

以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)，欢迎大家的关注：

💥ACM-ICPC算法汇总【基础篇】
💥ACM-ICPC算法汇总【提高篇】
💥AIoT(人工智能+物联网)
💥考研
💥CSP认证考试历年题解

减小和重新排列数组后的最大元素

题目链接：减小和重新排列数组后的最大元素

C++版AC代码：

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        arr[0] = 1;

        for (int i = 0; i < arr.size() - 1; ++ i ) {
            if (arr[i + 1] - arr[i] > 1)
                arr[i + 1] = arr[i] + 1;
        }

        return arr[arr.size() - 1];
    }
};

使数组唯一的最小增量

题目链接：使数组唯一的最小增量

C++版AC代码：

class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        int res = 0;
        for (int i = 1; i < nums.size(); ++ i ) {
            int t = nums[i] - nums[i - 1];
            if (t <= 0) {
                res += 1 - t;
                nums[i] += 1 - t;
            }
        }

        return res;
    }
};

字符频次唯一的最小删除次数

题目链接：字符频次唯一的最小删除次数

C++版AC代码：

class Solution {
public:
    int minDeletions(string s) {
        unordered_map<char, int> m;
        for (int i = 0; i < s.size(); ++ i ) 
            m[s[i]] ++;
        
        vector<int> num;
        for (auto i = m.begin(); i != m.end(); ++ i ) 
            num.push_back(i -> second);
        
        sort(num.begin(), num.end(), greater<>());

        int res = 0;
        for (int i = 0; i < num.size() - 1; ++ i ) {
            int t = num[i + 1] - num[i];
            if (t >= 0 && num[i + 1] > t + 1) {
                res += t + 1;
                num[i + 1] -= t + 1;
            } else if (num[i + 1] == t + 1) {
                for (int j = i + 1; j < num.size(); ++ j ) 
                    res += num[j];
                break;
            }

        }

        return res; 
    }
};

找到最大周长的多边形

题目链接：找到最大周长的多边形

C++版AC代码：

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        vector<long long> sum(nums.begin(), nums.end());
        for (int i = 1; i < sum.size(); ++ i ) {
            sum[i] += sum[i - 1];
        }

        long long res = -1;
        for (int i = nums.size() - 1; i > 0; i -- ) {
            if (nums[i] < sum[i - 1]) {
                res = sum[i - 1] + nums[i];
                break;
            }
        }

        return res;
    }
};

拆分成最多数目的正偶数之和

题目链接：拆分成最多数目的正偶数之和

C++版AC代码：

class Solution {
public:
    vector<long long> maximumEvenSplit(long long finalSum) {
        vector<long long> res;
        if (finalSum % 2) 
            return res;
        
        long long tmp = finalSum;
        // i < tmp - i (->) 2 * i < tmp
        for (long long i = 2; i <= finalSum && 2 * i < tmp; i += 2) {
            tmp -= i;
            res.push_back(i);
        }
        res.push_back(tmp);
        
        return res;
    }
};

修改两个元素的最小分数

题目链接：修改两个元素的最小分数

C++版AC代码：

class Solution {
public:
    int minimizeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        int n = nums.size() - 1;

        int sl1 = nums[n - 1] - nums[1];   // 最大最小改次大次小
        int sl2 = nums[n] - nums[2];       // 最小两个改最大
        int sl3 = nums[n - 2] - nums[0];   // 最大两个改最小
    
        return min(sl1, min(sl2, sl3));
    }
};