[数据结构与算法]LeetCode——算法思想训练（贪心，二分）

LeetCode——算法思想训练（贪心，二分）

题号目录网址 (只做了部分题)
对应题号到LeetCode搜索

1.贪心

455. 分发饼干（简单题）

让胃口小的先吃，尽可能多分发

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int children = 0, cookie = 0;
        // 先排序
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        while(children<g.size() && cookie<s.size()){
            if(g[children]<=s[cookie]) ++children;
            ++cookie;
        }
        return children;
    }
};

135. 分发糖果（困难题）

来回两次循环，挺有意思

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size(), res=0;
        if (n < 2) {
        return n;
        }
        vector<int> candyNum(n,1); // 所有人都先给一个
        // 从左往右，保证每个比他左边大的数糖果都更多，从右往左保证每个比他右边大的糖果更多。
        // 从左往右，如果右边的数更大，就比他左边多一颗糖
        for(int i=1;i<n;++i){
            if(ratings[i-1]<ratings[i]){
                candyNum[i] = candyNum[i-1]+1;
            }
        }
        // 从右往左，如果左边的数更大，那取本身和右边加一个的最大值，主要保证左右两边都符合。
        for(int i=n-1;i>0;--i){
            if(ratings[i]<ratings[i-1]){
                candyNum[i-1] = max(candyNum[i-1], candyNum[i]+1);
            }
            res+=candyNum[i]; // 求最后结果，因为前面已经固定了
        }
        res+=candyNum[0];
        return res;
    }
};

435. 无重叠区间（中等题）

先排序，贪心很多时候都和排序一起用，这里有自定义排序。对区间尾的数字经行排序，然后从最小开始选，找不重复就行。这里区间尾很重要，排序是为了每次找最小区间，这样就可以尽量的保留更多的区间。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty()){
            return 0;
        }
        int n = intervals.size();
        // 自定义排序,sort(开始，结束，排序规则),排序规则函数，下面是lamda函数
        sort(intervals.begin(),intervals.end(),[](vector<int> a,vector<int> b){
            return a[1] < b[1];
        });
        int cnn=1,prev=intervals[0][1]; // cnn是第一个
        for(int i=1;i<n;++i){
            // 这里计算是无重叠区间个数
            if(intervals[i][0]>=prev){
                cnn++;
                prev=intervals[i][1];
            }
        }
        return n-cnn;
    }
};

452. 用最少数量的箭引爆气球（中等题）

跟上面那题类似，不过这次按照区间头排序，我们只要每次箭可以到达的最右边。具体看代码

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty()) return 0;
        int n = points.size();
        // 按照区间头排序
        sort(points.begin(),points.end(),[](vector<int> a,vector<int> b){
            return a[0]<b[0];
        });
        int res=1,right=points[0][1];
        for(int i=1;i<n;++i){
	        // 如果目前区间最左都比目前最右的都靠右，那就需要再一根箭了
	        // 否则就是判断下目前最右是哪个，然后继续
            if(points[i][0]>right){
                right=points[i][1];
                res++;
            }else{
                right=min(points[i][1],right);
            }
        }
        return res;
    }
};

下面是我自己强行找每次最小的区间，左右都比较，多了很多判断，比较繁琐

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty()) return 0;
        int n = points.size();
        sort(points.begin(),points.end(),[](vector<int> a,vector<int> b){
            return a[0]<b[0];
        });
        /*for(int i=0;i<n;++i){
            cout<<points[i][0]<<"=="<<points[i][1];
        }*/
        int res=1,left=points[0][0],right=points[0][1];
        for(int i=1;i<n;++i){
            if(points[i][0]<=right){
                // 保持区间最小
                if(points[i][0]>left){
                    left=points[i][0];
                }
                if(points[i][1]<right){
                    right=points[i][1];
                }
            }else{
                left=points[i][0];
                right=points[i][1];
                res++;
            }
        }
        return res;
    }
};

