Java | Leetcode Java题解之第327题区间和的个数

题目:

题解:

class Solution {public int countRangeSum(int[] nums, int lower, int upper) {long sum = 0;long[] preSum = new long[nums.length + 1];for (int i = 0; i < nums.length; ++i) {sum += nums[i];preSum[i + 1] = sum;}BalancedTree treap = new BalancedTree();int ret = 0;for (long x : preSum) {long numLeft = treap.lowerBound(x - upper);int rankLeft = (numLeft == Long.MAX_VALUE ? (int) (treap.getSize() + 1) : treap.rank(numLeft)[0]);long numRight = treap.upperBound(x - lower);int rankRight = (numRight == Long.MAX_VALUE ? (int) treap.getSize() : treap.rank(numRight)[0] - 1);ret += rankRight - rankLeft + 1;treap.insert(x);}return ret;}
}class BalancedTree {private class BalancedNode {long val;long seed;int count;int size;BalancedNode left;BalancedNode right;BalancedNode(long val, long seed) {this.val = val;this.seed = seed;this.count = 1;this.size = 1;this.left = null;this.right = null;}BalancedNode leftRotate() {int prevSize = size;int currSize = (left != null ? left.size : 0) + (right.left != null ? right.left.size : 0) + count;BalancedNode root = right;right = root.left;root.left = this;root.size = prevSize;size = currSize;return root;}BalancedNode rightRotate() {int prevSize = size;int currSize = (right != null ? right.size : 0) + (left.right != null ? left.right.size : 0) + count;BalancedNode root = left;left = root.right;root.right = this;root.size = prevSize;size = currSize;return root;}}private BalancedNode root;private int size;private Random rand;public BalancedTree() {this.root = null;this.size = 0;this.rand = new Random();}public long getSize() {return size;}public void insert(long x) {++size;root = insert(root, x);}public long lowerBound(long x) {BalancedNode node = root;long ans = Long.MAX_VALUE;while (node != null) {if (x == node.val) {return x;}if (x < node.val) {ans = node.val;node = node.left;} else {node = node.right;}}return ans;}public long upperBound(long x) {BalancedNode node = root;long ans = Long.MAX_VALUE;while (node != null) {if (x < node.val) {ans = node.val;node = node.left;} else {node = node.right;}}return ans;}public int[] rank(long x) {BalancedNode node = root;int ans = 0;while (node != null) {if (x < node.val) {node = node.left;} else {ans += (node.left != null ? node.left.size : 0) + node.count;if (x == node.val) {return new int[]{ans - node.count + 1, ans};}node = node.right;}}return new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE};}private BalancedNode insert(BalancedNode node, long x) {if (node == null) {return new BalancedNode(x, rand.nextInt());}++node.size;if (x < node.val) {node.left = insert(node.left, x);if (node.left.seed > node.seed) {node = node.rightRotate();}} else if (x > node.val) {node.right = insert(node.right, x);if (node.right.seed > node.seed) {node = node.leftRotate();}} else {++node.count;}return node;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/394872.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java参数传递

Java参数传递 一、 方法重载 一个类中可以存在多个同名的方法&#xff0c;只要这些方法的参数列表不同即可。 参数列表不同&#xff1a;参数个数或者参数类型不同方法重载与修饰符、返回值类型等统统无关&#xff0c;只看参数列表 二、 可变个数的形参 从Java5.0开始&…

陶瓷材质的防静电架空地板越来越受欢迎的原因

目前市面上的陶瓷防静电架空地板主要分为两种&#xff1a;钢基和硫酸钙基。前者是以全钢冲孔裸板作为板基&#xff0c;经粘接、固定整型和灌浆的方式加工而成&#xff0c;后者是以复合硫酸钙板为基材&#xff0c;表面粘接防静电陶瓷砖&#xff0c;四周导电PVC边条封边。近年来陶…

【C++】vector 的模拟实现

&#x1f4e2;博客主页&#xff1a;https://blog.csdn.net/2301_779549673 &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01; &#x1f4e2;本文由 JohnKi 原创&#xff0c;首发于 CSDN&#x1f649; &#x1f4e2;未来很长&#…

02_快速启动 Demo 创建 Electron 项目、electron-forge 搭建一个 electron 项目、手动创建electron项目

快速启动 Demo 创建 Electron 项目 一、克隆一个仓库、快速启动一个项目二、electron-forge 搭建一个 electron 项目三、手动搭建一个 electron 项目四、开发工具中配置 Eslint 一、克隆一个仓库、快速启动一个项目 要使用 git 的话首先电脑上面需要安装 git //克隆示例项目的…

Qt3D给圆环等立体图形添加纹理图片

添加纹理图片&#xff0c;首先需要自己找一个纹理图&#xff0c;当然了&#xff0c;随便什么图片都行。 创建3D图形的主要步骤查看另一篇文章。 这里主要代码如下&#xff1a; 使用QTextureLoader加载图片&#xff0c;图片路径需为qrc:/的路径。 auto *planeTransform1 ne…

嵌入式学习day13(C高级Linux命令)

一丶进程管理命令 1.grep 功能&#xff1a;从文件中查找字符串 格式&#xff1a;grep "要查找的字符串" 文件名 精确查找&#xff1a;grep "\<要查找的字符串\>" 文件名 结合ps以及管道&#xff1a;ps -ef | grep a.out: 从进程信息中查找带…

10个理由告诉你,为什么鸿蒙是下一个职业风口!

在当今科技飞速发展的时代&#xff0c;新的技术和趋势不断涌现&#xff0c;为人们带来了前所未有的机遇和挑战。鸿蒙操作系统作为我国自主研发的创新成果&#xff0c;正逐渐成为科技领域的焦点&#xff0c;被认为是下一个职业风口。 10个理由告诉你&#xff0c;为什么鸿蒙是下一…

【海贼王航海日志:前端技术探索】CSS你了解多少?(二)

目录 1 -> 字体属性 1.1 -> 设置字体 1.2 -> 字体大小 1.3 -> 字体粗细 1.4 -> 文字样式 2 -> 文本属性 2.1 -> 文本颜色 2.1.1 -> 认识RGB 2.1.2 -> 设置文本颜色 2.2 -> 文本对齐 2.3 -> 文本装饰 2.4 -> 文本缩进 2.5 -&g…

vue的nextTick是下一次事件循环吗

如题&#xff0c;nextTick的回调是在下一次事件循环被执行的吗&#xff1f; 是不是下一次事件循环取决于nextTick的实现&#xff0c;如果是用的微任务&#xff0c;那么就是本次事件循环&#xff1b;否则如果用的是宏任务&#xff0c;那么就是下一次事件循环。 我们看下Vue3中…

【Canvas与艺术】黄色立体感放射光芒五角星

【成图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>黄色立体感放射光芒五角星</title><style type"text/c…

Html详解——Vue基础

HTML是什么&#xff1f; 超文本标记语言&#xff08;英语&#xff1a;HyperText Markup Language&#xff0c;简称&#xff1a;HTML&#xff09;是一种用来结构化 Web 网页及其内容的标记语言。网页内容可以是&#xff1a;一组段落、一个重点信息列表、也可以含有图片和数据表…

[Vue]Vue3从入门到精通-综合案例分析

一.Vue是什么&#xff1a; 概念&#xff1a;Vue是一个用于构建用户界面的渐进式的框架 以下的内容是自里向外的 声明式渲染(Vuejs核心包)组件系统(Vuejs核心包)客户端路由VueRouter大规模状态管理Vuex构建工具Webpack/Vite Vue的两种使用方式&#xff1a; Vue核心包开发-&…

DSL domain specific language of Kola

How we design Kola - ApiHugKola background, Kola a consumer driver tester frameworkhttps://apihug.com/zhCN-docs/kola/003_dsl_contract Concept 在 Kola 定位中 Kola 是什么, 是致力于提供一个让相关各方都能够理解共同创造的测试框架和工具。 同时 Kola 是建立于业界…

node中使用http创建web服务器

1.案例代码 // 1.导入http模块 const http require(http)// 2.创建web服务器实例 const server http.createServer()// 3.为服务器实例绑定request事件&#xff0c;监听客户的请求 server.on(request,function(req,res){console.log(欢迎来到服务器);// req.url是客户端请求…

Kubernets(k8s) 网络原理二:Pod访问外网

上一篇文章中&#xff0c;我们介绍了pod与宿主机通信&#xff0c;并且通过network namespace模拟了通信过程。回顾整个流程&#xff0c;无非就涉及到两个东西&#xff0c;通信设备和路由规则。 本文要讲的&#xff0c;也离不开这两个东西&#xff0c;只不过需要对容器IP进行额…

学习c语言第24天(练习)

编程题 第一题 最大公约数最小公倍数求和 //求最大公约数和最小公倍数之和 //暴力求解 //int main() //{ // int n 0; // int m 0; // while (scanf("%d %d", &n, &m)2) // { // int min n < m ? n : m; // int max n > m ? n : m; //…

Stable Diffusion 使用详解(7)---AI 摄影

目录 背景 底模的选择 例子 majicMix GirlFriendMix&#xff08; Lora&#xff09; 对比效果 LEOSAMs MoonFilm ADetailer 使用 说明 例子 问题 处理方式 效果 背景 魔法师使用魔法作的画有时候太过完美&#xff0c;以至于有点脱离真实摄影的感觉&#xff0c;我们…

【电控笔记z14z16】增加霍尔元件分辨率

霍尔传感器用的不多?实际增量编码器更好 z14 假设60度内速度不变 z16(更简单的方法)BLDC

【机器学习】BP神经网络正向计算

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 BP神经网络正向计算1. 引言2. BP神经网络结构回顾3. 正向计算的基本原理4. 数学…

7.3.1.算法设计与分析-总结及真题讲解

总结 分治法特征&#xff1a;把一个问题拆分成多个小规模的相同子问题&#xff0c;一般可用递归解决。 经典问题&#xff1a;斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔 回溯法特征&#xff1a;系统的搜索一个问题的所有解或任一解。 经典问题…