当前位置：首页 > news >正文

（leetcode算法题）382. 链表随机节点

news 来源：原创 2025/5/16 23:01:14

如果给你一个智能记录 k行内容的小笔记本，从一本你也不知道有多少行的 C++ Primer 中进行摘抄，你应该怎么做才能让抄写的时候能让书中的每一行都等概率的出现在小笔记本中？

答：准备好一个公平的轮盘和一个巨大的摇奖机，

轮盘上有k个数字，每个数字对应小笔记本的一行，抽中每个数字的概率相同

摇奖机装置可以从放入其中的 i 个纸条中等概率的抽出一个纸条

开始遍历 C++ Primer 中的每一行，对于前k行，直接将他们的行号写到纸条上，放入摇奖机中

并且在一个record数组中记录下这些行号

在k行之后，同样将行号写到纸条上，然后把纸条放到摇奖机中开始摇奖，如果摇出来的纸条是轮盘上的某个数字num，那么将这个新放入的纸条上的行号替换调record中记录的这个数字，

直到把 C++ Primer 中的所有行都遍历完，就能达到效果，

用数学归纳法就可以证明所有行都可以等概率的出现在小笔记本中，而且这个概率是 k / n

其中n 是 C++ Primer 中的行数

假设读到 i - 1行，每一行能够出现在小笔记本上的概率是 k / (i - 1)

那么读到 i - 1 行时，第一行能够进入小笔记本的概率是

k / (i - 1) * (1 - (k / i) * (1 / k)) = k / i

图片来自B站UP主五点七边的视频【经典算法题】蓄水池抽样算法_哔哩哔哩_bilibili

382的代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
ListNode* _head;
public:Solution(ListNode* head) {_head = head;}int getRandom() {int val = _head->val;ListNode* nextnode = _head->next;int count = 2;while(nextnode){int x = rand() % count;if(x == 0){val = nextnode->val;}count++;nextnode = nextnode->next;}return val;}
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(head);* int param_1 = obj->getRandom();*/

（leetcode算法题）382. 链表随机节点

如果给你一个智能记录 k行内容的小笔记本，从一本你也不知道有多少行的 C Primer 中进行摘抄，你应该怎么做才能让抄写的时候能让书中的每一行都等概率的出现在小笔记本中？ 答：准备好一个公平的轮盘和一个巨大的摇奖机&#xff0c…...

编程日记 2025/5/16 23:01:14

【Pytorch报错】AttributeError: cannot assign module before Module.init() call

代码： import torch.nn as nnclass Model(nn.Module):def __init__(self, input_dim, output_dim):self.linear nn.Linear(input_dim, output_dim) def forward(self, x):out self.linear(x)return outmodel Model(1, 1)报错： --------------------…...

编程日记 2025/5/16 20:17:55

深入理解计算机系统—虚拟内存（一）

一个系统中的进程是与其他进程共享 CPU 和主存资源的。然而，共享主存会形成特殊的挑战。随着对 CPU 需求的增长，进程以某种合理的平滑方式慢了下来。但是如果太多的进程需要太多的内存，那么它们中的一些就根本无法运行。为了更加有效地管理内…...

编程日记 2025/5/16 21:21:08

[Qt] 输入控件 | Line | Text | Combo | Spin | Date | Dial | Slider

目录输入类控件 1、Line Edit 录入个人信息使用正则表达式验证输入框的数据验证两次输入的密码一致切换显示密码 2、Text Edit 获取多行输入框的内容验证输入框的各种信号 3、Combo Box 使用下拉框模拟麦当劳点餐从文件中加载下拉框的选项 4、Spin Box 调整…...

编程日记 2025/5/16 14:59:25

【信息系统项目管理师】高分论文：论信息系统项目的风险管理（数字化联合审查管理系统）

更多内容请见：备考信息系统项目管理师-专栏介绍和目录文章目录论文一、全盘考虑，编制项目风险管理计划二、务实高效，做好项目的风险识别三、客观严谨，进行定性风险分析四、客观严谨，进行定量风险分析五、未雨绸缪，做好规划风险应对六、控制执行，实施风险应对七、做好…...

编程日记 2025/5/16 20:39:12

设计模式结构型外观模式（Facade Pattern）与常见技术框架应用解析

