leetcode贪心算法题总结(三)

1.合并区间

合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        //先按左端点进行排序
        sort(intervals.begin(),intervals.end());
        int left = intervals[0][0],right = intervals[0][1];
        vector<vector<int>> ret;
        //进行区间合并
        for(int i=1;i<n;i++)
        {
            int a = intervals[i][0],b = intervals[i][1];
            if(a<=right) right = max(right,b);
            else
            {
                ret.push_back({left,right});
                left = a;
                right = b;
            }
        }
        ret.push_back({left,right});
        return ret;
    }
};

2.无重叠区间

无重叠区间

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        //按照左端点进行排序
        sort(intervals.begin(),intervals.end());
        int ret = 0;
        //移除区间
        int left = intervals[0][0],right = intervals[0][1];
        for(int i=1;i<n;i++)
        {
            int a = intervals[i][0],b = intervals[i][1];
            if(a<right)
            {
                ret++;
                right = min(right,b);
            }
            else
            {
                right = b;
            }
        }
        return ret;
    }
};

3.用最少数量的箭引爆气球

用最少数量的箭引爆气球

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int n = points.size();
        //按左端点进行排序
        sort(points.begin(),points.end());
        //求交集
        int ret = 0;
        int right = points[0][1];
        for(int i=1;i<n;i++)
        {
            int a = points[i][0],b = points[i][1];
            if(a<=right)
            {
                right = min(right,b);
            }
            else
            {
                ret++;
                right = b;
            }
        }
        return ret+1;//最后一个也需要一支箭
    }
};

4.整数替换

整数替换

class Solution {
    unordered_map<long long,long long> hash;//存储某一个数到1的最小步数
public:
    int integerReplacement(int n) {
        //法一：递归+记忆化搜索
        return dfs(n);
    }

    long long dfs(long long n)
    {
        if(hash.count(n)) return hash[n];
        if(n == 1)
        {
            hash[1] = 0;
            return hash[1];
        }
        if(n%2==0)
        {
            hash[n] = 1+dfs(n/2);
            return hash[n];
        }
        else
        {
            hash[n] = 1+min(dfs(n+1),dfs(n-1));
            return hash[n];
        }
    }
};

class Solution {
public:
    int integerReplacement(int n) {
        //法二：贪心+找规律
        int ret = 0;
        while(n>1)
        {
            if(n%2 == 0)
            {
                n /= 2;
                ret++;
            }
            else
            {
                if(n == 3) 
                {
                    ret += 2;
                    n =1;
                }
                else if(n%4 ==1)
                {
                    ret +=2;
                    n /=2;
                }
                else
                {
                    ret += 2;
                    n = n/2 +1;
                }
            }
        }
        return ret;
    }
};

5.俄罗斯套娃信封问题

俄罗斯套娃信封问题

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& e) {
        //法一：动态规划 O(n^2) 超时
        //状态表示：dp[i]表示：以i位置的信封为结尾的所有套娃序列中，最长的套娃序列的长度
        int n = e.size();
        vector<int> dp(n,1);
        sort(e.begin(),e.end());
        int ret = 1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(e[i][0]>e[j][0]&&e[i][1]>e[j][1])
                {
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            ret = max(ret,dp[i]);
        }
        return ret;
    }
};

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& e) {
        //法二：重写排序+贪心+二分
        int n = e.size();
        sort(e.begin(),e.end(),[&](const vector<int>& v1,const vector<int>& v2)
        {
            return v1[0]!=v2[0]?v1[0]<v2[0]:v1[1]>v2[1];
        });
        //此时问题转化成我们之前写过的最长递增子序列问题
        vector<int> ret;
        ret.push_back(e[0][1]);
        for(int i=1;i<n;i++)
        {
            int a = e[i][1];
            if(a>ret.back())
            {
                ret.push_back(a);
            }
            else
            {
                int left = 0,right = ret.size()-1;
                while(left<right)
                {
                    int mid = (left+right)>>1;
                    if(ret[mid]>=a) right = mid;
                    else left = mid+1;
                }
                ret[left] = a;
            }
        }
        return ret.size();
    }
};

6.可被三整除的最大和

可被三整除的最大和

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        //正难则反 
        //把所有的数都累加起来，根据累加和进行删除
        const int INF = 0x3f3f3f3f;
        int x1 = INF,x2 = INF,y1 = INF,y2 = INF,sum = 0;
        for(auto x:nums)
        {
            sum+=x;
            if(x%3 ==1)
            {
                if(x<x1)
                {
                    x2 = x1;
                    x1 = x;
                }
                else if(x<=x2)
                {
                    x2 = x;
                }
            }
            else if(x%3 ==2)
            {
                if(x<y1)
                {
                    y2 = y1;
                    y1 = x;
                }
                else if(x<=y2)
                {
                    y2 = x;
                }
            }
        }
        //分类讨论
        if(sum%3==0) return sum;
        else if(sum%3 ==1) return max(sum-x1,sum-y1-y2);
        else return max(sum-y1,sum-x1-x2);
    }
};

7.距离相等的条形码

距离相等的条形码

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int,int> hash;//统计每个数字出现的次数
        int maxVal = 0,maxCount = 0;
        for(auto x:barcodes)
        {
            if(maxCount<++hash[x])
            {
                maxCount = hash[x];
                maxVal = x;
            }
        }
        //先处理出现次数最多的哪个数
        int n = barcodes.size();
        vector<int> ret(n);
        int index = 0;
        for(int i=0;i<maxCount;i++)
        {
            ret[index] = maxVal;
            index += 2;
        }
        //再处理其他的数
        hash.erase(maxVal);
        for(auto&[x,y] : hash)
        {
            for(int i=0;i<y;i++)
            {
                if(index>n-1) index = 1;
                ret[index] = x;
                index += 2;
            }
        }
        return ret;
    }
};

8.重构字符串

重构字符串

class Solution {
public:
    string reorganizeString(string s) {
        //模拟+贪心
        int hash[26] = {0};
        char maxChar = ' ';
        int maxCount = 0;
        for(auto x:s)
        {
            if(maxCount<++hash[x-'a'])
            {
                maxCount = hash[x-'a'];
                maxChar = x;
            }
        }
        //先判断
        int n = s.size();
        if(maxCount>(n+1)/2) return "";
        string ret(n,' ');
        int index = 0;
        //先处理出现次数最多的那个字符
        for(int i=0;i<maxCount;i++)
        {
            ret[index] = maxChar;
            index += 2;
        }
        //再处理其他字符
        hash[maxChar-'a'] = 0;
        for(int i=0;i<26;i++)
        {
            for(int j=0;j<hash[i];j++)
            {
                if(index>n-1) index = 1;
                ret[index] = 'a'+i;
                index += 2;
            }
        }
        return ret;
    }
};

这个系列到此就全部完啦，希望对您有所帮助，有什么不懂的可以直接私信我，我会为大家进行依次解答呀！