贪心3
贪心算法通过每步选择局部最优解，期望最终达到全局最优，适用于最优化和排序问题。
贪心3
贪心3
581. 最短无序连续子数组
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
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
class Solution {
public:
static int findUnsortedSubarray(vector<int> &nums) {
int n = nums.size();
// 从左往右，记录最右边的一个不满足左边的最大值小于等于当前值的位置
int right = -1;
int maxVal = INT_MIN;
for (int i = 0; i < n; i++) {
if (maxVal > nums[i]) right = i;
maxVal = max(maxVal, nums[i]);
}
// 从右往左，记录最左边的一个不满足右边的最小值大于等于当前值的位置
int left = n;
int minVal = INT_MAX;
for (int i = n - 1; i >= 0; i--) {
if (minVal < nums[i]) left = i;
minVal = min(minVal, nums[i]);
}
return max(0, right - left + 1);
}
};
632. 最小区间
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
#include <iostream>
#include <vector>
#include <set>
#include <climits>
using namespace std;
// 结构体表示一个元素的信息
struct Node {
int v; // 值
int i; // 值来自第 i 个数组
int j; // 值在第 i 个数组中的下标
Node(int val, int row, int col) : v(val), i(row), j(col) {}
// 为了使用 set 排序，需要定义比较函数
bool operator<(const Node &other) const {
// 如果值不同，按值升序排列
// 如果值相同，按数组下标 i 排序，避免值相同的元素被覆盖
return v != other.v ? v < other.v : i < other.i;
}
};
class Solution {
public:
// 时间复杂度 O(n * log k)，n 是所有数字总数，k 是数组数量
// 每个 num[i] 数组都是有序的
vector<int> smallestRange(vector<vector<int>> &nums) {
int k = nums.size();
set<Node> s; // 使用有序集合，自动按 Node 排序
// 初始化，将每个数组的第一个元素放入 set
for (int i = 0; i < k; ++i) {
s.insert(Node(nums[i][0], i, 0));
}
int range = INT_MAX; // 当前最小区间的宽度
int start = 0; // 最小区间的左端点
int end = 0; // 最小区间的右端点
while (s.size() == k) {
auto minNode = *s.begin(); // 当前区间最小值
auto maxNode = *s.rbegin(); // 当前区间最大值
// 如果当前区间更小，则更新答案
if (maxNode.v - minNode.v < range) {
range = maxNode.v - minNode.v;
start = minNode.v;
end = maxNode.v;
}
// 弹出最小值节点
s.erase(s.begin());
// 如果该数组还有下一个元素，则插入到 set 中
if (minNode.j + 1 < nums[minNode.i].size()) {
s.insert(Node(nums[minNode.i][minNode.j + 1], minNode.i, minNode.j + 1));
}
}
return {start, end};
}
};
组团买票
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>
// 组团买票
// 景区里一共有m个项目，景区的第i个项目有如下两个参数：
// game[i] = { Ki, Bi }，Ki、Bi一定是正数
// Ki代表折扣系数，Bi代表票价
// 举个例子 : Ki = 2, Bi = 10
// 如果只有1个人买票，单张门票的价格为 : Bi - Ki * 1 = 8
// 所以这1个人游玩该项目要花8元
// 如果有2个人买票，单张门票的价格为 : Bi - Ki * 2 = 6
// 所以这2个人游玩该项目要花6 * 2 = 12元
// 如果有5个人买票，单张门票的价格为 : Bi - Ki * 5 = 0
// 所以这5个人游玩该项目要花5 * 0 = 0元
// 如果有更多人买票，都认为花0元(因为让项目倒贴钱实在是太操蛋了)
// 于是可以认为，如果有x个人买票，单张门票的价格为 : Bi - Ki * x
// x个人游玩这个项目的总花费是 : max { x * (Bi - Ki * x), 0 }
// 单位一共有n个人，每个人最多可以选1个项目来游玩，也可以不选任何项目
// 所有员工将在明晚提交选择，然后由你去按照上面的规则，统一花钱购票
// 你想知道自己需要准备多少钱，就可以应付所有可能的情况，返回这个最保险的钱数
// 数据量描述 :
// 1 <= M、N、Ki、Bi <= 10^5
using namespace std;
// 项目信息结构体
struct Game {
int ki; // 折扣系数
int bi; // 原始票价
int people; // 当前已选这个项目的人数
Game(int k, int b) : ki(k), bi(b), people(0) {}
// 如果再来一个人，这个项目能“省”多少钱（贡献值）
int earn() const {
// bi - (people + 1) * ki: 当前的人，门票原价减少了，当前的门票价格
// people * ki: 当前人的到来，之前的所有人，门票价格都再减去 ki
return bi - (people + 1) * ki - people * ki;
}
// 为了能在 priority_queue 中比较，定义比较运算符
// 大根堆：earn 值高的排前面
bool operator<(const Game &other) const {
return earn() < other.earn();
}
};
// 暴力递归（验证用），时间复杂度 O((m+1)^n)
int f(int i, int n, int m, vector<vector<int>> &games, vector<int> &cnts) {
if (i == n) {
int res = 0;
for (int j = 0; j < m; ++j) {
int k = games[j][0];
int b = games[j][1];
int x = cnts[j];
res += max((b - k * x) * x, 0);
}
return res;
} else {
int res = f(i + 1, n, m, games, cnts); // 不选任何项目
for (int j = 0; j < m; ++j) {
cnts[j]++;
res = max(res, f(i + 1, n, m, games, cnts)); // 尝试选第 j 个项目
cnts[j]--;
}
return res;
}
}
int enough1(int n, vector<vector<int>> &games) {
int m = games.size();
vector<int> cnts(m, 0);
return f(0, n, m, games, cnts);
}
// 正式解法，时间复杂度 O(n * log m)
int enough2(int n, vector<vector<int>> &games) {
// 当前再来一个人的话，去堆顶的项目对景区来说最赚钱
priority_queue<Game> heap;
// 初始化所有项目放入堆中
for (const auto &g: games) {
heap.emplace(g[0], g[1]);
}
int res = 0;
// 把进来的人都分配到当前新加一个人会对景区最赚钱的项目
for (int i = 0; i < n; ++i) {
Game top = heap.top();
// 再分人已经不增加花费了，直接退出
if (top.earn() <= 0) break;
heap.pop();
res += top.earn(); // 加上当前人的花费
top.people++; // 当前项目多了一个人
heap.push(top); // 更新后重新加入堆中
}
return res;
}
// 随机生成项目数据，用于测试
vector<vector<int>> randomGames(int m, int v) {
vector<vector<int>> res(m, vector<int>(2));
for (int i = 0; i < m; ++i) {
res[i][0] = rand() % v + 1;
res[i][1] = rand() % v + 1;
}
return res;
}
// 测试主函数
int main() {
int N = 8;
int M = 8;
int V = 20;
int testTimes = 2000;
cout << "测试开始" << endl;
for (int i = 1; i <= testTimes; ++i) {
int n = rand() % N + 1;
int m = rand() % M + 1;
vector<vector<int>> games = randomGames(m, V);
int res1 = enough1(n, games);
int res2 = enough2(n, games);
if (res1 != res2) {
cout << "出错了！" << endl;
return 1;
}
if (i % 100 == 0) {
cout << "测试到第" << i << "组" << endl;
}
}
cout << "测试结束" << endl;
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
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <climits>
// 平均值最小累加和
// 给定一个数组arr，长度为n
// 再给定一个数字k，表示一定要将arr划分成k个集合
// 每个数字只能进一个集合
// 返回每个集合的平均值都累加起来的最小值
// 平均值向下取整
// 1 <= n <= 10^5
// 0 <= arr[i] <= 10^5
// 1 <= k <= n
using namespace std;
// 暴力递归函数（验证用），时间复杂度 O(k^n)
int f(const vector<int> &arr, int i, vector<int> &sum, vector<int> &cnt) {
if (i == arr.size()) {
int res = 0;
for (int j = 0; j < sum.size(); ++j) {
if (cnt[j] == 0) return INT_MAX;
res += sum[j] / cnt[j]; // 向下取整
}
return res;
} else {
int res = INT_MAX;
for (int j = 0; j < sum.size(); ++j) {
sum[j] += arr[i];
cnt[j]++;
res = min(res, f(arr, i + 1, sum, cnt));
sum[j] -= arr[i];
cnt[j]--;
}
return res;
}
}
// 暴力方法（验证用）
int minAverageSum1(const vector<int> &arr, int k) {
vector<int> sum(k, 0);
vector<int> cnt(k, 0);
return f(arr, 0, sum, cnt);
}
// 正式方法，时间复杂度 O(n * log n)
int minAverageSum2(vector<int> arr, int k) {
sort(arr.begin(), arr.end()); // 升序排序
int res = 0;
// 前 k - 1 个最小值单独成组，平均值向下取整就是自身
for (int i = 0; i < k - 1; ++i) res += arr[i];
int sum = 0;
for (int i = k - 1; i < arr.size(); ++i)
sum += arr[i];
// 剩下所有人组成一个集合，平均值向下取整
res += sum / (arr.size() - k + 1);
return res;
}
// 随机数组生成器（测试用）
vector<int> randomArray(int n, int v) {
vector<int> res(n);
for (int i = 0; i < n; ++i)
res[i] = rand() % v;
return res;
}
// 主函数：对数器验证
int main() {
int N = 8; // 最大数组长度
int V = 10000; // 数值上限
int testTimes = 2000;
cout << "测试开始" << endl;
for (int i = 1; i <= testTimes; ++i) {
int n = rand() % N + 1;
vector<int> arr = randomArray(n, V);
int k = rand() % n + 1;
int res1 = minAverageSum1(arr, k);
int res2 = minAverageSum2(arr, k);
if (res1 != res2) {
cout << "出错了！" << endl;
return 1;
}
if (i % 100 == 0)
cout << "测试到第" << i << "组" << endl;
}
cout << "测试结束" << endl;
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
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdlib>
// 执行所有任务的最少初始电量
// 每一个任务有两个参数，需要耗费的电量、至少多少电量才能开始这个任务
// 返回手机至少需要多少的初始电量，才能执行完所有的任务
using namespace std;
// 交换任务顺序
void swapJobs(vector<vector<int>> &jobs, int i, int j) {
swap(jobs[i], jobs[j]);
}
// 暴力递归：尝试所有排列，找出所需最少初始电量
int f1(vector<vector<int>> &jobs, int n, int i) {
if (i == n) {
int res = 0;
for (const auto &job: jobs) {
// job[0]: 耗电量，job[1]: 最少启动电量
res = max(job[1], res + job[0]);
}
return res;
} else {
int res = INT_MAX;
for (int j = i; j < n; ++j) {
swapJobs(jobs, i, j);
res = min(res, f1(jobs, n, i + 1));
swapJobs(jobs, i, j);
}
return res;
}
}
// 暴力递归入口
int atLeast1(vector<vector<int>> jobs) {
return f1(jobs, jobs.size(), 0);
}
// 贪心算法：根据(耗电量 - 至少启动电量)降序排序
int atLeast2(vector<vector<int>> jobs) {
sort(jobs.begin(), jobs.end(), [](const vector<int> &a, const vector<int> &b) {
return (b[0] - b[1]) < (a[0] - a[1]);
});
int res = 0;
for (const auto &job: jobs) {
res = max(res + job[0], job[1]);
}
return res;
}
// 随机生成任务
vector<vector<int>> randomJobs(int n, int v) {
vector<vector<int>> jobs(n, vector<int>(2));
for (int i = 0; i < n; ++i) {
jobs[i][0] = rand() % v + 1;
jobs[i][1] = rand() % v + 1;
}
return jobs;
}
int main() {
int N = 10;
int V = 20;
int testTimes = 2000;
cout << "测试开始" << endl;
for (int i = 1; i <= testTimes; ++i) {
int n = rand() % N + 1;
vector<vector<int>> jobs = randomJobs(n, V);
vector<vector<int>> jobsCopy = jobs;
int res1 = atLeast1(jobs);
int res2 = atLeast2(jobsCopy);
if (res1 != res2) {
cout << "出错了！" << endl;
}
if (i % 100 == 0) {
cout << "测试到第" << i << "组" << endl;
}
}
cout << "测试结束" << endl;
return 0;
}
两个0和1数量相等区间的最大长度
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
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cstdlib>
// 两个0和1数量相等区间的最大长度
// 给出一个长度为n的01串，现在请你找到两个区间
// 使得这两个区间中，1的个数相等，0的个数也相等
// 这两个区间可以相交，但是不可以完全重叠，即两个区间的左右端点不可以完全一样
// 现在请你找到两个最长的区间，满足以上要求
// 返回区间最大长度
using namespace std;
// 暴力方法：枚举所有子数组组合，统计每种(0,1)数量出现次数
int len1(const vector<int> &arr) {
unordered_map<int, unordered_map<int, int>> map;
int n = arr.size();
for (int i = 0; i < n; ++i) {
int zero = 0, one = 0;
for (int j = i; j < n; ++j) {
if (arr[j] == 0) zero++;
else one++;
map[zero][one]++;
}
}
int res = 0;
for (const auto &zero_pair: map) {
for (const auto &one_pair: zero_pair.second) {
if (one_pair.second > 1) {
res = max(res, zero_pair.first + one_pair.first);
}
}
}
return res;
}
// 优化方法：只找最远两个相同数字的位置作为可能组成最大区间的两端
int len2(const vector<int> &arr) {
int leftZero = -1, rightZero = -1;
int leftOne = -1, rightOne = -1;
int n = arr.size();
// 找到第一个和最后一个 0 的位置
for (int i = 0; i < n; ++i) {
if (arr[i] == 0) {
leftZero = i;
break;
}
}
for (int i = n - 1; i >= 0; --i) {
if (arr[i] == 0) {
rightZero = i;
break;
}
}
// 找到第一个和最后一个 1 的位置
for (int i = 0; i < n; ++i) {
if (arr[i] == 1) {
leftOne = i;
break;
}
}
for (int i = n - 1; i >= 0; --i) {
if (arr[i] == 1) {
rightOne = i;
break;
}
}
int p1 = (leftZero != -1 && rightZero != -1) ? (rightZero - leftZero) : 0;
int p2 = (leftOne != -1 && rightOne != -1) ? (rightOne - leftOne) : 0;
return max(p1, p2);
}
// 生成随机 0-1 数组
vector<int> randomArray(int len) {
vector<int> res(len);
for (int i = 0; i < len; ++i) {
res[i] = rand() % 2;
}
return res;
}
int main() {
int N = 500;
int testTimes = 2000;
cout << "测试开始" << endl;
for (int i = 1; i <= testTimes; ++i) {
int n = rand() % N + 2;
vector<int> arr = randomArray(n);
int res1 = len1(arr);
int res2 = len2(arr);
if (res1 != res2) {
cout << "出错了!" << endl;
}
if (i % 100 == 0) {
cout << "测试到第" << i << "组" << endl;
}
}
cout << "测试结束" << endl;
return 0;
}
本文由作者按照 CC BY 4.0 进行授权