从零学算法2848

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

2848.给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i,nums[i] = [starti, endi] ,其中 starti 是第 i 辆车的起点,endi 是第 i 辆车的终点。
返回数轴上被车 任意部分 覆盖的整数点的数目。
示例 1:
输入:nums = [[3,6],[1,5],[4,7]]
输出:7
解释:从 1 到 7 的所有点都至少与一辆车相交,因此答案为 7 。
示例 2:
输入:nums = [[1,3],[5,8]]
输出:7
解释:1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交,因此答案为 7 。文章来源地址https://www.toymoban.com/news/detail-706794.html

  • 我的原始人解法:直接遍历每个区间,加到 set,最后返回 set 的长度
  •   public int numberOfPoints(List<List<Integer>> nums) {
          Set<Integer> set = new HashSet<>();
          for(List<Integer> l : nums){
              for(int i=l.get(0);i<=l.get(1);i++){
                  set.add(i);
              }
          }
          return set.size();
      }
    
  • 他人解法:比较两个区间,根据能否合并区间划分,你会发现总共只有 6 种可能。设区间 1 两端为 3,5,区间 2 两端为 a,b:
    • a < 3 时有三种情况,比如 a 为 2
      • b < 3,3<b<5,b>5
    • 3<=a<=5 时有两种情况,比如 a 为 4
      • b<=5(合并后仍为 3-5),b>5(合并后为 3-b)
    • a>5 时那 b 不用说了也大于 5,所以只有一种情况。此时无法合并
  • 那么,如果我们对 nums 根据区间起点进行排序,使得遍历 nums 时保证 3<=a 就只剩下了三种情况。我们先构造一个区间,然后遍历区间时如果能合并区间就合并,如果不能那么我们就计算当前区间包含几个点,然后更新成新的区间即可。
  •   public int numberOfPoints(List<List<Integer>> nums) {
      	  // 排序
          Collections.sort(nums,(l1,l2)->l1.get(0)-l2.get(0)); 
          int start=0,end=0,ans=0;
          for(List<Integer> l:nums){
          	// 分析中 3<=a<=5 的情况
              if(l.get(0)<=end){
              	// 更新区间末端
                  if(l.get(1)>end){
                      end=l.get(1);
                  }else{
                  // 否则区间 2 属于区间 1,就什么也不用改,这个 else 可以直接省略掉
                  	continue;
                  }
              }else{
              	// 最开始肯定是直接进这个部分更新区间的,此时不该计算区间长度
              	// 否则等于 ans 初始就为 0-0+1=1 了
              	// 之后再进来就是直接结算完当前区间然后更新为新的区间了
                  ans+=end==0?0:end-start+1;
                  start=l.get(0);
                  end=l.get(1);
              }
          }
          ans+=end-start+1;
          return ans;
      }
    

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

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

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

相关文章

  • 从零学算法50

    50 .实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。 示例 1: 输入:x = 2.00000, n = 10 输出:1024.00000 示例 2: 输入:x = 2.10000, n = 3 输出:9.26100 示例 3: 输入:x = 2.00000, n = -2 输出:0.25000 解释:2-2 = 1/22 = 1/4 = 0.25 还真没我想的那么简单,这题可以学一下快速幂,我就直

    2024年02月07日
    浏览(34)
  • 从零学算法295

    295 .中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。 例如 arr = [2,3,4] 的中位数是 3 。 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 实现 MedianFinder 类: MedianFinder() 初始化 MedianFinder 对象。 void addNum(int num) 将数据流中的

    2024年02月09日
    浏览(36)
  • 从零学算法560

    560 . 和为 K 的子数组 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。 示例 1: 输入:nums = [1,1,1], k = 2 输出:2 示例 2: 输入:nums = [1,2,3], k = 3 输出:2 比较容易想到的是暴力解法(我承认我想不到)。为了不遗漏的得到每个连续

    2024年02月15日
    浏览(33)
  • 从零学算法34

    34 .给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1: 输入:nums = [5,7,7,8,8,10], target

    2024年02月13日
    浏览(38)
  • 从零学算法113

    113 .给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8,4,5]] 示例 2: 输入:root = [1,2,3]

    2024年02月11日
    浏览(35)
  • 从零学算法

    1575.给你一个 互不相同 的整数数组,其中 locations[i] 表示第 i 个城市的位置。同时给你 start,finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量 每一步中,如果你在城市 i ,你可以选择任意一个城市 j ,满足 j != i 且 0 = j locations.length ,并移动到城市 j 。从

    2024年02月06日
    浏览(25)
  • 从零学算法(LCR 180)

    文件组合 .待传输文件被切分成多个部分,按照原排列顺序,每部分文件编号均为一个 正整数(至少含有两个文件)。传输要求为:连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。 注意,返回时需遵循以下规则: 每种组合

    2024年02月07日
    浏览(33)
  • 从零学算法(剑指 Offer 45)

    输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 我的原始人解法:直接冒泡排序,把最先应该拼接的那个数不断后移,然后拼接即可。关键就

    2024年02月10日
    浏览(39)
  • 从零学算法 (剑指 Offer 13)

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+

    2024年02月11日
    浏览(34)
  • 【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表(数组、链表、栈、队列、哈希表) 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 (n = 0) a1 是首节点

    2024年02月10日
    浏览(78)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包