double Week Contest 9

Posted on | In , | |
Words count in article: 1.1k | Reading time ≈ 4

最多可以买到的苹果数量

楼下水果店正在促销，你打算买些苹果，arr[i] 表示第 i 个苹果的单位重量。

你有一个购物袋，最多可以装 5000 单位重量的东西，算一算，最多可以往购物袋里装入多少苹果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxNumberOfApples(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int ret = 0 ;
        int sum = 0;
        for(int i=0; i<arr.size(); i++)
        {
            sum += arr[i];
            if(sum > 5000)
                return ret;
            ret++;
        }
        return ret;
    }
};

进击的骑士

一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上，你的 骑士 驻扎在坐标为 [0, 0] 的方格里。

骑士的走法和中国象棋中的马相似，走 “日” 字：即先向左（或右）走 1 格，再向上（或下）走 2 格；或先向左（或右）走 2 格，再向上（或下）走 1 格。

每次移动，他都可以按图示八个方向之一前进。

现在，骑士需要前去征服坐标为 [x, y] 的部落，请你为他规划路线。

最后返回所需的最小移动次数即可。本题确保答案是一定存在的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
  int minKnightMoves(int x, int y) {
    vector<vector<int>> M(800, vector<int>(800, -1));
    M[300][300] = 0;
    queue<pair<int, int>> Q;
    Q.push({0, 0});
    int dx[] = {1, 1, 2, 2, -1, -1, -2, -2};
    int dy[] = {2, -2,1, -1, 2, -2, 1, -1};
    while (!Q.empty() && M[x+300][y+300] == -1) {
      auto [sx, sy] = Q.front(); Q.pop();
      for (int i = 0; i < 8; i++) {
        int tx = sx + dx[i];
        int ty = sy + dy[i];
        if (abs(tx) + abs(ty) > 300) continue;
        if (M[tx+300][ty+300] != -1) continue;
        M[tx+300][ty+300] = M[sx+300][sy+300] + 1;
        Q.push({tx, ty});
      }
    }
    return M[x+300][y+300];
  }
};

找出所有行中最小公共元素

给你一个矩阵 mat，其中每一行的元素都已经按 递增 顺序排好了。请你帮忙找出在所有这些行中 最小的公共元素。

如果矩阵中没有这样的公共元素，就请返回 -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
class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        for(int i=0; i<mat[0].size(); i++)
        {
            int tmp = mat[0][i];
            int flag = 1;
            for(int j=1; j<mat.size(); j++)
            {
                int z;
                for(z=0; z<mat[j].size(); z++)
                {
                    if(mat[j][z] == tmp)
                        break;
                }
                if(z == mat[j].size())
                {
                    flag = 0;
                    break;
                }
            }
            if(flag == 1)
                return tmp;
            else
                continue;
        }
        return -1;
    }
};

建造街区的最短时间

你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中 blocks[i] = t 意味着第 i 个街区需要 t 个单位的时间来建造。

由于一个街区只能由一个工人来完成建造。

所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。

一个工人再召唤一个工人所花费的时间由整数 split 给出。

注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是 split。

最开始的时候只有 一个 工人，请你最后输出建造完所有街区所需要的最少时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 1：

输入：blocks = [1], split = 1
输出：1
解释：我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。
示例 2：

输入：blocks = [1,2], split = 5
输出：7
解释：我们用 5 个时间单位将这个工人分裂为 2 个工人，然后指派每个工人分别去建造街区，从而时间花费为 5 + max(1, 2) = 7
示例 3：

输入：blocks = [1,2,3], split = 1
输出：4
解释：
将 1 个工人分裂为 2 个工人，然后指派第一个工人去建造最后一个街区，并将第二个工人分裂为 2 个工人。
然后，用这两个未分派的工人分别去建造前两个街区。
时间花费为 1 + max(3, 1 + max(1, 2)) = 4

提示：

  • 1 <= blocks.length <= 1000
  • 1 <= blocks[i] <= 10^5
  • 1 <= split <= 100
//
//贪婪: 挑最小的两个合并(取大值+split)成新节点

class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        multiset<int> vals(blocks.begin(), blocks.end());

        while (vals.size() > 1)
        {
            int minVal = *vals.begin();
            vals.erase(vals.begin());
            int minVal2 = *vals.begin();  //这个一定比前一个大或相等
            vals.erase(vals.begin());
            vals.insert(minVal2 + split);
        }

        return *vals.begin();
    }
};
Donate? comment?