2022 年度杭州未来科技城数字经济人才编程大赛

前三题基本上常规题目，感觉最后一题确实有一点思路比较难想到，还是卡在了关键的一点上。

zj-future01. 信号接收

题目

假设有若干信号发射源定时发送信号， signals[i] = [start, end) 表示第 i 个信号发射源运作的开始时间 start 和停止时间 end 。

若调度员的接收设备同一时刻仅能接收一个发射源发出的信号，请判断调度员能否收到所有发射源的完整信号。

注意：只有接收了一个信号源从开始到结束的所有信号才算完整信号。

示例 1：

输入：signals = [[0,40],[10,15],[20,30]]
输出：false
解释：
时间 [10,15) 内不能同时接收信号 0 和信号 1，
时间 [20,30) 内不能同时接收信号 0 和信号 2。

示例 2：

输入：signals = [[2,8],[8,14]]
输出：true

示例 3：

输入：signals = [[9,12],[2,3]]
输出：true

提示：

0 <= signals.length <= 104
signals[i].length == 2
0 <= starti < endi <= 106

地址

https://leetcode.cn/contest/zj-future2022/problems/WYKGLO/

题意

排序、二分查找、线段树

思路

感觉至少有三种解法，排序，二分查找，线段树。

排序：按照从小到大依次插入区间，并同时记录已经插入区间的最右值 $r$, 此时如果检测到当前插入的区间范围小于 $r$ 则认为区间重复，返回 $\texttt{false}$。
线段树：感觉就是普通的动态线段树即可，每次在树上对区间进行标记，如果发现出现已经标记的区间则返回，否则则插入新的区间

复杂度分析：

时间复杂度：$O(n \log n))$, 其中 $n$ 为区间的长度。
空间复杂度：$O(n)$，其中 $n$ 为区间的长度。

代码

class Solution {
public:
    bool canReceiveAllSignals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end());
        int last = -1;
        for (int i = 0; i < n; i++) {
            if (intervals[i][0] < last) {
                return false;
            }
            last = intervals[i][1];
        }
        return true;
    }
};

zj-future02. 黑白棋游戏

题目

现有一个黑白棋游戏，初始时给出一排棋子，记作数组 chess，其中白色棋子记作 0，黑色棋子记作 1。用户可以每次交换任意位置的两颗棋子的位置。

为了使得所有黑色棋子相连，请返回最少需要交换多少次。

示例 1:

输入: chess = [1,0,1,0,1,0]
输出: 1
解释: 
有四种可能的方法可以把所有的 1 组合在一起：
[1,1,1,0,0,0]，交换 1 次；
[0,1,1,1,0,0]，交换 2 次；
[0,0,1,1,1,0]，交换 1 次；
[0,0,0,1,1,1]，交换 2 次。
所以最少的交换次数为 1。

示例 2:

输入：chess = [0,0,0,1,0]
输出：0
解释： 
由于数组中只有一个 1，所以不需要交换。

示例 3:

输入：chess = [1,1,0,1,0,1,0,0,1,0,1]
输出：2
解释：
最佳方案为 [1,1,1,1,1,1,0,0,0,0,0]，
因此返回最少交换 2 次

提示:

1 <= chess.length <= 105
chess[i] == 0 或 1.

地址

https://leetcode.cn/contest/weekly-contest-299/problems/count-number-of-ways-to-place-houses/

题意

滑动窗口 + 前缀和

思路

我们统计棋盘中 $1$ 的总数为 $x$，则我们可以知道 $1$ 的子序列长度为 $x$，我们依次统计连续的长度为 $x$ 的子数组中 $1$ 的最大数目即可，依次尝试将窗口为 $x$ 的子数组全部变为 $1$ 的次数。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(n)$，可以将其优化到 $O(1)$。

代码

class Solution {
public:
    int minSwaps(vector<int>& chess) {
        int n = chess.size();
        int tot = 0;
        vector<int> sum(n + 1);
        for (int i = 0; i < n; i++) {
            if(chess[i] == 1) {
                tot++;
            }
            sum[i + 1] = sum[i] + chess[i];
        }
        int ans = n;
        for (int i = tot; i <= n; i++) {
            ans = min(ans, tot - (sum[i] - sum[i-tot]));
        }
        return ans;
    }
};

zj-future03. 快递中转站选址

题目

某区域地图记录在 k 二维数组 area，其中 0 表示空地，1 表示快递分发点。

若希望选取一个地点设立中转站，使得中转站至各快递分发点的「曼哈顿距离」总和最小。请返回这个最小的距离总和。

注意：

曼哈顿距离：distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|
所有位置均可作为快递中转站的设立点。

示例 1：

输入: area = [[0,1,0,0,0],[0,0,0,0,1],[0,0,1,0,0]]
输出: 5 
解释: 三个快递分发点分别位于(0,1)，(1,4) 和 (2,2):
     (1,2) 是最佳的中转站选址，总距离为 2 + 2 + 1 = 5。

示例 2:

输入: area = [[1,1],[1,1]]
输出: 4
解释: (0,0) 是最佳的中转站选址之一，总距离为 0 + 1 + 1 + 2 = 4。

提示:

m == area.length
n == area[i].length
1 <= m, n <= 200
area[i][j] == 0 或 1.
area 中至少有两个快递分发点

地址