605. 种花问题（简单题）

主要开头和结尾要处理下，第二个方法比较厉害

方法一：

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        if(flowerbed.empty()) return n==0;
        if(flowerbed.size()==1){
            if(flowerbed[0]==0) return n<=1;
            else return n==0;
        }
        int i=0,left=0,right=1;
        while(i<flowerbed.size()-1 && n>0){
        	// 连续三个0才能种
            if(flowerbed[i]==0 && flowerbed[left]==0 && flowerbed[right]==0){
                flowerbed[i]=1;
                n--;
                cout<<n;
            }
            i++;
            left=i-1;
            right=i+1;
        }
        // 处理结尾
        if(n>0 && flowerbed[flowerbed.size()-2]==0 && flowerbed[flowerbed.size()-1]==0){
            n--;
        }
        return n==0;
    }
};

方法二：

因为要能种必然是前面一个0，肯定间隔是2，所以循环可以每次跳两个

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        if(flowerbed.empty()) return n==0;
        for(int i=0;i<flowerbed.size() && n>0;i+=2){
        	// 如果是0，判断下后面也是0或者最后一个就可种花，否则就跳过后面的1
        	// 如果是1，就再往后跳2个
            if(flowerbed[i]==0){
                if(i==flowerbed.size()-1 || flowerbed[i+1]==0){
                    n--;
                }else{
                    i++;
                }
            }
        }
        return n==0;
    }
};

763. 划分字母区间（中等题）

这题主要是字母位置标记处理好

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int n = s.size();
        // 存储每个字符最后出现的位置
        for(int i=0;i<n;i++){
            last[s[i]-'a']=i;
        }
        // 每个片段的左右
        int left=0,right=0;
        vector<int> res;
        for(int i=0;i<n;i++){
            // 每次选择最右节点
            right = max(right,last[s[i]-'a']);
            // 如果当前节点就是片段最右节点则找到片段
            if(right==i){
                res.push_back(right-left+1);
                left = right+1;
            }
        }
        return res;
    }
};

122. 买卖股票的最佳时机 II（简单题）

我不会，感觉有点动态的，下面这个是一直叠加。动态应该更好理解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for(int i=1;i<prices.size();++i){
        	// 因为最大差价，就是他们之间的差价和
            res+=max(0,prices[i]-prices[i-1]);
        }
        return res;
    }
};

406. 根据身高重建队列（中等题）

这题和前面类似，先排序，不过这题两个都得排序，然后思路就是身高高的人先排序，因为他不会影响到身高比他矮的，所以先确定身高高的位置就可以了。

class Solution {
public:

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),[](vector<int> a,vector<int> b){
        	// 先按照身高，再按照k
            return a[0]>b[0] || (a[0]==b[0]&&a[1]<b[1]);
        });
        vector<vector<int>> ans;
        for(int i=0;i<people.size();++i){
            ans.insert(ans.begin()+people[i][1], people[i]);
        }
        return ans;
    }
};

665. 非递减数列（中等题）

存在非递减数列就计数，当出现两次就不对。

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int cnt=0;
        for(int i=0;i<nums.size()-1;++i){
            int x = nums[i], y = nums[i+1];
            if(x>y){
                cnt++;
                if(cnt>1) return false;
                // 这里是为了防止比如3,4,2,3的情况，这时候只改变4是不行的。
                // 要保持前面序列对的情况，再继续对后面做判断
                if(i>0 && y<nums[i-1]){
                    nums[i+1] = x;
                }
            }
        }
        return true;
    }
};

2.二分查找

69. x 的平方根（简单题）

虽然是简单题，但这里有个牛顿迭代，数值分析的，不过其实很简单。

class Solution {
public:
    int mySqrt(int x) {
        if(x==0) return 0;
        int l=1,r=x,mid=0;
        while(l<=r){
            mid = l+(r-l)/2;
            int sqrt = x/mid;
            if(mid==sqrt) return mid;
            else if(mid>sqrt) r = mid-1;
            else l = mid+1;
        }
        return r;
    }
};

