1. 前言
早上兴高采烈起床写周赛，结果写完两题开始坐牢。菜的很。
2. 赛题
LeetCode 第 350 场周赛
2.1 题1
LeetCode 6901. 总行驶距离
2.1.1 题意
卡车两个油箱，耗油1L行驶10km。油箱A耗5L,油箱B给邮箱A油1L。油箱A空后停止行驶，求可行使距离。
2.1.2 分析
开始想O(1)解法，发现这题主要问题在油箱B给了油箱A的油在消耗过后也计算在油箱A的油中。没理清O(1)思路，数据量不大，直接模拟。
1
2.1.3 我的解法
class Solution {
public:
int distanceTraveled(int mainTank, int additionalTank) {
int res = 0;
while(mainTank > 0){// 油箱A还有油
if(mainTank >= 5){
// 油箱A的油可以消耗5L
// 也就是油箱B可以给油箱A油
mainTank -= 5;
res += 50;
if(additionalTank >= 1){
// 前提是油箱B还有油
mainTank++;
additionalTank--;
}
}
else{
// 油箱A的油不足5L
// 直接消耗
res += (mainTank * 10);
mainTank=0;
}
}
return res;
}
};
2.1.4 学习题解反思
我的解法：
时间复杂度O( (m+n)/5 ), （m,n为A、B油箱中的油量
空间复杂度O(1)
学习了一下O(1)解法,这个想法确实好。再加上一些油箱B的可补充量就可以算出总耗油量。
消耗5 升油 → 补充 1 升油，相当于花费 4 升油
2.2 题2
LeetCode 6890. 找出分区值
2.2.1 题意
将原数组分为非空两份，求第一份中最大值和第二份中最小值的差的绝对值最小的结果
2.2.2 分析
看一下数据，复杂度大概在O(nlogn)级别。
2 1
这个时间复杂度级别可以很快想到排序。排序之后对数组切一刀，第一份中最大值和第二份中最小值就是排序后数组相邻的两个数，所以只需要找到排序后相邻两个数的最小差值即可
2.2.3 我的解法
class Solution {
public:
int findValueOfPartition(vectorint>& nums) {
sort(nums.begin(), nums.end()); // 排序
int res = INT_MAX; // 记录结果
int n = nums.size();
for(int i = 1; in; i++){
// 求相邻两个数的差
res = min(res, abs(nums[i]-nums[i-1]));
}
return res;
}
};
2.2.4 学习题解反思
我的解法：
时间复杂度O(nlogn),
空间复杂度O(1)
2.3 题3
LeetCode 6893. 特别的排列
2.3.1 题意
给定一个数组，求满足该条件的排列数：对于每个位置i，这个位置的数能被前一个数整除或者被后一个数整除。
2.3.2 分析
看一下数据，范围很小，时间复杂度可以到O(
n
2
∗
2
n
n^2*2^n
n2∗2n)
2 1
我的思路是把他想象成图，每个数对应一个节点，然后每个边对应整除关系，那么从节点a到节点b并且经过所有点的一种路径，对应上就是一种数组的排列。最后求结果需要求这个图中所有的哈密尔顿回路的数量。（我觉得我这个想法还是很有趣的，但是没什么特别的用）
首先数据集很小，使用状态压缩来存状态信息，递推过程中需要关注的信息有：路径中上一个落点的，以及已访问的点的信息
高16位，表示上一个落点的位置
低16位，为1的位表示已经访问过
思考状态转移
转移到状态j：上一轮中所有的可以转移到状态k的和
判断可否转移，需要用到两个状态中存的信息。
2.3.3 我的解法
class Solution {
public:
const int MOD = 1e9 + 7;
long res = 0;
int specialPerm(vectorint>& nums) {
int n = nums.size();
vectorvectorint> > g(n, vectorint>(n, 0) );
// build graph
// 建图
for(int i=0; in; i++){
for(int j=0; jn; j++){
if(i!=j && ( (nums[j]%nums[i]==0) || (nums[i]%nums[j]==0) )){
g[i][j]=1;
}
}
}
// 状压 dp
// 按集合看，不关注顶点，只关注上一个点，和已经走过的点
// dp[i][j] 表示第i步走到状态j有多少种走法
// 状态j中包含了上一个点和已经走过的点的信息
// 高16位，表示上一个落点的位置
// 低16位，为1的位置表示已经访问过
// 想一下递推式
// dp[i][j] = sum(dp[i-1][k] 所有可转移到状态j的状态k)
// 这里其实可以用两个map(滚动数组
vectorunordered_mapint,int> > dp;
// 初始化
unordered_mapint, int> init;
// 把所有顶点情况都初始化为1
for(int i=0; in; i++)
init[(i16) | (1i)] = 1;
dp.emplace_back(init);
// dp
for(int k=1; kn; k++){
auto b = dp.back();
unordered_mapint, int> tmp;
for(auto it=b.begin(); it!=b.end(); it++){
// 遍历所有状态
// 解析出上一个位置，以及已经访问过的位置
int lastPos = (it->first) >> 16;
int vis = (it->first) & 0xffff;
for(int l=0; ln; l++){
if(g[lastPos][l] && ( (vis & (1l)) == 0)){
int index = (l16) | (vis | (1l) );
tmp[index]= (tmp[index]%MOD + ((it->second)%MOD) )%MOD;
}
}
}
dp.emplace_back(tmp);
}
// get answer
for(auto it=dp.back().begin(); it!=dp.back().end(); it++){
if( ( ( (it) -> first ) & 0xffff) == (1n) - 1 )
// 最后所有点都访问过的状态
res = (res%MOD + (it->second)%MOD) %MOD;
}
return res % MOD;
}
};
// [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]
2.3.4 学习题解反思
我的解法：
时间复杂度O(
n
2
∗
2
n
n^2*2^n
n2∗2n),
空间复杂度O(
n
∗
2
n
n*2^n
n∗2n) （这个可以优化到O(
2
n
2^n
2n) )
2.3.5 bug日记
2.3.5.1 复杂度估计错误
我从这题开始坐牢
使用回溯法去求哈密尔顿回路数量，当时估计时间复杂度的时候我估计的是O(
n
2
∗
2
n
n^2*2^n
n2∗2n),因为枚举左右端点，加上回溯法的时间。但实际上他是一个全排列O(n!)，因为每种合理的情况都会遍历到。
错误估计的原因：使用状态压缩（使用14位记录，每一位如果为1表示已经访问，如果为0表示没有访问）来标记是否经过了该点，然后估计了所有的状态数2^n，但是，实际上并非每个状态只访问一次。提交后T了。
2.3.5.2 起点和终点并不重要
在赛后补题的时候，我想到了这几天刚写的题。
但是由于先入为主的觉得无向图，从起点到终点，枚举一半的情况结果乘2可以省时间,导致dp复杂度到了O(
n
4
∗
2
n
n^4*2^n
n4∗2n)(实际会比这小，因为不会枚举到2^n的状态)，只能算到n=12的情况，然后想办法剪枝，针对完全图的情况哈密尔顿通路总数量就是n!，但是还是会有样例过不了。
看了灵茶山艾府的讲解，明白了（by the way 灵神太强了也，10min开始可以看榜单，刚好切出去看题，发现灵神已经全A了)。
灵神的讲解记忆化搜索中重复的状态是没有选的点集，和上一个选的点的下标的元组。也就是起点和终点不重要，重要的是已经走过的集合，以及已经走过的集合的上一个点，所以不需要枚举起点和终点，这样才能有重复状态被利用，时间复杂度O(
n
2
∗
2
n
n^2*2^n
n2∗2n)。
2.4 题4
LeetCode2742. 给墙壁刷油漆
2.4.1 题意
n堵墙，刷墙有对应的时间time和花费cost。2个油漆匠，一个免费用时1可刷1堵墙，一个付费用时和开销对应刷墙的time和cost，且免费油漆匠只在付费油漆匠工作时工作
2.4.2 分析
看一下数据，复杂度大概在O(
n
3
n^3
n3)级别。
1 cost.length == time.length
1 1
先考虑贪心是否可以解，贪心的选择单位时间花销少的墙给付费油漆匠刷。但是如果单位时间花销少，但是他需要的时间长，就可能不是最优解，举一个极限的例子
cost = [1000, 1] time = [10000, 2]
那就考虑动态规划。因为每面墙都有两个选择，免费刷和付费刷。这里很关键的需要记录的信息是可够免费刷墙的时间，和状态息息相关。
dp[i][t] 表示刷到第i面墙，可够免费刷墙时间t 的最小花销
这个t应该要可以为负数范围[-n, n] 长度是2n+1 bias = n-1
(为什么最大免费刷墙的时间是这个？因为只要超过n就表示所有墙都可以免费刷，这在情况中需要做特殊处理。实际上这个负数范围取不到正负n，因为至少一个墙付费刷）
递推式分两个情况
dp[i][t] = dp[i-1][t+1] // 免费刷 免费刷时间-1，价格不变
dp[i][t] = dp[i-1][t-time[i]] + cost[i] // 付费刷，免费刷时间+time 价格+cost
对于特殊情况
特殊情况time[i] 很大 -> 最大免费刷墙时间的开销为cost[i]
（因为设定了最大免费刷墙的时间范围，多余的时间范围没有用）
免费刷的递推相同，付费刷的递归:dp[i][t_max] = cost[i]
初始化情况
dp[0][-1] = 0 // 免费刷
dp[0][time[0]] = cost[0] // 付费刷
还要注意time[0]很大情况的初始化
加上一点点细节，对于正负范围，加上一个偏置n即可。
2.4.3 我的解法
class Solution {
public:
int paintWalls(vectorint>& cost, vectorint>& time) {
// 贪? 单位时间花销少的 -> 时间大
// 如: cost = [1000, 1] time = [10000, 2]
// 组合 1
// 复杂度: n^3
// dp[i][t] 表示刷到第i面墙，可够免费刷墙时间t 的最小花销
// 这个t应该要可以为负数范围[-n, n] 长度是2n+1 bias = n-1
// dp[i][t] = dp[i-1][t+1] // 免费刷
// dp[i][t] = dp[i-1][t-time[i]] + cost[i] // 付费刷
// 特殊情况time[i] 很大 -> 最大免费刷墙时间的开销为cost[i]
// 免费刷的递推相同，付费刷的递归:dp[i][t_max] = cost[i]
// 初始化 dp[0][-1] = 0 // 免费刷
// dp[0][time[0]] = cost[0]
int n = time.size();
// 这里空间多开1，避免递推时越界
vectorvectorint> > dp(n, vectorint> (n*2 + 2, INT_MAX) );
// 初始化
dp[0][n - 1] = 0; // 免费刷
// 付费刷
if(n+time[0] 2 * n +1){
dp[0][n + time[0]] = cost[0];
}
else{
dp[0][2 * n +1] = cost[0];
}
// 递推
for(int i=1; in; i++){
for(int t=0; t(2*n + 1); t++){
dp[i][t] = dp[i-1][t+1]; // 免费刷
if(t >= time[i] && dp[i-1][t-time[i]] != INT_MAX){
// 付费刷
dp[i][t] = min(dp[i][t], dp[i-1][t-time[i]] + cost[i]);
}
}
if(time[i] >= n){
// time[i] 很大
// 如果付费刷直接更新上限
dp[i][2*n + 1] = min( dp[i][2*n + 1], min(dp[i-1][2*n + 1], cost[i]) );
}
}
// 找答案
// 从 0~n 范围找
int res = INT_MAX;
for(int t=n; t2*n+1; t++){
res = min(res, dp[n-1][t]);
}
return res;
}
};
/*
30 51 3
3 1 3
[-10, 10]
[82,30,94,55,76,94,51,82,3,89]
[2, 3, 3, 1, 2, 2, 1, 2,3 ,2]
^ ^ ^
*/
2.4.4 学习题解反思
我的解法：
时间复杂度O(
n
2
n^2
n2),
空间复杂度O(
n
2
n^2
n2)
灵神转化01背包这招太强了，直接不考虑免费刷墙的状态了。学习了。
2.4.5 bug日记
2.4.5.1 初始化
初始化时，忘记了付费刷墙可能有时间time[i]很大的情况
2.4.5.2 范围限制
加上范围限制后，关于time[i]很大的情况处理想了很久。
3. 后记
这次周赛补题补了好久，咱就是说菜哭了。
仅分享自己的想法，有意见和指点非常感谢
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
