5072.最多可以买到的苹果数量
楼下水果店正在促销，你打算买些苹果，arr[i] 表示第 i 个苹果的单位重量。
你有一个购物袋，最多可以装 5000 单位重量的东西，算一算，最多可以往购物袋里装入多少苹果。
示例 1：
1
2
3
| 输入：arr = [100,200,150,1000]
输出：4
解释：所有 4 个苹果都可以装进去，因为它们的重量之和为 1450。
|
示例 2：
1
2
3
| 输入：arr = [900,950,800,1000,700,800]
输出：5
解释：6 个苹果的总重量超过了 5000，所以我们只能从中任选 5 个。
|
提示：
1 <= arr.length <= 10^31 <= arr[i] <= 10^3
解法:贪心
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int maxNumberOfApples(vector<int>& arr) {
sort(arr.begin(),arr.end());
int n=arr.size();
int res=0;
int sum=5000;
for(int i=0;i<n;i++)
{
sum-=arr[i];
if(sum<0)
break;
res++;
}
return res;
}
};
|
5073.进击的骑士
一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上，你的 骑士 驻扎在坐标为 [0, 0] 的方格里。
骑士的走法和中国象棋中的马相似，走 “日” 字：即先向左（或右）走 1 格，再向上（或下）走 2 格；或先向左（或右）走 2 格，再向上（或下）走 1 格。
每次移动，他都可以按图示八个方向之一前进。
现在，骑士需要前去征服坐标为 [x, y] 的部落，请你为他规划路线。
最后返回所需的最小移动次数即可。本题确保答案是一定存在的。
示例 1：
1
2
3
| 输入：x = 2, y = 1
输出：1
解释：[0, 0] → [2, 1]
|
示例 2：
1
2
3
| 输入：x = 5, y = 5
输出：4
解释：[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
|
提示：
解法1：bfs
广度优先搜索，注意判断边界条件，
小技巧：将坐标+300，就全都变成了正数，处理数据更简单
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
| class Solution {
public:
int minKnightMoves(int x, int y) {
int dx[8]={1, 2, 2, 1, -1, -2, -2, -1};
int dy[8]={-2, -1, 1, 2, 2, 1, -1, -2};
bool dist[610][610];
queue<pair<int, int> > que;
x+=300,y+=300;
int res=0;
memset(dist, false, sizeof(dist));
dist[300][300]=true; que.push(make_pair(300, 300));
while(!que.empty())
{
int size=que.size();
for(int i=0;i<size;i++)
{
int nowx=que.front().first, nowy=que.front().second;
que.pop();
if(nowx==x&&nowy==y)
return res;
for (int k=0; k<8; k++)
{
int nx=nowx+dx[k], ny=nowy+dy[k];
if (nx<0 || ny<0 || nx>600 || ny>600||dist[nx][ny]) continue;
dist[nx][ny]=true;
que.push(make_pair(nx, ny));
}
}
res++;
}
return res;
}
};
|
5071.找出所有行中最小公共元素
给你一个矩阵 mat，其中每一行的元素都已经按 递增 顺序排好了。请你帮忙找出在所有这些行中 最小的公共元素。
如果矩阵中没有这样的公共元素，就请返回 -1。
示例：
1
2
| 输入：mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
输出：5
|
提示：
1 <= mat.length, mat[i].length <= 5001 <= mat[i][j] <= 10^4mat[i] 已按递增顺序排列。
解法1：map
map存每一个数字的个数，找到map中数字个数和行数相等的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int smallestCommonElement(vector<vector<int>>& mat) {
map<int,int> m;
int n=mat.size(),ml=mat[0].size();
for(int i=0;i<n;i++)
{
for(int j=0;j<ml;j++)
{
m[mat[i][j]]++;
}
}
for(map<int,int>::iterator ite=m.begin();ite!=m.end();ite++)
{
if(ite->second==n)
return ite->first;
}
return -1;
}
};
|
5091.建造街区的最短时间
你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中 blocks[i] = t 意味着第 i 个街区需要 t 个单位的时间来建造。
由于一个街区只能由一个工人来完成建造。
所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。
一个工人再召唤一个工人所花费的时间由整数 split 给出。
注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是 split。
最开始的时候只有 一个 工人，请你最后输出建造完所有街区所需要的最少时间。
示例 1：
1
2
3
| 输入：blocks = [1], split = 1
输出：1
解释：我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。
|
示例 2：
1
2
3
| 输入：blocks = [1,2], split = 5
输出：7
解释：我们用 5 个时间单位将这个工人分裂为 2 个工人，然后指派每个工人分别去建造街区，从而时间花费为 5 + max(1, 2) = 7
|
示例 3：
1
2
3
4
5
6
| 输入：blocks = [1,2,3], split = 1
输出：4
解释：
将 1 个工人分裂为 2 个工人，然后指派第一个工人去建造最后一个街区，并将第二个工人分裂为 2 个工人。
然后，用这两个未分派的工人分别去建造前两个街区。
时间花费为 1 + max(3, 1 + max(1, 2)) = 4
|
提示：
1 <= blocks.length <= 10001 <= blocks[i] <= 10^51 <= split <= 100
解法1：优先级队列
每次都取最小的两位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int minBuildTime(vector<int>& blocks, int split) {
priority_queue<int> que;
for(auto b:blocks)
{
que.push(-b);
}
while(que.size()>1)
{
int x=-que.top();que.pop();
int y=-que.top();que.pop();
int z=split+y;
que.push(-z);
}
return -que.top();
}
};
|