当前位置:网站首页>2022.07.13_每日一题
2022.07.13_每日一题
2022-07-31 06:07:00 【诺.い】
382. 链表随机节点
题目描述
给你一个单链表,随机选择链表的一个节点,并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution
类:
Solution(ListNode head)
使用整数数组初始化对象。int getRandom()
从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
示例:

输入
[“Solution”, “getRandom”, “getRandom”, “getRandom”, “getRandom”, “getRandom”]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]
解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个,每个元素被返回的概率相等。
提示:
- 链表中的节点数在范围
[1, 104]
内 -104 <= Node.val <= 104
- 至多调用
getRandom
方法104
次
进阶:
- 如果链表非常大且长度未知,该怎么处理?
- 你能否在不使用额外空间的情况下解决此问题?
- 水塘抽样
- 链表
- 数学
- 随机化
coding
class Solution1 {
ListNode head;
int size;
public Solution(ListNode head) {
this.head = head;
ListNode cur = head;
while (cur != null) {
cur = cur.next;
size ++;
}
}
public int getRandom() {
int randomNum = (int) (Math.random() * size);
int cnt = 0;
ListNode cur = head;
while (cur != null) {
if (cnt == randomNum) {
return cur.val;
}
cur = cur.next;
cnt ++;
}
return 0;
}
}
// ---------------------------------------------------------------
class Solution2 {
List<Integer> list;
public Solution(ListNode head) {
list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
}
public int getRandom() {
return list.get((int) (Math.random() * list.size()));
}
}
边栏推荐
猜你喜欢
(border-box) The difference between box model w3c and IE
Difficulty comparison between high concurrency and multithreading (easy to confuse)
批量免费文字翻译
嵌入式系统驱动初级【2】——内核模块下_参数和依赖
2.(1)栈的链式存储、链栈的操作(图解、注释、代码)
从 Google 离职,前Go 语言负责人跳槽小公司
SCI写作指南
解决win11/win10在登陆界面(解锁界面)点击获取每日壁纸无效的问题 - get Daily Lockscreen and Wallpaper - Win11/10的登录界面背景图片在哪里?
Project exercise - memorandum (add, delete, modify, check)
Core Tower Electronics won the championship in the Wuhu Division of the 11th China Innovation and Entrepreneurship Competition
随机推荐
线程唤醒机制
双倍数据速率同步动态随机存储器(Double Data Rate Synchronous Dynamic Random Access Memory, DDR SDRAM)- 逻辑描述部分
Obtaining server and client information
讲解实例+详细介绍@Resource与@Autowired注解的区别(全网最全)
Explain the example + detail the difference between @Resource and @Autowired annotations (the most complete in the entire network)
MySQL的触发器
2022.7.29 数组
什么是半波整流器?半波整流器的使用方法
数据库概论 - MySQL的简单介绍
Third-party library-store
leetcode 406. Queue Reconstruction by Height 根据身高重建队列(中等)
测试 思维导图
mysql索引失效的常见9种原因详解
一文读懂 MongoDB 和 MySQL 的差异
【第四章】详解Feign的实现原理
DirectExchange交换机简单入门demo
codec2 BlockPool:unreadable libraries
关于求反三角函数的三角函数值
项目 - 如何根据最近30天、最近14天、最近7天、最近24小时、自定义时间范围查询MySQL中的数据?
【Go语言刷题篇】Go完结篇函数、结构体、接口、错误入门学习