外观模式（Facade Pattern）是一种结构型设计模式，它的核心思想是将一个复杂的子系统封装在一个外观类中，为子系统提供一个统一的接口。通过这个接口，客户端可以简化对子系统的访问，而无需直接与子系统中的各…...

编程日记 2025/5/6 4:51:51

《learn_the_architecture_-_generic_interrupt_controller_v3_and_v4__lpisn》学习笔记

1.LPI（Locality-specific Peripheral Interrupts）是一种基于消息的中断（Message Signaled Interrupt，MSI），由中断翻译服务(ITS)提供翻译。这是因为LPI的设计目标是为系统中大量的设备提供高效的中断管理&am…...

编程日记 2025/5/14 19:57:53

java 常量池详解

目录 java 常量池详解一静态常量池（Static Constant Pool）1.1 概述1.2 存储内容1.3 特点1.4 示例二运行时常量池（Runtime Constant Pool）2.1 概述2.2 存储内容2.3 特点2.4 示例三基础类型常量池（Primitive Type C…...

编程日记 2025/5/16 21:57:07

aardio —— 虚表 —— 模拟属性框

写了个简单的属性框例程，抛砖引玉，期待你做出更丰富强大的功能。可折叠行、可输入文本、可下拉选择、支持下拉选择图片、颜色等功能。只有想不到，没有做不到，发挥你的想象力吧。 import win.ui; import godking.comboboxEx im…...

编程日记 2025/5/11 21:20:37

企业微信——智能表格学习

智能表格应用限制条件获取 token https://developer.work.weixin.qq.com/document/10013#%E5%BC%80%E5%8F%91%E6%AD%A5%E9%AA%A4 开发步骤你可以通过以下步骤，使用access_token来访问企业微信的接口。需要注意的是，所有的接口需使用Https协议、Js…...

编程日记 2025/5/11 13:05:09

2501d,jingo优化

原文大家好,我重构和优化了一下jin.go这里: 我去掉了vibe.d依赖,因为它又慢又大,而且我无法与2版本交朋友.当仅运行1000个vibe纤程时,不仅应用崩溃,甚至图形系统驱动也崩溃一次,这需要重启笔记本电脑. 当前,我用小栈大小的本地流(4kb)解决. 我真很期待photon的稳定性,以恢复支…...

编程日记 2025/5/16 6:11:12

实景三维点云处理专业软件ArcGIS根据DSM生成地表点云集

常见的实景三维处理软件及其特色功能如下： 一、专业实景三维建模软件 Agisoft Metashape 高精度建模：能够生成高精度的三维模型，精度可以达到厘米级甚至毫米级，适用于需要详细测量和分析的项目，如文物保护和建筑测量。…...

编程日记 2025/5/16 21:47:07

山东大学人工智能导论期末复习概念汇总

人工智能概念汇总V2 —Nevertheless 简介 [!NOTE] 本文是在原版的基础上，面向期末而进行的删减版本建议使用pdf版本，排版和图片显示完全。如有需要，可私信发送邮箱地址 PDF版本： 山东大学人工智能导论概念汇总pdf版山东大学软…...

编程日记 2025/5/16 22:41:17

Ubuntu下安装Android Sdk

下载android sdk命令行工具 https://developer.android.com/studio?hlzh-cn#command-tools mkdir android-sdk cd android-sdk unzip commandlinetools-linux-11076708_latest.zip 添加环境变量到~/.bashrc export ANDROID_HOME$HOME/android-sdk export PATH$PATH:$ANDRO…...

编程日记 2025/5/16 22:37:36

c语言中GHashTable的使用

