当前位置: 首页 > ai >正文

LeetCode每日一题,8-6

水果成篮3️⃣
本题给你两个数组fruits和baskets,对于fruits种的每个数,找到baskets中第一个大于等于fruits的值,然后baskets的该下标作废,最后返回有多少个fruit找不到对应的baskets。
用线段树维护区间最大值,然后对于每个fruits进行查询,重点是查询最左边的值。

class Solution {int N = (int) (1e5 + 10);Node[] tr = new Node[4 * N];class Node {int l, r;int val;}void build(int u, int l, int r,  int[] baskets) {tr[u] = new Node();tr[u].l = l;tr[u].r = r;tr[u].val = 0;if (l == r) {tr[u].val = baskets[l - 1];return;}int mid = l + r >> 1;build(u << 1, l, mid, baskets);build(u << 1 | 1, mid + 1, r, baskets);tr[u].val = Math.max(tr[u << 1].val, tr[u << 1 | 1].val);}int query(int u, int l, int r, int val) {// 如果当前节点的值小于要查询的值,直接返回0if (tr[u].val < val) {return 0;}// 如果当前节点区间完全在查询区间外,返回0if (tr[u].r < l || tr[u].l > r) {return 0;}// 如果是叶子节点且值满足条件if (tr[u].l == tr[u].r) {int pos = tr[u].l;tr[u].val = -1;  // 标记为已使用return pos;}int res = 0;int mid = (tr[u].l + tr[u].r) >> 1;// 先尝试左子树if (tr[u << 1].val >= val && l <= mid) {res = query(u << 1, l, Math.min(r, mid), val);}// 如果左子树没找到结果且右子树可能有解,尝试右子树if (res == 0 && tr[u << 1 | 1].val >= val && r > mid) {res = query(u << 1 | 1, Math.max(l, mid + 1), r, val);}// 更新当前节点的值tr[u].val = Math.max(tr[u << 1].val, tr[u << 1 | 1].val);return res;}public int numOfUnplacedFruits(int[] fruits, int[] baskets) {int n = fruits.length;int m = baskets.length;int res = n;build(1, 1, m, baskets);for (int i = 0; i < n; i++) {int val = fruits[i];
//            找到第一个大于等于val的位置int pos = query(1, 1, m, val);if(pos != 0)res --;}return res;}
}
http://www.xdnf.cn/news/17094.html

相关文章:

  • springboot项目justAuth扩展第二个小程序
  • Unity轻量观察相机
  • 功能安全和网络安全的综合保障流程
  • 云端软件工程智能代理:任务委托与自动化实践全解
  • CDP集群中通过Hive外部表迁移HBase数据的操作记录
  • 昇思+昇腾开发板+DeepSeek模型推理和性能优化
  • 自己本地搭建的服务器怎么接公网?公网IP直连服务器方法,和只有内网IP直接映射到互联网
  • 线性代数中矩阵的基本运算运算
  • 哲学中的主体性:历史演进、理论范式与当代重构
  • FLAN-T5:大规模指令微调的统一语言模型框架
  • python-自定义抠图
  • OpenSpeedy绿色免费版下载,提升下载速度,网盘下载速度等游戏变速工具
  • Datawhale AI夏令营 第三期 task2 稍微改进
  • MyBatis实现SQL
  • Python日志记录库——logaid
  • Centos-Stream 10 安装教程(2025版图文教程)
  • ASP3605I同步降压调节器的高频化设计与多相扩展技术优化方案
  • Python 函数详解
  • 重生之我在暑假学习微服务第十天《网关篇》
  • 微软Dragon Ambient eXperience (DAX) 深度解析
  • 《UE教程》第一章第六回——迁移独立项目(资源)
  • 【学习嵌入式day-17-数据结构-单向链表/双向链表】
  • 【计算机网络】6应用层
  • 深度学习·基础知识
  • selenium自动化收集资料
  • 从汇编角度揭秘C++构造函数(1)
  • 【深度学习新浪潮】混元3D是什么产品?
  • 2025《艾诺提亚失落之歌》逆向工程解包尝试
  • 【模电笔记】—— 直流稳压电源——整流、滤波电路
  • 二叉树——堆及其实现