首页/新闻资讯/正文详情

DeepSeek LeetCode 528. 按权重随机选择 Java实现

发布时间:2026/11/6 8:51:09 来源:云帆数科 栏目:资讯中心
DeepSeek    LeetCode 528. 按权重随机选择 Java实现
LeetCode 528. 按权重随机选择Java思路前缀和 二分查找把权重数组 w 展开成区间w [1, 3, 2] 前缀和 [1, 4, 6] 下标 0 占区间 [0, 1) —— 长度 1 下标 1 占区间 [1, 4) —— 长度 3 下标 2 占区间 [4, 6) —— 长度 2随机生成 r ∈ [0, total)在前缀和数组中二分查找第一个 r 的位置 idxidx 就是答案。因为每个下标对应的区间长度正好等于它的权重所以命中概率 权重 / 总权重。代码实现classSolution{privatefinalint[]prefix;// 前缀和数组privatefinalinttotal;// 总权重privatefinalRandomrandomnewRandom();publicSolution(int[]w){intnw.length;prefixnewint[n];intsum0;for(inti0;in;i){sumw[i];prefix[i]sum;}totalsum;}publicintpickIndex(){// 随机生成 [0, total) 之间的整数inttargetrandom.nextInt(total);// 二分查找第一个 prefix[mid] target 的下标intleft0,rightprefix.length-1;while(leftright){intmidleft(right-left)/2;if(prefix[mid]target){leftmid1;}else{rightmid;}}returnleft;}}示例验证w [1, 3, 2]prefix [1, 4, 6]total 6随机 r 二分结果 idx 对应区间0 0 [0, 1)1 1 [1, 4)2 1 [1, 4)3 1 [1, 4)4 2 [4, 6)5 2 [4, 6)命中概率下标 0 → 1/6下标 1 → 3/6下标 2 → 2/6正好等于权重比例。✅复杂度· 构造O(n)· pickIndexO(log n)二分查找· 空间O(n)前缀和数组易错点区间是左闭右开random.nextInt(total) 生成 [0, total)配合第一个 target的二分刚好不重不漏。若写成 [0, total] 或二分条件写成 边界会出错target 0 时容易误判。二分边界模板这里用的是找第一个满足条件的位置的经典写法left right right mid最后返回 left。溢出题目约束下 total ≤ 10^9int 足够若权重更大需改用 long。Random 线程安全java.util.Random 是线程安全的内部用 CAS但多线程高并发下可考虑 ThreadLocalRandom.current().nextInt(total) 提升性能inttargetThreadLocalRandom.current().nextInt(total);不要每次 pickIndex 重新构建前缀和前缀和只需构造一次pickIndex 只做二分。另一种写法TreeMapclassSolution{privatefinalTreeMapInteger,IntegermapnewTreeMap();privatefinalinttotal;privatefinalRandomrandomnewRandom();publicSolution(int[]w){intsum0;for(inti0;iw.length;i){sumw[i];map.put(sum,i);// 前缀和 - 下标}totalsum;}publicintpickIndex(){inttargetrandom.nextInt(total);// 返回 key target 的最小条目returnmap.higherEntry(target).getValue();}}TreeMap.higherEntry(target) 返回严格大于 target 的最小 key正好对应二分结果。代码更简洁但常数略大。推荐面试中写前缀和 二分最标准能体现对边界和概率映射的理解。TreeMap 版本可作补充。

相关推荐

DeepSeek    LeetCode 526. 优美的排列 Java实现
DeepSeek LeetCode 526. 优美的排列 Java实现

LeetCode 526. 优美的排列(Java) 题目要点 用 1 ~ n 构造排列 perm(下标从 1 开始),要求对每个位置 i: perm[i] % i 0 或 i % perm[i] 0返回满足条件的排列数量。方法一:回溯 剪枝 从位置 … · 2026/11/6 8:51:09

DiscoveryRSI:通过递归学习发现有价值的假设
DiscoveryRSI:通过递归学习发现有价值的假设

26年10月,论文“DiscoveryRSI: Recursively Learning to Discover Valuable Hypotheses”,来自PhAI Labs、香港中文大学、密歇根大学、新加坡国立大学、复旦大学、北京大学人民医院、北京大学、斯坦福大学、香港科技大学、加州大学圣塔芭芭拉分校、东南大… · 2026/11/6 8:50:05

CAN 技术系列 03 · CAN 位定时与同步
CAN 技术系列 03 · CAN 位定时与同步

📚 CAN总线技术系列 持续更新中 本系列从差分电气层一路打到 Linux SocketCAN,把"两根线"背后的电气/协议/控制器/驱动/实战全拧成一根线。 👉 想系统追更,戳这里查看完整专栏: 【CAN 技术系列】 👉 其他技… · 2026/11/6 8:50:05

息县考电工证在哪里?考前押题怎么准备更稳妥?
息县考电工证在哪里?考前押题怎么准备更稳妥?

息县考电工证在哪里?考前押题怎么准备更稳妥? 你是不是正盯着手机屏幕,心里直打鼓?手上没个电工证,连面试都进不去,更别说上班了。尤其是刚毕业或者想转行的你, 急需特种作业证才能上岗找工作 。现在正是关键时刻,别再犹豫了,… · 2026/11/6 19:10:54

高级电工证落户政策内部消息:学历不高怕报不上名?看这里全搞定
高级电工证落户政策内部消息:学历不高怕报不上名?看这里全搞定

高级电工证落户政策内部消息:学历不高怕报不上名?看这里全搞定 你是不是也这样? 学历不高怕报不上名 ,想考个高级电工证,但又担心自己能不能报名、能不能通过?其实, 高级电工证落户政策 里的“门槛”没你想的那么高,关键是你是不是了解… · 2026/11/6 19:10:54

工地太忙根本没时间复习考试?低压配电电工证真实经历帮你破局
工地太忙根本没时间复习考试?低压配电电工证真实经历帮你破局

工地太忙根本没时间复习考试?低压配电电工证真实经历帮你破局 工地太忙根本没时间复习考试,这几乎是每个电工从业者的真实写照。尤其是刚从济源应届毕业的你,可能一边在工地搬砖,一边还要准备低压配电电工证考试。别急,我就是从那个阶段走过来的,今天就… · 2026/11/6 19:10:54

一七年电工证千万别踩坑 怎么复审延期看这篇就够了
一七年电工证千万别踩坑 怎么复审延期看这篇就够了

一七年电工证千万别踩坑 怎么复审延期看这篇就够了 证书过期了不知道怎么复审延期?你不是一个人,这几乎是所有持证人最头疼的问题,尤其是在【一七年电工证】这类老证书持有者中,复审流程、政策变动、地方差异,稍有不慎就可能踩坑。今天我们就从真实案例… · 2026/11/6 19:10:54

高压电工作业真伪查询怎么查?真实经历告诉你该怎么操作
高压电工作业真伪查询怎么查?真实经历告诉你该怎么操作

高压电工作业真伪查询怎么查?真实经历告诉你该怎么操作 刚拿到高压电工作业证,却不知道怎么查真假?你不是一个人。我认识不少刚出社会的电工,拿着证去工地找工作,结果因为证书是假的被拒绝,连面试都没机会。这种情况在我们这一行太常见了。今天就用我这… · 2026/11/6 19:10:54

徐工特种车型号一览表在哪考 40分钟搞定复审延期攻略
徐工特种车型号一览表在哪考 40分钟搞定复审延期攻略

徐工特种车型号一览表在哪考 40分钟搞定复审延期攻略 工地太忙根本没时间复习考试,这几乎是所有一线特种作业人员的心声。特别是像南阳卧龙区这类施工密集区域,很多持证人员都面临着证书复审、延期甚至补办的问题,但时间总是不够用,复习成了“奢侈品”… · 2026/11/6 19:09:54

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 10:29:23

三菱PLC数据采集到数据库的时序设计:Python+MC协议实战
三菱PLC数据采集到数据库的时序设计:Python+MC协议实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 1:02:11

ASIC主模式RTL设计:状态机与三态驱动的流片级实现
ASIC主模式RTL设计:状态机与三态驱动的流片级实现

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 1:02:11

STM32嵌入式C++开发:GDB调试与Renode仿真实战指南
STM32嵌入式C++开发:GDB调试与Renode仿真实战指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 1:02:11

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:28:03

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/6 10:29:23

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码