LeetCode(C++)-贪心算法（用最少数量的箭引爆气球、无重叠区间、划分字母区间、合并区间、买卖股票的最佳时机含手续费、单调递增的数字、监控二叉树）

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

代码

class Solution {	//452. 用最少数量的箭引爆气球 当气球出现重叠时，一起射，所用弓箭最少 给气球从小到大排个序，
	//然后如果当前气球的起始边界大于前一个气球的结尾边界，气球个数就+1
	//否则，说明气球有重叠，更新当前气球的右边界（两个右边界中取最小的）
public:
	static bool cmp(vector<int> const& first, vector<int> const& second) {
		if (first[0] == second[0])return first[1] < second[1];
		return first[0] < second[0];
	}
	int findMinArrowShots(vector<vector<int>>& points) {
		sort(points.begin(), points.end());
		int result = 1;
		for (int i = 1; i < points.size(); ++i) {
			if (points[i][0] > points[i - 1][1]) {
				result++;
			}
			else {
				points[i][1] = min(points[i - 1][1], points[i][1]);
			}
		}
		return result;
	}
};

int main() {
	vector<vector<int>> points = { { 9, 12 }, { 1, 10 }, { 4, 11 }, { 8, 12 }, { 3, 9 }, { 6, 9 }, { 6, 7 } };
	Solution s;
	int result = s.findMinArrowShots(points);
	printf("%d\n", result);
	return 0;
}
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

435. 无重叠区间

代码

class Solution {	//435. 无重叠区间 按右边界从小到大排序	计算出不重叠的个数 用总数减去不重叠的个数
public:
	static bool cmp(vector<int> const& first, vector<int> const& second) {
		return first[1] < second[1];
	}
	int eraseOverlapIntervals(vector<vector<int>>& intervals) {
		if (intervals.size() == 0)return 0;
		sort(intervals.begin(), intervals.end(), cmp);
		int result = 1;
		int end = intervals[0][1];
		for (int i = 1; i < intervals.size(); ++i) {
			if (end <= intervals[i][0]) {
				end = intervals[i][1];
				result++;
			}
		}
		return intervals.size() - result;
	}
};

int main() {
	vector<vector<int>> intervals = { { 1, 2 }, { 2,3 }};
	Solution s;
	int result = s.eraseOverlapIntervals(intervals);
	printf("%d\n", result);
	return 0;
}
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

763. 划分字母区间

代码

class Solution {	//763. 划分字母区间  先将每个字母第一次出现的位置和最后一次出现的位置记录下来
	//形成一些区间，将这些区间排序，区间有交集的就合并成一个区间，最后有多个区间，计算每个区间长度，就是每个字符串片段的长度列表
public:
	static bool cmp(vector<int> const& first, vector<int> const& second) {
		return first[0] < second[0];
	}
	vector<int> partitionLabels(string s) {
		vector<vector<int>> nums;
		vector<int> result;
		unordered_map<char, map<int, int>> umap;
		//将字母第一次出现的位置以及最后一次出现的位置保存
		for (int i = 0; i < s.size(); ++i) {
			if (umap.find(s[i]) == umap.end())
				umap[s[i]][0] = i;
			else {
				umap[s[i]][1] = i;
			}
		}
		//形成每个字母区间
		unordered_map<char, map<int, int>>::iterator it;
		for (it=umap.begin(); it!= umap.end(); ++it) {
			vector<int> temp;
			for (pair<const int, int> & iter : it->second) {
				temp.push_back(iter.second);
			}
			if (temp.size() == 1) temp.push_back(temp.back());
			nums.push_back(temp);
		}
		//区间排序
		sort(nums.begin(), nums.end(), cmp);
		//区间合并 如果当前区间结束了 就将区间长度记录下来
		for (int i = 1; i < nums.size(); ++i) {
			if (nums[i][0] < nums[i - 1][1]) {
				nums[i][1] = max(nums[i][1], nums[i - 1][1]);
				nums[i][0] = min(nums[i][0], nums[i - 1][0]);
			}
			else {
				result.push_back(nums[i-1][1] - nums[i-1][0] + 1);
			}
		}
		//将最后一个区间加入
		result.push_back(nums[nums.size() - 1][1] - nums[nums.size() - 1][0] + 1);
		return result;
	}
};

