Problem#1
这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
Solving
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
|
//反悔贪心
//利用大根堆维护一个代价，不断加入时间，若时间超过限制，则比对当前代价和堆中的最高代价，如果当前代价更小，则弹出堆顶，加入当前代价。
vector<vector<int>> c = {{100,200},{200,1300},{1000,1250},{2000,3200}};
int solve(vector<vector<int>>& curses)
{
priority_queue<int> heap;
int curtime = 0;
int n = courses.size();
sort(courses.begin(),courses.end(),[](const auto& a,const auto& b)
{
return a[1] < b[1];
});//注意比较器中取址符和const关键字的使用，这样可以直接调用原函数进行比较而不用复制原函数生成样本进行比较，大大节省空间和时间效率.
for(auto c : courses)
{
if(c[0] + curtime <= c[1])
{
curtime += c[0];
heap.push(c[0]);
}
else
{
if(!heap.empty()&&c[0] < heap.top())
{
curtime -= heap.top();
curtime += c[0];
heap.pop();
heap.push(c[0]);
}
}
}
return (int)heap.size();
}
|
Problem #2
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
vector<int> nums = {1,24,5223,11,2454,88,99};
bool cmp(string s1,string s2)
{
return s1+s2 > s2+s1; //比对两个字符串相连后的ASCII码，降序排序
}
string solve(vector<int>& nums)
{
int n = nums.size();
string str[n];
for(int i=0;i<n;i++)
{
str[i] = to_string(nums[i]);
}
sort(str,str+n,cmp);
if(str[0]=="0") return "0";
string ans = "";
for(int i=0;i<n;i++) ans += str[i];
return ans;
}
|
Problem #3
给定数个线段的左右端点，返回最多的线段重合数量。
Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
vector<vector<int>> meeting = {{0,30},{5,10},{15,20}};
int solve(vector<vector<int>>& meeting)
{
int ans = 0;
int n = meeting.size();
priority_queue<int,vector<int>,greater<int>> q;
sort(meeting[0].begin(),meeting[0].end());
for(int i=0;i<n;i++)
{
int temp = meeting[i][0];
while(!q.empty()&&q.top()<=temp)
{
q.pop();
}
q.push(meeting[i][1]);
ans = max(ans,(int)q.size());
}
return ans;
}
|
Problem #4
给定数个会议的开始时间和结束时间，返回能参加的最多会议个数。
Solving
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
|
void solve()
{
int n;
cin >> n;
vector<array<int,2>> c(n+1);//多维数组用std::vector + std::array;
for(int i=1;i<=n;i++)
{
cin >> c[i][0] >> c[i][1];
}
sort(c.begin(),c.end(),[](const auto& a,const auto& b)
{
return a[1] < b[1];//贪心:按照会议结束时间从小到大排序
});
int cur = -1;
int ans = 0;
for(int i=1;i<=n;i++)
{
if(cur <= c[i][0])
{
ans++;
cur = c[i][1];
}
}
cout << ans;
}
|
Problem #5
公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCost_i, bCost_i] 。第 i 人飞往 a 市的费用为 aCost_i ，飞往 b 市的费用为 bCost_i。
返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。
Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
vector<vector<int>> cost = {{259,770},{448,54},{926,667},{184,139},{840,118},{577,469}};
int solve(vector<vector<int>>& costs)
{
int n = costs.size();
int diff[n];
int sum = 0;
for(int i=0;i<n;i++)
{
diff[i] = costs[i][1] - costs[i][0];//计算从a地调往b地所支付的差值
sum += costs[i][0];//sum代表初始时所有人都去A地
}
sort(diff,diff+n);//贪心 从小到大排序
for(int i=0;i<n/2;i++) sum += diff[i];//让调往b地花费费用最少的前一半人去b地;
return sum;
}
|
Problem #6
合并石子问题
Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
void solve()
{
int n;
cin >> n;
priority_queue<int,vector<int>,greater<int>> heap;
for(int i=1;i<=n;i++)
{
int x;
cin >> x;
heap.push(x);
}
int ans = 0;
int sum = 0;
while(heap.size() > 1)
{
sum = heap.top();
heap.pop();
sum += heap.top();
heap.pop();
ans += sum;
heap.push(sum);
}
cout << ans;
}
|
Problem #7
给定数个会议的开始和结束时间 ，在规定时间段只需选择一天参加会议，返回能最大参加的会议数量。
Solving
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
|
class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(),events.end(),[](const auto& a,const auto& b)
{
return a[0] < b[0];
});
int MIN = 0;
int n = events.size();
int MAX = 0;
for(auto a : events)
{
MAX = max(MAX,a[1]);
}
int i = 0;//一个指针，用于把相同开始时间的会议放入小根堆
int ans = 0;
priority_queue<int,vector<int>,greater<int>> heap;
for(int day = MIN;day <= MAX;day++)
{
//将所有同一天的会议的结束时间放入小根堆
while(i < n&&events[i][0]==day)
{
heap.push(events[i][1]);
i++;
}
//清空到当天 之前会过期的会议
while(!heap.empty()&&day > heap.top())
{
heap.pop();
}
//另外留在小根堆里的就为当天可以考虑开的会议
//优先考虑开堆顶的会议，因为它结束时间最小，最紧迫
if(!heap.empty())
{
heap.pop();
ans++;
}
}
return ans;
}
};
|