惠城网站设计,wordpress最简易主题,磁力猫,免费落地页制作平台目录
1.最优除法
题解
2.跳跃游戏 II
题解
3.加油站
题解 利用 单调性#xff0c;可以实现 区间跳跃 1.最优除法
链接#xff1a; 553. 最优除法
给定一正整数数组 nums#xff0c;nums 中的相邻整数将进行浮点除法。
例如#xff0c;nums [2,3,4]#xff0c;我…目录
1.最优除法
题解
2.跳跃游戏 II
题解
3.加油站
题解 利用 单调性可以实现 区间跳跃 1.最优除法
链接 553. 最优除法
给定一正整数数组 numsnums 中的相邻整数将进行浮点除法。
例如nums [2,3,4]我们将求表达式的值 2/3/4。
但是你可以在任意位置添加任意数目的括号来改变算数的优先级。你需要找出怎么添加括号以便计算后的表达式的值为最大值。
以字符串格式返回具有最大值的对应表达式。
注意你的表达式不应该包含多余的括号。 示例 1
输入: [1000,100,10,2]
输出: 1000/(100/10/2)
解释: 1000/(100/10/2) 1000/((100/10)/2) 200
但是以下加粗的括号 1000/((100/10)/2) 是冗余的
因为他们并不影响操作的优先级所以你需要返回 1000/(100/10/2)。其他用例:
1000/(100/10)/2 50
1000/(100/(10/2)) 50
1000/100/10/2 0.5
1000/100/(10/2) 2 给定一正整数数组 numsnums 中的相邻整数将进行浮点除法。
例如nums [2,3,4]我们将求表达式的值 “2/3/4”。 但是你可以在任意位置添加任意数目的括号来改变算数的优先级。
你需要找出怎么添加括号以便计算后的表达式的值为最大值。题意其实就是数组给一堆数数中间其实都有除法的此时让我们任意位置添加一些括号使表达式的值为最大值最后返回的是以字符串格式返回具有最大值的对应表达式。注意你的表达式不应该包含多余的括号。
原本括号里面顺序是3/4/5现在多添加一个括号还是(3/4)/5。 题解
举一个例子来提取我们的贪心策略
这个时候我们要明白一点在这个表达式中添加括号最终都会转换为 x/y 的形式。
也就是从这些数中挑一些放在分子上一些数放在分母上 我们最终要的是 x/y 是最大的一个分数要最大要么就是分子变大要么就是分子变小。
接下来我们设计表达式就是尽可能让分子大分母小。这就是我们的贪心方向。
还有一点无论在表达式哪里填上括号a都是在分子上b都是在分母上
所以a和b这两个无法通过添加括号去改变的a/b。所以最终a一定在分子上b一定在分母上。现在可供我们选择的就是c、d、e、f为了使最终结果最大我们就想无脑的把c、d、e、f和a一起放在分子上。
这里可以用贪心优化就是因为这个值乘起来是越来越大的 贪心策略除了前两个数以外其余的数全部放在分子即可
如何实现贪心策略呢 这里我们用小学就学过的知识负负得正。除除得正。因此我们仅需在b之前填一个(f后填一个括号里面得除法全都因为括号外面得除法变成除除得正 class Solution {
public:string optimalDivision(vectorint nums) {string str;if(nums.size()1) return to_string(nums[0]);if(nums.size()2){strto_string(nums[0]);str/;strto_string(nums[1]);return str;}for(int i0;inums.size();i){strto_string(nums[i]);str/;if(i0) str(;if(inums.size()-1) {str.pop_back();str);}}return str;}
}; 2.跳跃游戏 II
链接 45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i]i j n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 示例 1:
输入: nums [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums [2,3,0,1,4]
输出: 2 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处。
这句话特别重要的地方就是 任意
下面举个例子刚开始在0号位置最大跳跃长度是3可以跳到下标3的位置。 你可以跳转到任意 nums[i j] 处这句话意思eg. nums[i]里面存的3是最大跳跃长度你可以选择跳3步、跳2步、跳1步。
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
题解
贪心(X)
刚开始处于0好位置这里有一个最大跳跃长度那每次跳跃的时候就非常贪心的跳最长跳跃长度。但是这种贪心是错的。 2. 动态规划
这个模型无非就是从左往右的一个模型其实就是动规里面非常常规的线性dp问题。
1.状态表示
dp[i] 表示从 0 位置开始到达 i 位置的时候最小跳跃次数
2.状态转移方程
根据最近一步划分情况
能够到 i 位置的前提是要满足 nums[j] j i说明能够从 j 位置到达 i 位置那到达 j 位置的最小跳跃次数 在 加上 从 j 到 i 这一跳跃次就是到达 i 位置最小跳跃次数j的位置有很多因此外面要求dp[i]的最小值。 3.初始化
dp[0] 0 初始就在0位置然后要取dp[i]的最小值因此0位置之后可以初始化 INT_MAX
4.填表顺序
从左往右
5.返回值
dp[i] 表示从 0 位置开始到达 i 位置的时候最小跳跃次数我们要的是到底n-1位置的最小跳跃次数因此返回dp[n-1]
class Solution {
public:int jump(vectorint nums) {int nnums.size();if(n1) return 0;vectorint dp(n,0x3f3f3f3f);dp[0]0;for(int i1;in;i){for(int j0;ji-1;j){if(jnums[j]i)dp[i]min(dp[i],dp[j]1);//交给 计算机//j--i 次数要1}}return dp[n-1];}
};
虽然可以通过但是实际复杂度是O(N^2)
1. 类似于层序遍历的过程
刚开始在2这个位置此时起跳可以跳到3和1的位置。
2这里可以表示第1次起跳的位置3和1表示第2次起跳的位置。通过第2次起跳的位置我们可以得到第3从起跳的位置然后把重叠的删除这里其实也有一点小贪心如果能从第2次的1起跳那为什么还要从第3次重叠的1起跳呢跳跃次数更多了。所以只有1和4是第三次起跳的位置。同理从第3次起跳位置我们可以得到第4次起跳位置 你会发现这里类似于层序遍历每次都能知道起跳的左端点和右端点然后遍历这一层的时候又能找到下一层的左端点和右端点。
只要发现更新出来下一次起跳位置能够覆盖到n-1位置的时候就停止因为次数已经可以跳到最后一个位置了 如何实现呢 我们仅需搞两个指针left指向当前起跳的左端点right指向当前起跳的右端点把这个区间遍历一遍就可以找到下一个起跳区间其中找左端点很好找就是right 1找右端点就是在遍历的过程中拿着nums[i] i 找到其中的最大值就是右端点。
在这个遍历过程中我们仅需遍历一次就行了所以时间复杂度是O(N)
class Solution {
public:int jump(vectorint nums) {int ret0,nnums.size();int left0,right0;while(leftright){if(rightn-1) return ret;int tmpright;for(int ileft;itmp;i){rightmax(right,nums[i]i);}lefttmp1;ret;}return -1;}
};
不要忘了还要处理跳不到的情况
while(leftright)return -1; 3.加油站
链接 134. 加油站
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。 示例 1:
输入: gas [1,2,3,4,5], cost [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发可获得 4 升汽油。此时油箱有 0 4 4 升汽油
开往 4 号加油站此时油箱有 4 - 1 5 8 升汽油
开往 0 号加油站此时油箱有 8 - 2 1 7 升汽油
开往 1 号加油站此时油箱有 7 - 3 2 6 升汽油
开往 2 号加油站此时油箱有 6 - 4 3 5 升汽油
开往 3 号加油站你需要消耗 5 升汽油正好足够你返回到 3 号加油站。
因此3 可为起始索引。 选择某个加油站为出发点环绕一周看是否能回到出发点。
如果可以就返回对应的下标不能就返回-1。
初始时油箱是空的从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i]油箱容量是无限的。假设从3位置出发刚开始油箱为空此时可以补充1升汽油但是需要3升汽油才能到下一个位置。所以这个位置不可以同理4和5都不可以。可以从1位置出发 从这里可以补充4升汽油仅需消耗1升就可以到下一个位置到下一个位置还剩下3升到2的位置补充5升现在共有8升消耗2升到下一个位置还有6升 然后补充1升消耗3升到下一个位置还剩4在补充2升消耗4升到下一个位置还剩2升在补充3升消耗5升到出发点正好剩下0可以到达返回3。 题解
解法一暴力解法 - 枚举
首先可以想到一个优化仅需考虑g和c的差就可以了比如第一个位置会加1升油消耗3升油它们的差就是从这个加油站获得的净收益。
如果从负开始走绝对是走不到下一个位置的所以肯定会选择净收益为正的作为出发点。
我们这道题其实特别像是一道模拟的题任意枚举一个位置看看从这个位置能不能绕一圈会回来就可以。
如果不能就去枚举下一个位置。
所以我们的暴力策略就很简单
预处理 计算出 每一步的 diff依次枚举所有的起点从起点开始模拟一遍加油的流程即可
虽然策略很简单但是要注意这里是有环的所以写代码的时候要考虑如何从最后一个位置回到0位置。
diff [-2, -2, -2, 3, 3]
我们的贪心就是根据暴力优化来的所以先搞定暴力的代码。然后优化的时候仅需加一句代码就能将时间复杂度从O(N^2)变成O(N)
如何实现暴力的代码
这里我们主要考虑就是如何从最后一个位置回到第一个位置其实这里两层for循环就可以搞定我们创建一个变量step用这个变量表示从 i 往后走了多少步step变化是从 0 ~ n - 1。然后 i step% n (数组大小) 就可以从最后一个位置回到第一个位置。
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int ngas.size();vectorint diff(n);for(int i0;in;i){diff[i]gas[i]-cost[i];}for(int i0;in;i){bool checkfalse;if(diff[i]0){checktrue;int sumdiff[i];for(int step1;stepn;step){int curr(istep)%n;sumdiff[curr];if(sum0){checkfalse;break;}}}if(check) return i;}return -1;}
};
解法二优化 - 找规律贪心
diff表示g-c的差我们的暴力解法是依次固定一个位置为起点从这个起点开始模拟加油流程其实就是把净收益加一下。
如果发现从a加到f小于0了说明从f这个位置开始就不能往后走了所以从a为起来最多能到f这个位置。这里有一个等式。 我们的暴力是枚举下一个起点然后在走。然后我们这里也有个不等式我们要想从a走到b一定是a0的从a加到f 0现在第二个不等式又少了a那更是 0同理从c为起点也是越不过f的a b 0才能到c等式少了ab那更小于0 所以说发现有一个起点点都跑不到某个位置那中间的都不用在考虑了不用在枚举了。直接让 i 指针更新到 五角星 后面的一个位置也就是 i i step
我们最差会遍历数组两遍假设还是以a为起点发现到h走不到了下一个位置就是i最差我们绕回去在遍历一遍再走到h位置相当于遍历了数组两遍 然后接下来更新 i 的时候 是 i step 1 此时就已经越界了。所以最差遍历数组两遍时间复杂度O(N)
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int ngas.size();vectorint diff(n);for(int i0;in;i){diff[i]gas[i]-cost[i];}for(int i0;in;i){int step0;int sum0;for(;stepn;step){int curr(istep)%n;sumdiff[curr];if(sum0){break;}}if(sum0) return i;istep;}return -1;}
};
