算法篇-------贪心2

题目1-------活动选择

有n个需要在同一天使用同一个教室的活动a1, a2, …, an，教室同一时刻只能由一个活动使用。每个活动a[i]都有一个
开始时间s[i]和结束时间f[i]。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重
叠，a[i]和a[j]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。

怎么考虑呢？
我们优先考虑结束时间最早的活动，结束时间最早意味着能安排更多的活动。
贪心-------通过一系列的局部最优达到总体最优，（只考虑眼前）

选择最早开始和最短时间都不能达到目的。例如下面的3个活动：

代码分享：

class Sort
{
public:
	bool operator()(vector<int> a, vector<int> b)
	{
		return a[1] < b[1];
	}
};

//vv是已经按照最短结束时间排序好的
int get_max_act(const vector<vector<int>>& vv)
{
	int cnt = 1;
	int endtime = vv[0][1];
	for (int i = 1; i < vv.size(); i++)
	{
		//可以安排下一个活动了
		//下一个活动的起始时间大于当前活动的结束时间
		if (vv[i][0] >= endtime) 
		{
			endtime = vv[i][1];
			cnt++;
		}
	}

	return cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

题目2-----无重叠区间

力扣题：435

这一题和上面一题的思路一样， 优先选择结束区间最小的，使之能有更多的区间，然后达到删除最小区间的目的。
也就是说，通过一系列的局部最优达到整体最优。

class Solution {
public:
    class Sort
    {
    public:
           bool operator()(const vector<int>& a, const vector<int>& b)
           {
               return a[1] < b[1];
           }
    };

    int eraseOverlapIntervals(vector<vector<int>>& intervals) 
    {
        if(intervals.empty())
            return 0;

        sort(intervals.begin(), intervals.end(), Sort());
        int end = intervals[0][1];
        int num = 1;
        for(int i = 1; i < intervals.size(); i++)
        {
            if(intervals[i][0] >= end)
            {
                end = intervals[i][1];
                num++;
            }
        }

        return intervals.size()- num;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

题目3------最多可以参加的会议数目

力扣：1353

这个题和上面几个题有些不同，上面的是时间间隔， 而这一题用的是其中某一天
也就是说，在1-----10 0001天我们都是可以去开会议的。
怎么去选择会议呢？ 优先选择开始时间最早，结束时间最短的。

这个题的核心思路是：
优先选择开始时间最早， 但是呢很多会议也会存在开始时间一样的情况，所以呢我们再次进行选择，选择结束时间最早的。

这一题稍微有一些复杂，所以提供了不少的注释
代码：

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) 
    {
        //因为开始时间的范围是在1--10^5
        vector<vector<int>> vv(100001);
        
        //按照起始实际按分类，将第i个会议分到同一个一维数组
        for(int i = 0; i < events.size(); i++)
            vv[events[i][0]].push_back(i);
        
        //优先队列类型是int， 容器是适配器用vector， 采用小堆
        int ans = 0;
        priority_queue<int, vector<int>, greater<int>> pq;

        //遍历所有可以执行的时间，看看某一个会议能不能在这一天去执行
        for(int i = 0; i < 100001; i++)
        {
            for(auto e : vv[i])  //e是开始时间为vv[i]的第几个会议
              pq.push(events[e][1]);   //将其结束时间入队列
            
            //i表示当前执行的时间，而队列存放的是结束时间
            //只要比i小的结束时间表明该会议已经错过了
            while(!pq.empty() && pq.top() < i)
               pq.pop();
            
            //从里面找出一个会议结束时间最早的出来开。
            if(!pq.empty())
            {
                ans++;
                pq.pop();
            }
        }
        
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

题目4-------去除重复字母

力扣题：316

class Solution {
public:
    string removeDuplicateLetters(string s) 
    {
        unordered_map<char, int> cnt;
        unordered_map<char, bool> inst;
        stack<char> st;

        for(auto e : s)       //用map统计次数
              cnt[e]++;

        for(int i = 0; i < s.size(); i++)
        {
            char c = s[i];
            if(inst[c])  //要操作的元素已经在栈里面，默认已经放好了
            {
                cnt[c]--;
                continue;
            }
           
            //如果当前操作的元素小于栈顶元素，并且栈顶元素还存在
            while(!st.empty() && c < st.top() && cnt[st.top()] > 0)
            {
                inst[st.top()] = false; //出栈了，栈顶元素肯定就不在栈了
                st.pop();
            }
            
            inst[c] = true; //入栈后就改状态
            st.push(c);
            cnt[c]--;
        }
        
        string ans;
        while(!st.empty())
        {
            ans += st.top();
            st.pop();
        }
        
        reverse(ans.begin(), ans.end()); //需要逆序操作的
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

题目5------移掉K位数字

力扣题：402

class Solution {
public:
    string removeKdigits(string num, int k)
    {
         string ans;
         stack<char> st;

         for(int i = 0; i < num.size(); i++)
         {
             char c = num[i];
             
             //当前操作的元素 < 栈顶元素 &&  有删除的机会 k > 0 
             while(!st.empty() && c < st.top() && k > 0)
             {
                 st.pop();
                 k--;
             }
            
            //栈位空， 当前为0，直接不考虑
            if(st.empty() && c == '0')
                   continue;

             st.push(c);
         }
           
         while(!st.empty() && k--)   //如果还有删除的机会，直接删除
             st.pop();

        while(!st.empty())
        {
            ans += st.top();
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        
        if(ans.empty())
              ans += "0";

        return ans;     
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

题目6-----拼接最大数

力扣321

这一个题目代码虽然有一些长，但是逻辑比较简单，并不复杂。

class Solution {
public:

    //k是需要移除的个数
    vector<int> subNumber(const vector<int>& v, int k)
    {
        vector<int> ans;
        stack<int> st;
        for (int i = 0; i < v.size(); i++)
        {
            int c = v[i];

            while (!st.empty() && c > st.top() && k > 0)
            {
                st.pop();
                k--;
            }

            st.push(c);
        }

        while (!st.empty() && k > 0)
        {
            st.pop();
            k--;
        }

        while (!st.empty())
        {
            ans.push_back(st.top());
            st.pop();
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }

    // v1 >= v2 返回true
    bool cmpArray(const vector<int>& v1, int i, const vector<int>& v2, int j)
    {
        while (i < v1.size() && j < v2.size())
        {
            if (v1[i] > v2[j])
                return true;

            if (v1[i] < v2[j])
                return false;

            i++;
            j++;
        }

        //走到这里， 无非就是一个为空， 一个不为空
        if (j == v2.size())
            return true;

        return false;
    }

    vector<int> mergeArray(const vector<int>& v1, const vector<int>& v2)
    {
        int i = 0, j = 0;
        vector<int> ans;

        while (i < v1.size() && j < v2.size())
        {
            if (cmpArray(v1, i, v2, j))
            {
                ans.push_back(v1[i]);
                i++;
            }
            else
            {
                ans.push_back(v2[j]);
                j++;
            }
        }

        while (i < v1.size())
        {
            ans.push_back(v1[i++]);
        }

        while (j < v2.size())
        {
            ans.push_back(v2[j++]);
        }

        return ans;
    }

    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
    {
        //下面一个数组拿出多少个元素，另一个数组拿出一个元素边界不好控制
        //我们用举例来： m = 4 , n = 6,显然对于nums2来说
        //最少拿出一个元素， 最多拿出5个元素
        int m = nums1.size(), n = nums2.size();
        int begin = max(0, k - m), end = min(k, n);

        vector<int> ans;
        for (int i = begin; i <= end; i++)
        {
            //对于nums2来说，拿出i个元素， 去掉n - i 个元素
            //对于nums1来说，就要拿出k - i个， 去掉m - k + i个元素
            vector<int> subnum1 = subNumber(nums2, n - i);
            vector<int> subnum2 = subNumber(nums1, m - k + i);

            vector<int> ret = mergeArray(subnum1, subnum2);
            if (cmpArray(ret, 0, ans, 0))
                swap(ret, ans);  //c++11支持右值引用，可以窃取资源
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115