LeetCode刷题记录——day3

这篇具有很好参考价值的文章主要介绍了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 发布!文章来源地址https://www.toymoban.com/news/detail-842205.html

到了这里,关于LeetCode刷题记录——day3的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 嵌入式面试刷题(day3)

    本篇文章我们继续讲解嵌入式面试刷题,给大家继续分享嵌入式中的面试笔试经验和技巧。 在C语言中,可以使用以下代码来比较两个float类型的数据是否相同: 上述代码中,通过计算两个浮点数之差的绝对值,并与给定的误差范围进行比较。如果差值小于等于指定的误差范

    2024年02月14日
    浏览(72)
  • 代码随想录Day3 | 链表01-leetcode203、707、206

    题目链接:移除链表元素 思路: 链表中元素的添加和删除关键是要 保证不断链且指向关系正确 。对于删除操作,链的修改涉及将待删除元素的前一个元素指向待删除元素的后一个元素,因此在判断当前元素是否需要删除时,要记录当前元素的前后指针。 1.删除头结点时另作

    2024年02月16日
    浏览(62)
  • 算法刷题营【Day3】:: 链表篇:单链表结点删除思路:一题辨别哨兵结点的优势(删除有奇效):203. 移除链表元素

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:203. 移除链表元素 2. 题解参考 - - 2.1 方法一:原表操作(不含哨兵结点) - - 2.2 方法二:虚设哨兵结点辅助法 - - 2.3 方法三:递归法 3. 单链表结点删除思路 4. 方法思路点拨:原表操

    2024年02月06日
    浏览(48)
  • 【LeetCode题目详解】 203. 移除链表元素707. 设计链表206. 反转链表 day3(补)

    题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 看到这道题就想到了链表 这道题有两种写法,涉及如下链表操作的两种方式: 直接使用

    2024年02月16日
    浏览(41)
  • day 1 LeetCode刷题日志

    今天的内容是 704 和 27 ovo 704. 二分查找 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target ,如果目标值存在返回下标,否则返回 -1 Myself C: Myself C++: Carl C++: Myself Sum: NOTICE 左闭右闭 左闭右开 C语言的int类型最大是10^9 C++的

    2024年02月03日
    浏览(38)
  • day01刷题记录

    牛牛举办了一次编程比赛,参加比赛的有3*n个选手,每个选手都有一个水平值a_i.现在要将这些选手进行组队,一共组成n个队伍,即每个队伍3人.牛牛发现队伍的水平值等于该队伍队员中第二高水平值。 例如: 一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3 一个队伍三个

    2024年02月02日
    浏览(50)
  • 力扣python刷题day03|LeetCode203、707、206

    题目 题目链接:203:移除链表元素 方法一: 知识点: 设置虚拟头结点 题目 来源:力扣(LeetCode) 提示: 0 = index, val = 1000 请不要使用内置的 LinkedList 库。 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。 方法一:单链表法 方法二:双链表法 (有点难

    2024年02月16日
    浏览(41)
  • 【LeetCode刷题记录】数组专题

    说明 : 文章内容为个人的力扣刷题记录,不定时更新。 文章内容如有错误,欢迎指正。 2023-04-24 题目1. 两数之和 1. 两数之和 - 力扣(Leetcode) 方法一:暴力解法,循环遍历 C++ python 方法二:哈希表 参考1. 两数之和 - 力扣(Leetcode) 哈希表的查找时间复杂度为O(1),可以大大

    2024年02月02日
    浏览(53)
  • 力扣python刷题day04|LeetCode24、19、160、142

    题目 来源:24:两两交换链表中的节点 建议使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。 接下来就是交换相邻两个元素了,此时一定要画图,不画图,操作多个指针很容易乱,而且要操作的先后顺序 方法: 题目

    2024年02月16日
    浏览(36)
  • LeetCode刷题记录--- 微软企业题库

    😄 今天是2022年12月30号,我开始了LeetCode的《微软企业题库》专题 刷题! 😄 开了力扣plus会员了,可以看到各企业的出题情况和题目的出现频率,所以打算把各企业的出题指数第一页 (也就是top50题刷一遍),当然肯定有些题也是刷过的,那就当二刷。加油! 🚀 进度: 已完

    2024年02月08日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包