成立网站是不是需要先成立公司,企业网站 生成html,门户网站建设的作用及意义,海南网络推广评估题目列表 6901. 总行驶距离
6890. 找出分区值
6893. 特别的排列
6447. 给墙壁刷油漆
一、总行驶距离 很显然#xff0c;这题单纯就是一道数学应用题#xff0c;我们要明白最关键的一点 #xff1a;只有当mainTank5并且additionalTank0时#xff0c;才能发生副油…题目列表 6901. 总行驶距离
6890. 找出分区值
6893. 特别的排列
6447. 给墙壁刷油漆
一、总行驶距离 很显然这题单纯就是一道数学应用题我们要明白最关键的一点 只有当mainTank5并且additionalTank0时才能发生副油箱的油转移到主油箱代码如下
int distanceTraveled(int mainTank, int additionalTank){int ans0;while(mainTank/5){//这一条件等价于mainTank5ans50;mainTank-5;if(additionalTank1){mainTank;additionalTank--;}}ansmainTank*10;//记得加上主油箱中剩余的油所能跑的路程return ans;
}
二、找到分区值 这题其实题目看懂就不算很难就是让你将nums数组拆成俩个数组找到第一个数组的max第二个数组的min返回max和min的最小差值乍一看这题好像需要枚举所有可能的拆分方法但仔细看一下元素的个数范围你就会知道这不现实那么我们该怎么做
首先我们可以明确的是我们可以通过分配数组元素将任何一个数通过最大值或最小值拿出来那么我们可不可以通过分配数组元素将任意两个数通过最大值和最小值的形式拿出来
假设能这样操作那么该问题就会变成找到两个数的差值最小的问题而后面一个问题解决起来就会很容易那么到底能不能这么操作呢
我们假设原始数组中的两个数为x,yxy,分成的两个数组分别是数组A和数组B我们将x和大于y的数全部放到数组A将剩余的数全部放入数组B那么数组A的最小值就是x数组B的最大值就是y很显然我们能够选取出任意xy
代码如下
int cmp(int*p1,int*p2){return *p1-*p2;
}
int findValueOfPartition(int* nums, int numsSize){qsort(nums,numsSize,sizeof(int),cmp);int ansINT_MAX;for(int i1;inumsSize;i){if(nums[i]-nums[i-1]ans){ansnums[i]-nums[i-1];}}return ans;
}
三、特别的排列 这题的思路其实不是很难只要会回溯就能做出来但是会超时得用记忆化搜索减少时间复杂度或者直接用递推。
讲一下这类回溯的基本思路首先要有数组记录数字有没有被使用过因为需要考虑数字所在的位置问题然后不断dfs找到适合当前位置的数字直到将所有的数字都选上记入答案 最后返回
这里的思路说的比较简单具体的可以看该题的代码的逻辑
//注意这是正常的回溯代码---会超时
const int MOD1e97;//题目要求答案取模为了防止数字超出int的范围我们将所有计算结果都取模
int* visited;//记录数字是否被使用
int dfs(int i,int depth,int n,int* nums){//i是前一个数的下标depth记录用了几个数n代表数的个数nums数组if(depthn){return 1;//返回1代表找到一种组合方法}int res0;for(int j0;jn;j){if(!visited[j](nums[i]%nums[j]0||nums[j]%nums[i]0)){visited[j]1;res(resdfs(j,depth1,n,nums))%MOD;visited[j]0;}}return res%MOD;
}
int specialPerm(int* nums, int numsSize){int nnumsSize;int ans0;visited(int*)malloc(sizeof(int)*n);memset(visited,0,sizeof(int)*n);for(int i0;in;i){visited[i]1;ans(ansdfs(i,1,n,nums))%MOD;visited[i]0;}free(visited);return ans;
}
好写到这一步我们会发现超时这里超时的原因和求较大值的斐波那契数列一样相同的递归进行太多次我们需要用数组记录我们已经计算过的dfs这样之后我们在需要时就不用计算直接返回从而减少时间复杂度
而这题的难点在于我们需要进行状态压缩之后才能进行记忆化搜索而状态压缩在本题中就是将visited数组用二进制的数来表示
举个栗子 状态压缩后的代码如下
//依旧会超时但空间复杂度降低
const int MOD1e97;
int visited;
int dfs(int i,int n,int* nums){if(visited0){//visited0,代表所有的数都被使用return 1;}int res0;for(int j0;jn;j){if((visited(1j))(nums[i]%nums[j]0||nums[j]%nums[i]0)){visited^(1j);res(resdfs(j,n,nums))%MOD;visited^(1j);}}return res%MOD;
}
int specialPerm(int* nums, int numsSize){int nnumsSize;int ans0;visited(1n)-1;for(int i0;in;i){visited^(1i);ans(ansdfs(i,n,nums))%MOD;visited^(1i);}return ans;
}
下面我们只要有一个数组来储存已经计算过的dfs从而实现记忆化搜索就行但这个数组的形状一维二维...大小是什么呢
这里我们只要看dfs函数是由几个关键的参数决定的就行(因为dfs其实就是在求某种状态我们要建立数组储存状态肯定是看共多少种状态来决定数组的形状大小而状态是由参数决定的所以我们看参数)很显然nums是辅助型参数不对dfs的状态产生影响其他的都有影响即两个参数二维数组这两个参数的范围数组的大小
记忆化搜索的代码如下
const int MOD1e97;
int visited;
int**memo;
int dfs(int i,int n,int* nums){if(visited0){return 1;}if(memo[i][visited]!-1)return memo[i][visited];int res0;for(int j0;jn;j){if((visited(1j))(nums[i]%nums[j]0||nums[j]%nums[i]0)){visited^(1j);res(resdfs(j,n,nums))%MOD;visited^(1j);}}return memo[i][visited]res%MOD;
}
int specialPerm(int* nums, int numsSize){int nnumsSize;int ans0;visited(1n)-1;memo(int**)malloc(sizeof(int*)*n);for(int i0;in;i){int s1n;memo[i](int*)malloc(sizeof(int)*s);for(int j0;js;j){memo[i][j]-1;}}for(int i0;in;i){visited^(1i);ans(ansdfs(i,n,nums))%MOD;visited^(1i);}for(int i0;in;i){free(memo[i]);}free(memo);return ans;
}
其实这题还有一种写法就是递推我们可以直接将上面的记忆化搜索直接转换成递推
const int MOD1e97;
int specialPerm(int* nums, int numsSize){int nnumsSize;int ans0;int visited(1n)-1;int s1n;int f[n][s];memset(f,0,sizeof(f));for(int i0;in;i){f[i][0]1;}//首先枚举状态注意这里先枚举列再枚举行因为每一列的状态由它的上一列状态推出for(int i1;is;i){for(int j0;jn;j){//然后计算每一个状态long long res0;for(int k0;kn;k){if((i(1k))(nums[j]%nums[k]0)||(nums[k]%nums[j]0)){res(resf[k][i^(1k)])%MOD;}}f[j][i]res;}}for(int i0;in;i)ans(ansf[i][visited^(1i)])%MOD;return ans;
}
四、给墙壁刷油漆 这题其实和上一题很相似思路一面墙要么是免费刷的消耗时间要么是付费刷的增加时间和金额取较小值即dfs(ij) min { dfs(i - 1 j - 1) dfs( i - 1j time[ i ] ) cost[ i ] }
递归边界1. ji1即剩下的墙可以免费刷返回0 2. i0并且ji1即没有墙可刷但是还欠费该方案不符合条件返回一个正无穷(就是一个无法作为答案的正数目的是在取较小值时不影响答案取值)
递归入口一开始从最后一面墙开始(下标是n-1)时间为0dfs(n-1,0)
代码如下
//正常的递归:超时
long long dfs(int i,int j,int* cost,int* time)//剩余第0~i面墙剩余花费的时间j,返回所需要的金额
{if(ji)return 0;//等价ji1这里的i是用下标表示的墙的个数if(i0)return INT_MAX;//i0ji,即欠费时间return fmin(dfs(i-1,j-1,cost,time),dfs(i-1,jtime[i],cost,time)cost[i]);
}
int paintWalls(int* cost, int costSize, int* time, int timeSize){int ncostSize;return dfs(n-1,0,cost,time);
}//记忆化搜索--可以过
//dfs(i,j)fmin(dfs(i-1,j),dfs(i-1,j-time[i])cost[i])
#define MIN(x,y) ((x)(y)?(y):(x))//这是宏定义或者你定义函数都行用来比较大小
//以下全局变量是为了减少函数参数个数使dfs函数的逻辑更加清晰当然把它们放入参数中也是可以的
int*Cost;
int*Time;
int**memo;
int N;
int dfs(int i,int j){if(ji1)return 0;//如果免费的时间要刷的墙的数量那么剩下的墙直接免费if(i0)return INT_MAX/2;//如果墙全刷完后ji10返回正无穷(该值取决于题目的可能答案区间和函数返回值类型)if(memo[i][jN-1]!-1)return memo[i][jN-1];return memo[i][jN-1]MIN(dfs(i-1,j-1),dfs(i-1,jTime[i])Cost[i]);
}
int paintWalls(int* cost, int costSize, int* time, int timeSize){int ncostSize;NcostSize;Costcost;Timetime;memo(int**)malloc(sizeof(int*)*n);for(int i0;in;i){memo[i](int*)malloc(sizeof(int)*(2*n));for(int j0;j2*n;j){memo[i][j]-1;}}int res dfs(n-1,0);for(int i0;in;i){free(memo[i]);}free(memo);return res;
}
上面代码中的memo数组的第二维度(时间维度)的范围是[-(n-1)n]即最多连续有n-1面墙免费和n面墙的免费时间其他的状态会被直接返回0或INT_MAX/2而要表示负的情况我们只能将每个数加上n-1,得到[02n-1],而这是下标范围我们数组大小就是2n
当然这题其实也是一种01背包问题的变形以后找时间出一期01背包问题的详解。
关注我让你了解更多周赛题目
不要忘记点赞评论加收藏哦
