有的网站打开的是html结尾的路径有的不是,企业信息服务平台,网站支付怎么做安全吗,wordpress添加动态图标目录1662. 检查两个字符串数组是否相等题目自己代码5606. 具有给定数值的最小字符串题目自己代码贪心算法1664. 生成平衡数组的方案数题目自己代码动态规划优化1665. 完成所有任务的最少初始能量题目思路1662. 检查两个字符串数组是否相等
题目
给你两个字符串数组 word1 和 … 目录1662. 检查两个字符串数组是否相等题目自己代码5606. 具有给定数值的最小字符串题目自己代码贪心算法1664. 生成平衡数组的方案数题目自己代码动态规划优化1665. 完成所有任务的最少初始能量题目思路 1662. 检查两个字符串数组是否相等
题目
给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同返回 true 否则返回 false 。
数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。
自己代码
累加然后判断是否相等
class Solution {
public:bool arrayStringsAreEqual(vectorstring word1, vectorstring word2) {string str1;string str2;for(int i0;iword1.size();i){str1word1[i];}for(int i0;iword2.size();i){str2word2[i];}if(str1str2) return true;else return false;}
};5606. 具有给定数值的最小字符串
题目
小写字符 的 数值 是它在字母表中的位置从 1 开始因此 a 的数值为 1 b 的数值为 2 c 的数值为 3 以此类推。
字符串由若干小写字符组成字符串的数值 为各字符的数值之和。例如字符串 “abe” 的数值等于 1 2 5 8 。
给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。
自己代码
记录一下自己超时的代码 使用的回溯法这一题使用回溯法并不好字母越多解空间树就会越大并且没有使用高效的剪枝手段。
class Solution {
public:int sum;int num;string res;char zimu[27]{a,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z};bool backtracking(int n,int k){if(num n || sum k || (numn sumk 26*(n-num)(k-sum))){return false;}//找到了n个数if(num n sum k){return true;}for(int i1;i26;i){//处理结点string new_res res;res(zimu[i]);sumi;num1;//递归,探索下一层if(backtracking(n,k)true) return true; sum-i;num-1;//回溯撤销处理结果resnew_res;}return false;}string getSmallestString(int n, int k) {res;sum0;num0;backtracking(n,k);return res;}
};贪心算法
构造出的字符串字典序最小可以考虑贪心地从字符串的开头处开始构造每次选择一个满足要求的最小字母。 假设我们当前构造到了某一个位置包括此位置还剩下n’个位子没有放入字符并且这些位子的数值之和为k’; 那么如果我们放入字母c那么剩余n’-1个位置以及k’-c的数值和必须满足 n’-1k’-c26(n’-1) 位置数 位置数上的数值和 位置数能放的最多的数值和; 这样就能得到c的取值范围: k’ - 26(n’-1) c k’ - (n’-1) 这样就能得到c的取值下限k’ - 26(n’-1); 如果下限小于等于0我们取a(这是我们能取的当中最小的) 如果下限大于0那么选择数值对应的字符。 总的来说就是从第一位到最后一位都取当前能够取的最小值这样就能保证构造出来的字符串字典序最小了。
class Solution {
public:string getSmallestString(int n, int k) {int post_unusedn;int sum_leftk;string result;while(post_unused!0){int c1;if(sum_left - 26*(post_unused-1)0) c1;else csum_left - 26*(post_unused-1);resultc-1a;post_unused--;sum_left-c;}return result;}
};按照这个思路写一遍。 我他妈傻了贪心也太牛了学习了。
1664. 生成平衡数组的方案数
题目
给你一个整数数组 nums 。你需要选择 恰好 一个下标下标从 0 开始并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。
比方说如果 nums [6,1,7,4,1] 那么 选择删除下标 1 剩下的数组为 nums [6,7,4,1] 。 选择删除下标 2 剩下的数组为 nums [6,1,4,1]。 选择删除下标 4 剩下的数组为 nums [6,1,7,4] 。 如果一个数组满足奇数下标元素的和与偶数下标元素的和相等该数组就是一个 平衡数组 。 请你返回删除操作后剩下的数组 nums 是 平衡数组 的 方案数 。
自己代码
又是一个超时代码 先讲讲思路 首先nums数组中的每个位置都定义四个相应数组 分别用来记录i之前的偶数之和i之前的奇数之和i之后的偶数之和i之后的奇数之和。 然后开始遍历这个数组记录每个位子的四个数组数值。 去除索引为i的元素后i之前元素的奇偶性不变i之后元素的奇偶性改变即i之后奇/偶数下标元素的和变成了偶/奇数下标。 然后暴力解满足奇数下标元素的和与偶数下标元素的和相等
class Solution {
public:int waysToMakeFair(vectorint nums) {int fangannums0;for(int i0;inums.size();i){vectorint sum{0,0,0,0};for(int j0;ji;j2){sum[0]nums[j];}for(int j1;ji;j2){sum[1]nums[j];}if(i%20){for(int ji1;jnums.size();j2){sum[2]nums[j];}for(int ji2;jnums.size();j2){sum[3]nums[j];} }else{for(int ji1;jnums.size();j2){sum[3]nums[j];}for(int ji2;jnums.size();j2){sum[2]nums[j];} }if(sum[0]sum[2] sum[1]sum[3]) fangannums1;}return fangannums;}
};动态规划优化
之前超时很明显就是四个数组值重复计算i之前的偶数之和i之前的奇数之和i之后的偶数之和i之后的奇数之和。 现在直接看下标这样不容易混淆下标是偶数数组名字中就有even下标是奇数名字中就有odd。 步骤如下 需要特别注意的地方 dp推导 注意这里我们四个数组都不会将nums[i]包括进去的。 i为偶数的话i-1是奇数所以左偶和[i] 左偶和[i-1]左奇和[i] 左奇和[i-1]nums[i-1]; i为奇数的话i-1是偶数所以左偶和[i] 左偶和[i-1]nums[i-1]左奇和[i] 左奇和[i-1]; 这样一来就能对计算i之前的偶数和奇数和省下时序。没必要每次都从i0开始判断累加。 其次i右边的偶数和奇数和也没必要通过for运算开始计算而是只需要从sum_odd和sum_even中视情况减去左偶右偶、nums[i]即可。 这样也是同时省下大把时序。
//如果i是偶数下标,i-1为奇数下标
if(i%20)
{before_i_evensum[i]before_i_evensum[i-1];before_i_oddsum[i]before_i_oddsum[i-1]nums[i-1];
}
else
{before_i_evensum[i]before_i_evensum[i-1]nums[i-1];before_i_oddsum[i]before_i_oddsum[i-1];
}class Solution {
public:int waysToMakeFair(vectorint nums) {int fangannums0;int n nums.size();//i左边偶数下标所指数之和vectorint before_i_evensum(n,0);//i左边奇数下标所指数之和vectorint before_i_oddsum(n,0);//i右边偶数下标所指数之和vectorint after_i_evensum(n,0);//i右边偶数下标所指数之和vectorint after_i_oddsum(n,0);//*******【1】计算数组的奇数下标和以及偶数下标和***//int sum_odd0;int sum_even0;for(int i0;in;i){if(i%20) sum_evennums[i];else sum_oddnums[i];}//****************************************//for(int i0;in;i){if(i0){after_i_evensum[0]sum_even - nums[i];after_i_oddsum[0] sum_odd; }else{//*******【2】i之前的偶数下标和以及奇数下标和***////如果i是偶数下标,i-1为奇数下标if(i%20) {before_i_evensum[i]before_i_evensum[i-1];before_i_oddsum[i]before_i_oddsum[i-1]nums[i-1];after_i_evensum[i]sum_even - before_i_evensum[i] - nums[i];after_i_oddsum[i] sum_odd - before_i_oddsum[i];}//如果i是奇数下标,i-1为偶数下标else{before_i_evensum[i]before_i_evensum[i-1]nums[i-1];before_i_oddsum[i]before_i_oddsum[i-1];after_i_evensum[i]sum_even - before_i_evensum[i];after_i_oddsum[i] sum_odd - before_i_oddsum[i] - nums[i];}}if(before_i_evensum[i]after_i_oddsum[i] before_i_oddsum[i]after_i_evensum[i])fangannums; }return fangannums;}
};这一题当时并没有做出来是刚刚才想到的。
1665. 完成所有任务的最少初始能量
题目
给你一个任务数组 tasks 其中 tasks[i] [actuali, minimumi]
actuali 是完成第 i 个任务 需要耗费 的实际能量。 minimumi 是开始第 i 个任务前需要达到的最低能量。 比方说如果任务为 [10, 12] 且你当前的能量为 11 那么你不能开始这个任务。如果你当前的能量为 13 你可以完成这个任务且完成它后剩余能量为 3 。
你可以按照 任意顺序 完成任务。
请你返回完成所有任务的 最少 初始能量。 思路
观察示例可以发现完成的任务是按照最低能量-实际能量的大小来排序的差越大的越先被执行。 https://leetcode-cn.com/problems/minimum-initial-energy-to-finish-tasks/solution/wan-cheng-suo-you-ren-wu-de-zui-shao-chu-shi-neng-/ 神仙题目这里贴个代码
class Solution {
public:static bool cmp(vectorint p1, vectorint p2) {return p1[1] - p1[0] p2[1] - p2[0];}int minimumEffort(vectorvectorint tasks) {sort(tasks.begin(), tasks.end(),cmp);int sum0; //完成任务需要消耗的实际能量int ans0; //完成任务需要达到的最低能量//打印信息// for(auto task : tasks)// {// couttask[0]:task[0] task[1]:task[1]endl;// }for(auto task : tasks){//coutans:ans sum:sumendl;ans max(ans,sumtask[1]);sum task[0];}return ans;}
};