https://leetcode.cn/contest/zj-future2022/problems/kflZMc/

题意

中位数

思路

首先我们观察一下，求曼哈顿距离时，纵坐标与横坐标是分开的，我们可以分开来求，首先记录所有分支点的横坐标为 $v$ 与纵坐标 $h$, 我们分别来求出目标中转站的行数与列数。我们将 $v$ 与 $h$ 都进行排序，我们可以知道在一个排序的数组中中位数距离其他元素的距离之和最小，因此目标终点站的坐标为 $(median(v), median(h))$，然后我们依次求出所有分支到目标点的距离之和即可。
复杂度分析：

时间复杂度：$O(n^2)$, $n$ 表示给定的天数，可以优化到 $O(n)$ 的时间复杂度。
空间复杂度：$O(n)$，$n$ 表示给定的天数。

代码

class Solution {
public:
    int buildTransferStation(vector<vector<int>>& area) {
        int m = area.size();
        int n = area[0].size();
        vector<int> ver;
        vector<int> hec;
        vector<pair<int,int>> arr;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (area[i][j] == 1) {
                    ver.emplace_back(i);
                    hec.emplace_back(j);
                }
            }
        }
        int ans = 0;
        int k = ver.size();
        sort(ver.begin(), ver.end());
        sort(hec.begin(), hec.end());
        int x = ver[k/2];
        int y = hec[k/2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (area[i][j] == 1) {
                    ans += abs(x - i) + abs(y - j);
                }
            }
        }
        return ans;
    }
};

zj-future04. 门店商品调配

题目

某连锁店开设了若干门店，门店间允许进行商品借调以应对暂时性的短缺。本月商品借调的情况记于数组 distributions，其中 distributions[i] = [from,to,num]，表示从 from 门店调配了 num 件商品给 to 门店。

若要使得每一个门店最终借出和借入的商品数量相同，请问至少还需要进行多少次商品调配。

注意：一次商品调配以三元组 [from, to, num] 表示，并有 from ≠ to 且 num > 0。

示例 1：

输入：distributions = [[0,1,5],[1,2,10],[2,0,5],[2,1,1]]
输出：1
解释：
商店 0 给商店 1 五件商品；
商店 1 给商店 2 十件商品；
商店 2 给商店 0 五件商品；
商店 2 给商店 1 一件商品。
此时商店 1 少了 4 件商品，商店 2 多了 4 件商品，

因此仅需一次商品调配，商店 2 给商店 1 四件商品，即可满足每个门店借出和借入商品数量相同：
商店 0 借出和借入的商品数量均为 5；
商店 1 借出和借入的商品数量均为 10；
商店 2 借出和借入的商品数量均为 10。

示例 2：

输入：distributions = [[0,1,5],[1,4,5],[4,0,5]]
输出：0
解释：
此时各商店借入和借出的商品数量均相等，无需额外的商品调配。

提示：

1 <= distributions.length <= 8
distributions[i].length == 3
0 <= fromi, toi < 12
fromi != toi
1 <= numi <= 100

地址

https://leetcode.cn/contest/zj-future2022/problems/NBCXIp/

题意

动态规划

思路

题目中最关键的一点需要说明下，如果知道这个关键点，则这个题目比较容易，否则还是还是挺难的。对于一个集合 $S$，如果集合 $S$ 且除空集以外的任意子集 $S^{‘}$ 满足子集中的所有元素的和 $\sum(S^{‘}) \neq 0$，此时将集合 $S$ 变为 $0$ 的最小调配次数为 $|S| - 1$。根据以上分析则我们可以知道如下：

设 $dp[mask]$ 表示以 $mask$ 代表的集合变为 $0$ 最小调配次数，则此时 $i = mask \oplus j$，则此时满足 $i | j = mask$, 且满足 $sum(mask) = 0, sum(i) = 0, sum(j) = 0$ 此时我们可以知道 $dp[mask] = \min(dp[mask], dp[i] + dp[j])$
我们依次检测 $mask$ 的子集即可。

复杂度分析：

时间复杂度：$3^n$，$n$ 表示商店的数量。
空间复杂度：$2^n$，$n$ 表示商店的数量。

代码

class Solution {
public:
    int minTransfers(vector<vector<int>>& distributions) {
        int n = distributions.size();
        int k = 12;
        vector<int> arr(k);
        vector<int> sum(1 << k);
        vector<int> dp(1 << k, k);
        for (auto v :  distributions) {
            int from = v[0], to = v[1], num = v[2];
            arr[from] -= num;
            arr[to] += num;
        }
        for (int i = 1; i < (1 << k); i++) {
            for (int j = 0; j < k; j++) {
                if (i & (1 << j)) {
                    sum[i] += arr[j];
                }
            }
            if (sum[i] == 0) {
                dp[i] = __builtin_popcount(i) - 1;
            }
        }
        
        dp[0] = 0;
        for (int i = 1; i < (1<<k); i++) {
            if (sum[i] == 0) {
                for (int j = i; j != 0; j = (j - 1) & i) {
                    if (sum[j] == 0) {
                        dp[i] = min(dp[i], dp[j] + dp[i^j]);
                    }
                }
            }
        }
        return dp[(1<<k) - 1];
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode biweekly contest 82 leetcode contest 300 →

扫描二维码，分享此文章