LeetCode刷题记录——day3
1、https://leetcode.cn/problems/gas-station/submissions/514930619/?envType=study-plan-v2&envId=top-interview-150
对于这个问题可以这样来考虑，将数据看作一个环，如果答案唯一，那么就意味着从任意一个节点开始寻找，最后都会得到同一个节点的答案，那么为何不直接从0节点开始呢？
其次，我们可以建立一个total变量来记录总的油量和消耗量的差的结果，倘若这个值小于0，则一定没有解，倘若大于零，则说明一定有解。
继续这个思路，当有解时，我们不妨从i节点出发，设置一个temp变量记录从i开始到j的剩余油量。当temp小于0时，说明现在到达的节点j是可以到达的，但是无法到达j+1节点，那么下次的起点就可以从j+1开始重复这个过程。
为什么？
不妨这样考虑，i到j构成一个弧，同样，我们假设当前的问题是无解的，那么我们应该可以用上述方式将j与j+1断开，把环分成许多的弧。当然我们这里假设的无解，其实从total就可以看出。那么假如现在我们发现total大于0了，我们还可以将环分割成这样的弧吗？我们不妨0开始，一直分割，假设前面我们分割成了许多弧，最后从某个节点k开始一直遍历完了却再也没有分割出弧。那么这个末尾的弧可以和第一个弧链上吗？当然可以！假设不可以的话，那么我们每个弧最终的剩余油量都不足以支持它到达下一个弧，那么total不就是小于0了吗？但我们已经得到了total大于0，所以最后一个弧一定可以和第一个弧连起来，接下来两个弧变成一个弧，我们将这个新弧看作最后一个弧，那么他和现在的新的第一个弧会怎么样呢，同理，他们还是可以连起来的！由此我们的算法就明确了：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int len = gas.size();
vector<int> remaind(len);
int total = 0,temp = 0;
int start = 0;
for(int i=0;i<len;i++){
total=total+gas[i]-cost[i];
temp = temp+gas[i]-cost[i];
if(temp<0){
temp=0;
start=i+1;
}
}
return total<0?-1:start;
}
};
2、https://leetcode.cn/problems/candy/submissions/514952725/?envType=study-plan-v2&envId=top-interview-150
对于这个问题，我们观察数组，会发现第一个和最后一个元素非常特殊，因为它们只有一个元素和自己相邻，如果其余元素都确定了，那么它们也就确定了，所以我们不妨从第二个和倒数第二个元素开始处理，我们设置两个变量j，i它们分别从第二个以及倒数第二个开始向后向前遍历，并且它们会分别比较自己的j-1以及i+1元素，倘若比它们小则不变，大于则比较现在的糖果数量，若是少了则改变糖果数量。最后每个元素都会和自己左右两个相邻的元素比较。
class Solution {
public:
int candy(vector<int>& ratings) {
int len=ratings.size();
vector<int> candy(len);
int total=0;
for(int i=len-2,j=1;i>=0;i--,j++){
if(ratings[i]>ratings[i+1]){
if(candy[i]<=candy[i+1]){
total=total+candy[i+1]+1-candy[i];
candy[i]=candy[i+1]+1;
}
}
if(ratings[j]>ratings[j-1]){
if(candy[j]<=candy[j-1]){
total=total+candy[j-1]+1-candy[j];
candy[j]=candy[j-1]+1;
}
}
}
total = total+len;
return total;
}
};
本文由博客一文多发平台 OpenWrite 发布！