牛顿迭代，其主要用处是电脑用这样的方法求开方贼快，数值分析很多这样的。

class Solution {
public:
    int mySqrt(int x) {
        // 牛顿迭代法，切线不断逼近
        // X(n+1) = Xn - f(Xn)/f'(Xn)
        // 这里的Xn是x^2，所以X(n+1) = x - (x*x-a)/2*x = (x+a/x)/2
        long a = x;
        while(a*a>x){
            a = (a+x/a)/2;
        }
        return a;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置（中等题）

二分查找快一点，貌似还有更容易的

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if(n==0) return {-1, -1};
        int left=0,right=n-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]==target){
                left=mid-1;
                right=mid+1;
                while(left>=0 && nums[left]==target) --left;
                while(right<=n-1 && nums[right]==target) ++right;
                return {left+1,right-1};
            }
            else if(nums[mid]>target) right = mid-1;
            else left = mid+1;
        }
        return {-1,-1};
    }
};

81. 搜索旋转排序数组 II（中等题）

也是二分思路，不过感觉这些题目就是强行用二分，为了时间能过

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        int left=0, right=n-1;
        if(n==0) return false;
        if(n==1) return nums[0]==target;
        while(left<=right){
            int mid = (right+left)/2;
            if(nums[mid]==target) return true;
            if(nums[mid]==nums[left]) ++left;  // 如果无法判断则往右移动,最右肯定是递增
            else if(nums[mid]<=nums[right]){   // 若目标存在则肯定在中间,否则就找左边
                if(target>nums[mid] && target<=nums[right]){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }else{  // 这时候mid在左半边
                if(target>=nums[left] && target<nums[mid]){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
        }
        return false;
    }
};

154. 寻找旋转排序数组中的最小值 II（困难题）

感觉多旋转几次没差别啊，跟上面不是一样，这题求最小，所以判断简单了很多

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        int l=0,r=n-1;
        while(l<r){
            int mid = (l+r)/2;
            if(nums[mid]<nums[r]){
                r = mid;  // 这里的mid可能是最小值
            }else if(nums[mid]>nums[r]){
                l = mid+1;
            }else{
                --r;
            }
        }
        return nums[l];
    }
};

540. 有序数组中的单一元素（中等题）

看着很简单，用二分还是有点坑

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        int l=0,r=n-1;
        while(l<r){
            int mid = (l+r)/2;
            if(mid%2==1) --mid;  // 奇数数组,前后下标为偶数
            if(nums[mid]==nums[mid+1]){
                l=mid+2;
            }else{
                r = mid;
            }
        }
        return nums[l];
    }
};

451. 根据字符出现频率排序（中等题）

研究了下几个for循环方法

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> mp;
        int maxFreq = 0;
        for(int i=0;i<s.size();++i){
            maxFreq = max(maxFreq,++mp[s[i]]); // 按照频率计数
        }
        vector<string> buckets(maxFreq+1);
        /*for(auto &[ch,num]:mp){
            buckets[num].push_back(ch);
        }
        for(auto a:mp){
            buckets[a.second].push_back(a.first);
        }*/
        // 这里是有排序
        for(unordered_map<char,int>::iterator ch=mp.begin();ch!=mp.end();++ch){
            buckets[ch->second].push_back(ch->first);
        }
        
        string ans;
        for(int i=maxFreq;i>0;--i){
            string &bucket = buckets[i];
            for(auto &ch:bucket){
                for(int j=0;j<i;++j){
                    ans.push_back(ch);
                }
            }
        }
        return ans;
    }
};

总结

贪心思想主要是找最小或最大，很多时候感觉可以用动态，但贪心代码简单。二分题目感觉有些强行二分，不过还是很重要，数据量大了速度差别很大。