LeetCode刷题记录——day4

这篇具有很好参考价值的文章主要介绍了LeetCode刷题记录——day4。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150
对于一个可以构成“碗”的序列,最后装满水的话应该和最短的一边齐平,那么可以左右各遍历一次,记录每个元素位置对应的最短边高度,再对比就可以得出左右哪边最短

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

总结,对于一些左右对称的问题,也就是将其对称翻转过来结果一样的问题,或者说有时我们需要同时知道左右元素的信息才能得到答案的,我们不可能只从一边遍历一次就得到答案,应该左右各遍历一次才能同时得到左边的信息和右边的信息,这样才能够可能得到答案

本文由博客一文多发平台 OpenWrite 发布!文章来源地址https://www.toymoban.com/news/detail-842553.html

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

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

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

相关文章

  • 【C刷题】day4

    一、选择题 1、设变量已正确定义,以下不能统计出一行中输入字符个数(不包含回车符)的程序段是( )  A: n=0;while(ch=getchar()!=\\\'n\\\')n++;                             B: n=0;while(getchar()!=\\\'n\\\')n++; C: for(n=0;getchar()!=\\\'n\\\';n++);                                         D: n=0;f

    2024年02月08日
    浏览(33)
  • 【代码随想录】刷题Day4

    24. 两两交换链表中的节点 前后指针实现 1.没有元素或者只有一个元素无意义 2.给出一个前驱prev,以及用来交换的两个节点cur和next 3.我当时是这么想的,如果两个指针一起动,那么就要用cur和next同时判断结束,也许这个条件会比较苛刻(我就烦这种边界条件),所以我觉得动一

    2023年04月22日
    浏览(48)
  • 【LeetCode】挑战100天 Day4(热题+面试经典150题)

    LeetCode是一个在线编程网站,提供各种算法和数据结构的题目,面向程序员、计算机科学专业学生和技术爱好者等人群,旨在帮助他们提高算法和编程技能。LeetCode上的问题通常来自各种技术公司的面试题目,因此它也是程序员面试准备的重要资源之一。 LeetCode上的问题涵盖了

    2024年02月04日
    浏览(41)
  • 代码随想录Day4 | 链表02-leetcode24、19、面试题02.07、142

    题目链接:两两交换链表中的节点 思路: 双指针p1、p2,分别指向每次需要交换的节点。交换过程为p2的next指向p1,p1的next指向p2的next, 还需要注意将p1de前一个指针指向交换后的p2以确保不断链 。 1. 空链 or 只有头结点? - 直接返回head,无需做任何修改 2. 交换需要记录前驱

    2024年02月12日
    浏览(42)
  • 算法刷题Day4 两两交换链表中的节点+删除链表的倒数第N个结点+链表相交+环形链表

    使用dummy节点可以极大地简化过程 有个地方折磨了我有一会儿,是粗心导致的,而且提示的错误也很难发现是哪里导致的。就是在case为 head = [1], n = 1 时,最后释放了 tmp 之后(此时 tmp 刚好指向 head ,我还 return head; ,意思就是操作了已经被我释放的内存, leetcode 就报错了

    2024年02月09日
    浏览(49)
  • 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日
    浏览(40)
  • day01刷题记录

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

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

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

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

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

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

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

    2024年02月16日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包