前言:最近在c代码中需要用到键值对的存储，由于没有map，需要自己实现或者使用库函数，g_hash_table_new是GLib中的库函数，但使用起来会有很多坑，记录一下构建hash表g_hash_table_new GHashTable* g_hash_table_new(GH…...

编程日记 2025/5/15 2:50:39

Conda清理缓存

参考：1、2...

编程日记 2025/5/16 21:45:19

【每日学点鸿蒙知识】导入cardEmulation、自定义装饰器、CallState状态码顺序、kv配置、签名文件配置

1、HarmonyOS 无法导入cardEmulation？ 在工程entry mudule里的index.ets文件里导入cardEmulation失败可以按照下面方式添加SystemCapability；在src/main/syscap.json(此文件需要手动创建）中添加如下内容 {"devices": {"gen…...

编程日记 2025/5/16 21:03:29

【从零开始入门unity游戏开发之——C#篇42】C#补充知识——随机数（Random）、多种方法实现string字符串拼接、语句的简写

文章目录一、随机数1、Random.Next()生成随机整数示例：生成一个随机整数生成指定范围内的随机整数 2、Random.NextSingle生成随机浮点数示例：生成随机浮点数 3、生成随机字母或字符示例：生成随机字母示例：生成随机小写字母二、…...

编程日记 2025/5/16 22:24:39

深入解析 Conda 安装的默认依赖包及其作用：conda create安装了哪些包（中英双语）

深入解析 Conda 安装的默认依赖包及其作用当我们使用 Conda 创建新环境时，例如执行命令： conda create -n olmes python3.10Conda 会自动为我们安装一系列基础依赖包，保证 Python 环境能够正常运行。这些包不仅是我们开发的基础工具&#…...

编程日记 2025/5/16 20:23:01

《Vue3实战教程》35：Vue3测试

如果您有疑问，请观看视频教程《Vue3实战教程》测试为什么需要测试自动化测试能够预防无意引入的 bug，并鼓励开发者将应用分解为可测试、可维护的函数、模块、类和组件。这能够帮助你和你的团队更快速、自信地构建复杂的 Vue 应用。与任何应用一…...

编程日记 2025/5/16 8:51:22

Mysql监视器搭建

Mysql监视器搭建资源下载在：Mysql监视器资源包查询问题：CPU、连接数、慢查询 --> 暴增 1、exporter进行Mysql信息采集修改my.cnf [client] userroot password数据库密码 host:数据库URL port3306启动命令 mysqld_exporter.exe --config.my-c…...

编程日记 2025/5/16 6:54:30

Linux(centos)安装 MySQL 8 数据库(图文详细教程)

前言前几天写了个window系统下安装Mysql的博客，收到很多小伙伴私信需要Linux下安装Mysql的教程，今天这边和大家分享一下，话不多说，看教程。一、删除以前安装的MySQL服务一般安装程序第一步都需要清除之前的安装痕迹&#xff…...

编程日记 2025/5/9 11:02:03

软件工程大作业——图书管理系统/图书个性化推荐与实现系统

目录 1 绪论 1.1研究背景 1.2研究现状 1.3研究内容 2 系统关键技术 2.1 Spring Boot框架 2.2 JAVA技术 2.3 MYSQL数据库 2.4 B/S结构 3 系统分析 3.1 可行性分析 3.1.1 技术可行性 3.1.2经济可行性 3.1.3操作可行性 3.2 系统性能分析 3.3 系统功能分析 3.4系统流程分析 3.4.1登…...

编程日记 2025/5/8 11:15:38

Linux下编译安装PETSc

本文记录在Linux下编译安装PETSc的流程。零、环境操作系统Ubuntu 22.04.4 LTSVS Code1.92.1Git2.34.1GCC11.4.0CMake3.22.1oneAPI2024.2.1 一、安装依赖 1.1 安装oneAPI 参见：Get the Intel oneAPI Base Toolkit , Get the Intel oneAPI HPC Toolkit 1.2 安…...

编程日记 2025/5/15 21:52:43

检索增强生成

概述检索增强生成（Retrieval-Augmented Generation，RAG）是一种将信息检索与语言模型相结合的技术。由Facebook AI Research于2020年提出，它把数据库的优势与语言模型的优势相结合。它能让模型从外部知识库中检索信息&#xff0c…...

编程日记 2025/5/14 8:17:12

九、Vue 事件处理器

文章目录前言一、基础事件绑定：v-on 指令二、方法调用：组织有序的交互逻辑三、事件修饰符阻止冒泡与默认事件捕获与自身触发单次触发与鼠标按键区分四、按键修饰符前言在 Vue.js 的交互世界里，事件处理器起着举足轻重的作用，它让页面从静态展示迈向动态交互，精准捕捉用户…...

编程日记 2025/5/16 22:41:47

stm32内部flash在线读写操作

stm32内部flash在线读写操作 📍相关开源库文章介绍《STM32 利用FlashDB库实现在线扇区数据管理不丢失》 ✨不同系列，内部flash编程有所区别。例如stm32f1是按照页擦除，半字（16bit）或全字(32bit)数据写入；st…...

编程日记 2025/5/15 10:13:20

DuckDB：密钥管理器及其应用

密钥管理器(Secrets Manager)为所有使用密钥的后端提供了统一的用户界面。密钥信息可以被限定范围，因此不同的存储前缀可以有不同的密钥信息，例如允许在单个查询中连接跨组织的数据。密钥也可以持久化，这样就不需要在每次启动DuckDB时都指定它…...

编程日记 2025/5/16 12:53:11

每日一学——自动化工具（Ansible）

3.1 Ansible 3.1.1 Playbook编写指南嘿，小伙伴们！你们知道吗，运维工作其实也可以变得像搭积木一样简单！今天我们要介绍的就是Ansible，一款非常流行的自动化运维工具。通过Ansible，我们可以用Playbook来描…...

编程日记 2025/5/11 21:36:32

typescripts语法笔记

游戏引擎：图形渲染系统，特效系统，物理系统，各个功能集合。 cocoscreator是将cocos2d-x封装成了可视化编辑。面向对象转变成面向组件开发。 ts编程是js编程语言的超集。基础类型""可以转换成字符串类型，适用…...

编程日记 2025/5/12 4:22:32

TypyScript从入门到精通

TypyScript从入门到精通 TypyScript 是什么？增加了什么环境搭建二、为何需要 TypeScript三、编译 TypeScript四、类型声明五、类型推断基本类型六、类型总览JavaScript 中的数据类型TypeScript 中的数据类型1. 上述所有 JavaScript 类型2. 六个新类型：3.…...

编程日记 2025/5/15 17:33:32

vscode代码AI插件Continue 安装与使用

“Continue” 是一款强大的插件，它主要用于在开发过程中提供智能的代码延续功能。例如，当你在编写代码并且需要进行下一步操作或者完成一个代码块时，它能够根据代码的上下文、语法规则以及相关的库和框架知识，为你提供可能的代码续…...

编程日记 2025/5/9 6:06:52

STM32-笔记20-测量按键按下时间

1、按键按下的时间-思路我们先检测下降沿信号，检测到以后，在回调函数里切换成检测上升沿信号，当两个信号都检测到的时候，这段时间就是按键按下的时间，如图所示：>N*(ARR1)CCRx的值 N是在这段时间内&…...

编程日记 2025/5/15 10:45:57

继承与多态 - 继承机制、虚函数、纯虚函数

引言 C 是一种支持面向对象编程（OOP）的编程语言，继承和多态是 OOP 的两个核心概念。通过继承，我们可以创建新的类，这些新类可以重用现有类的代码，并且可以根据需要进行扩展或修改。多态则允许我们编写更加…...

编程日记 2025/5/13 12:10:36

微信小程序：正确输出＜小于，大于＞符号

错误写法 1、如果直接输入<符号会直接报错，>能正常使用，如图标红的是错误写法 2、输入html的<&gt的写法，会原样输入符号解决方法采用变量的方式输出 1、js写入变量 2、wxml直接写...

编程日记 2025/5/11 4:28:17

uni-app tab 双击事件监听

1、data中定义属性，用于临时记录点击次数 tabClick: {touchNum: 0 },2、添加页面事件监听方法 onTabItemTap(e) {this.tabClick.touchNumsetTimeout(()>{if(this.tabClick.touchNum > 2){// 双击执行代码区}this.tabClick.touchNum 0}, 250) },个人博客&am…...

编程日记 2025/5/14 15:41:02

GIT 企业级开发学习 1_基本操作

本节主要命令： git init ls 不能列出 .git ls -a 列出 .git 创建本地仓库 1. 初始化 Git 仓库 git init • 初始化一个新的 Git 仓库，在当前目录下生成一个 .git 隐藏文件夹，用于存储版本控制信息。 2. 查看隐藏文件 ls -a • 使用 ls …...

编程日记 2025/5/16 2:32:28

Computed在Vue2、Vue3写法的不同

在 Vue 2 和 Vue 3 中，computed 的写法有一些区别，特别是在 Vue 3 中新增了组合式 API 和 setup 语法糖。以下是不同写法的详细比较： 1. Vue 2 选项式 API 写法在 Vue 2 中，computed 是一个选项，直接在 computed 对…...

编程日记 2025/5/14 11:21:58

Hive集群安装部署

上传安装包并解压 cd /ddhome/tools tar -zxvf apache-hive-3.1.2-bin.tar.gz -C /ddhome/bin/ cd /ddhome/bin/ mv apache-hive-3.1.2-bin hive注意：如果Hive要使用Spark计算引擎，需要重新编译Hive， 这里已经编译完毕修改配置文件 cd …...

编程日记 2025/5/12 14:48:09

卸载干净 IDEA（图文讲解）

目录 1、卸载 IDEA 程序 2、注册表清理 3、残留清理 1、卸载 IDEA 程序点击屏幕左下角 Windows 图标 -> 设置-控制面板->intellij idea 勾选第一栏 Delete IntelliJ IDEA 2022.2 caches and local history，表示同时删除 IDEA 本地缓存以及历史。 Delete I…...

编程日记 2025/5/14 15:21:01

Gitea代码仓服务搭建

特点与优势轻量级：Gitea是一个轻量级的Git服务，提供了快速、稳定的代码托管和协作开发环境。它资源占用低，适合在资源受限的环境中运行。易于安装和部署：Gitea提供了简单易用的安装和部署方式，支持多种安装方式，包括二进制文件、Docker容器等，并提供了详细的文档和配置…...

编程日记 2025/5/16 18:05:42

什么情况会导致JVM退出？

大家好，我是锋哥。今天分享关于【什么情况会导致JVM退出？】面试题。希望对大家有帮助； 什么情况会导致JVM退出？ 1000道互联网大厂Java工程师精选面试题-Java资源分享网 JVM（Java Virtual Machine，Java虚…...

编程日记 2025/5/16 11:46:46

docker 安装influxdb

docker pull influxdb mkdir -p /root/influxdb/data docker run -d --name influxdb -p 8086:8086 -v /root/influxdb/data:/var/lib/influxdb influxdb:latest#浏览器登录：http://192.168.31.135:8086，首次登录设置用户名密码：admin/admin1…...

编程日记 2025/5/7 21:09:14

TLS: WebRTC中ThreadManager的线程局部存储

1. 什么是线程局部存储： 线程局部存储（TLS，Thread-Local Storage）： 线程局部存储（TLS）允许每个线程保存一份独立的数据副本，避免多个线程共享数据导致的竞争问题。每个线程可以根…...

编程日记 2025/5/13 17:15:20

[Qt] 万字详解 | 常用控件 | Button | Label | LCD | ProgressBar

目录按钮类控件 1、Push Button 按钮 2、Radio Buttion 单选 click、press、release、toggled 的区别 3、Check Box 复选 4、Tool Button 显示类控件 1、Label 2、LCD Number 3、ProgressBar 4、Calendar Widget 按钮类控件 1、Push Button 按钮概述&#xff1a…...

编程日记 2025/5/11 9:12:19

【数据仓库】hadoop3.3.6 安装配置

文章目录概述下载解压安装伪分布式模式配置hdfs配置hadoop-env.shssh免密登录模式设置初始化HDFS启动hdfs配置yarn启动yarn 概述该文档是基于hadoop3.2.2版本升级到hadoop3.3.6版本，所以有些配置，是可以不用做的，下面仅记录新增操作&#…...

编程日记 2025/5/14 20:37:10

ffmpeg八大开发库

‌FFmpeg八大库‌是指FFmpeg项目中最重要的八个库，它们各自承担不同的功能，共同构成了FFmpeg的强大功能。以下是这八大库的详细介绍： ‌libavcodec‌：负责音频和视频的编解码。它支持多种编解码器，如H.264、AAC、MP3、…...

编程日记 2025/5/16 9:22:34

Uniapp中使用`wxml-to-canvas`开发DOM生成图片功能

Uniapp中使用wxml-to-canvas开发DOM生成图片功能在移动端开发中，生成图片是一个常见需求，例如用于分享海报、生成动态二维码等。在Uniapp框架中，我们可以通过wxml-to-canvas插件轻松实现将DOM转化为图片的功能。本文将详细介绍如何在Uniapp…...

编程日记 2025/4/25 1:44:06

【09】深入解析 Three.js 官网示例：下雪粒子特效与场景渲染的实现（webgpu_compute_particles_snow.html）

引言 Three.js 是一个强大的 JavaScript 库，用于在网页上创建和渲染 3D 场景。本文将深入分析一段 Three.js 官网示例代码，详细解释其实现思路和主要功能代码，帮助读者更好地理解和掌握 Three.js 的应用。官网代码地址：https://g…...

编程日记 2025/5/15 10:45:58

相关文章：