int main() {
	string s = "ababcbacadefegdehijhklij";
	Solution solution;
	vector<int> result = solution.partitionLabels(s);

	return 0;
}
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

56. 合并区间

代码

class Solution {	//56. 合并区间   763. 划分字母区间这道题就用到了区间合并的思想 将这些区间排序，区间有交集的就合并成一个区间
	//左边界取两者中最小 右边界取两者最大 每次都对区间边界进行更新 区间结束 将i的前一个加入结果集 开始新的区间
public:
	static bool cmp(vector<int> const& first, vector<int> const& second) {
		return first[0] < second[0];
	}
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		vector<vector<int>> result;
		sort(intervals.begin(), intervals.end(), cmp);
		for (int i = 1; i < intervals.size(); ++i) {
			if (intervals[i][0] <= intervals[i - 1][1]) {
				intervals[i][1] = max(intervals[i][1], intervals[i - 1][1]);
				intervals[i][0] = min(intervals[i][0], intervals[i - 1][0]);
			}
			else {
				result.push_back(intervals[i - 1]);
			}
		}
		result.push_back(intervals[intervals.size() - 1]);
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

738. 单调递增的数字

代码

class Solution {	//738. 单调递增的数字  将数字转为字符串 然后从后往前遍历，遇见前一个数大于后一个数的，做个标记，同时前面那个数减一
	//然后从标记的位置开始，一直到最后，将这段区间的数字都改成9  最后将字符串转为数字
public:
	int monotoneIncreasingDigits(int n) {
		string strNum = to_string(n);
		int flag = strNum.size();
		for (int i = strNum.size() - 1; i > 0; --i) {
			if (strNum[i - 1] > strNum[i]) {
				flag = i;
				strNum[i - 1]--;
			}
		}
		for (int i = flag; i < strNum.size(); ++i) {
			strNum[i] = '9';
		}
		return stoi(strNum);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

714. 买卖股票的最佳时机含手续费

代码

class Solution {	//714. 买卖股票的最佳时机含手续费 
public:
	int maxProfit(vector<int>& prices, int fee) {
		int result = 0;
		int minPrice = prices[0];
		for (int i = 1; i < prices.size(); ++i) {
			if (prices[i] < minPrice)minPrice = prices[i];	//更新最小价格

			if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {	//在最小价格 与最小价格加上手续费之间 不能卖出
				continue;
			}

			if (prices[i] > minPrice + fee)	{	//价格大于最小价格加上手续费 可以获利
				result += prices[i] - minPrice - fee;
				minPrice = prices[i] - fee;
			}
		}
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

968. 监控二叉树

代码

class Solution {	//968. 监控二叉树	
	//0为无覆盖 1为有监控 2为有覆盖 空节点视为2 后序遍历二叉树 自底向上开始放置摄像头，因为要让叶子节点的父节点放置摄像头，总数才尽可能少 
	//如果当前节点的左孩子和右孩子都为2，那么返回0，表示该节点未覆盖
	//如果当前节点的左孩子或右孩子为0，那么表示应该在当前节点放置摄像头，result++，返回1
	//如果当前节点的左孩子和右孩子为1，说明该节点被覆盖，返回2
	//最后看根节点有没有被覆盖，未被覆盖就再放置一个摄像头
public:
	int result = 0;
	int traversal(TreeNode* cur) {
		if (cur == nullptr)return 2;

		int left = traversal(cur->left);
		int right = traversal(cur->right);

		if (left == 2 && right == 2)return 0;
		
		if (left == 0 || right == 0) {
			result++;
			return 1;
		}

		if (left == 1 || right == 1)return 2;

		return -1;
	}
	int minCameraCover(TreeNode* root) {
		if (traversal(root) == 0)result++;
		return result;
	}
};
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

参考资料：

代码随想录