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

LeetCode-384-打乱数组

在这里插入图片描述

1、列表随机

为了能够初始化数组,我们使用nums保存当前的数组,利用orignal保存初始化数组。为了实现等可能随机打乱,考虑到随机数本质上是基于随机数种子的伪随机,我们采用如下的方式实现等可能随机:我们将所有元素压入列表,每次随机选择一个位置上的数字,按顺序将其放入打乱后的数组中,而后我们从列表中删除当前元素。

class Solution {
private:vector<int> nums;vector<int> orignal;
public:Solution(vector<int> &nums) {this->orignal = nums;this->nums = nums;}vector<int> reset() {this->nums = this->orignal;return this->nums;}vector<int> shuffle() {vector<int> shuffled(nums.size());list<int> lst(nums.begin(), nums.end());for (int i = 0; i < nums.size(); ++i) {int j = rand() % (lst.size());auto it = lst.begin();advance(it, j);shuffled[i] = *it;lst.erase(it);}copy(shuffled.begin(), shuffled.end(), nums.begin());return nums;}
};

2、Fisher-Yates 洗牌算法

考虑到方法一中随机打乱的时间复杂度达到O(n2)O(n^2)O(n2),我们可以对随机打乱的方式进行进一步的改进:我们在第i次循环中,在[i,n)[i,n)[i,n)中随机选择一个位置j上的元素将其与位置i上的元素进行交换,如此循环直至n次。这样做能够确保我们在O(n)O(n)O(n)的时间复杂度内实现随机打乱。

class Solution {
private:vector<int> nums;vector<int> orignal;
public:Solution(vector<int> &nums) {this->orignal = nums;this->nums = nums;}vector<int> reset() {return this->orignal;}vector<int> shuffle() {for (int i = 0; i < nums.size(); ++i) {int j = i + rand() % (nums.size() - i);swap(nums[i], nums[j]);}return nums;}
};

相关文章:

LeetCode-384-打乱数组

1、列表随机 为了能够初始化数组&#xff0c;我们使用nums保存当前的数组&#xff0c;利用orignal保存初始化数组。为了实现等可能随机打乱&#xff0c;考虑到随机数本质上是基于随机数种子的伪随机&#xff0c;我们采用如下的方式实现等可能随机&#xff1a;我们将所有元素压…...

九龙证券|重大利好!期货公司打新再“解绑”:可直接参与首发网下配售!

时隔近7年&#xff0c;期货公司及其财物办理子公司参加首发证券网下询价和配售事务再次“解绑”。 2月17日&#xff0c;为适应全面实行股票发行注册制变革需求&#xff0c;中国证券业协会&#xff08;以下简称中证协&#xff09;发布《初次公开发行证券网下出资者办理规矩》&am…...

信号完整性设计规则之串扰最小化

本文内容从《信号完整性与电源完整性分析》整理而来&#xff0c;加入了自己的理解&#xff0c;如有错误&#xff0c;欢迎批评指正。 1. 对于微带线和带状线&#xff0c;保持相邻信号路径的间距至少为线宽的2倍。 减小串扰的一种方式就是增大线间距&#xff0c;使线间距等于线…...

Windows Ubuntu双系统 设置时间同步方式

文章目录0 前言1 系统时间机制1.1 Windows时间机制1.2 Ubuntu时间机制2 设置Ubuntu的时间机制3 参考0 前言 在安装windows与ubuntu的双系统之后&#xff0c;会发现两个系统的时间不一致&#xff0c;如果使用了Ubuntu之后&#xff0c;再使用windows就会发现时间变早。原因是两个…...

【python】英雄联盟电竞观赛引擎 掉落提示 CapsuleFarmerEvolved 「Webhook」「钉钉」

介绍 本项目链接 Github本项目链接 Gitee本项目链接 最近在github上发现一个可以用来自动帮你挂英雄联盟(除国服)电竞引擎(可以开出头像和表情)的项目,CapsuleFarmerEvolved,github原项目链接简单来说就是本来是通过看比赛获取奖励的,它帮助你进行观看. 对这个活动有兴趣的话…...

加油站会员管理小程序实战开发教程11

我们已经用了10篇的篇幅讲解了首页的功能,首页主要是用来展示信息的。那么接下来就要进入我们的功能页面了,会员管理一个比较重要的功能是充值的功能。 要想实现充值功能,首先需要办一张会员卡,那什么时候办理会员卡呢?需要先注册成为会员,然后进行开卡的动作。这里要注…...

Python量化入门:投资的风险有哪些?

‍ 在金融资产中,风险是指获得收益的不确定性,通常以实际收益与期望收益的偏离来表示。 影响资产收益的因素有很多,而且不同资产面对的风险也不尽相同,在详细介绍风险度量之前,我们有必要了解一下风险的来源。 资产风险的来源 1. 市场风险 市场风险就是我们常说的系统…...

AV1编码标准整体概述

本专栏预计将从如下几方面详细介绍AV1 (1)从AV1的发展历史,AV1与MPEG、AVS系列的异同。 (2)AV1标准支持的传统编码工具及引入的机器学习工具 (3)开源的AV1编码器及解码器原理详解 (4)AV1的生态 一、AV1产生背景 2010年,谷歌收购了一家叫On2 Technologies的公司。那时VP8…...

基于springboot+vue的药物咨询平台

基于springbootvue的药物咨询平台 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取项目下载方式&#x1f345; 一、项目背景介绍&…...

第64章 SQL 主机教程

如果大神想要大神的网站存储数据在database并从database显示数据&#xff0c;大神的 Web server 必须能使用 SQL 语言访问database系统。 如果大神的 Web server 托管在互联网服务提供商&#xff08;ISP&#xff0c;全称 Internet Service Provider&#xff09;&#xff0c;大…...

【软件测试】python接口自动化测试编写脚本,资深测试总结方法,你的实用宝典......

目录&#xff1a;导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09;前言 接口测试&#xff0…...

MathType公式编辑器过期(禁止联网)的解决方案

MathType公式编辑器过期&#xff08;禁止联网&#xff09;的解决方案 Mathtype公式编辑器无法使用解决方案 MathType联网后显示证书失效&#xff0c;需要重新认证或者购买。或者是MathType成了精简版&#xff0c;只剩两行了。 1. 打开控制面板 方法1 首先大家在电脑中打开W…...

电子技术——共栅和共源共栅放大器的高频响应

电子技术——共栅和共源共栅放大器的高频响应 我们在之前学过无论是是CS放大器还是CE放大器&#xff0c;都可以看做是一个带通&#xff08;IC低通&#xff09;滤波器。在高频处的响应收到输入电容 CinC_{in}Cin​ 的限制&#xff08;主要是米勒效应&#xff09;。因此&#xff…...

基于jsplumb构建的流程设计器

项目背景 最近在准备开发工作流引擎相关模块&#xff0c;完成表结构设计后开始着手流程设计器的技术选型&#xff0c;调研了众多开源项目后决定基于jsplumb.js开源库进行自研开发&#xff0c;保证定制化的便捷性&#xff0c;相关效果图及项目地址如下 项目地址&#xff1a;ht…...

解析从Linux零拷贝深入了解Linux-I/O(下)

接上文解析从Linux零拷贝深入了解Linux-I/O&#xff08;上&#xff09; 大文件传输场景 零拷贝还是最优选吗 在大文件传输的场景下&#xff0c;零拷贝技术并不是最优选择&#xff1b;因为在零拷贝的任何一种实现中&#xff0c;都会有「DMA 将数据从磁盘拷贝到内核缓存区——P…...

【学习笔记2.19】动态规划、MySQL、Linux、Redis(框架)

动态规划 343整数拆分 class Solution {public int integerBreak(int n) {int dp [] new int [n 1];//dp[i]:正整数i拆分后的最大乘积dp[2] 1;for(int i 2;i < n ;i ){for(int j 1;j < i;j ){dp[i] Math.max(dp[i],Math.max(j * (i - j),j * dp[i - j]));} …...

String intern方法理解

1、原理 参考学习视频&#xff1a; https://www.bilibili.com/video/BV1WK4y1M77t/?spm_id_from333.337.search-card.all.click&vd_source4dc3f886f5ce1d43363b603935f02bd1 String s1 “hello”; String s1 "hello"; 代码原理解释如下图String s1 new Str…...

解决 cocosjs与安卓原生集成 崩溃问题

版本:cocos2dx3.16 背景&#xff1a;公司需要把游戏整合到一个APP里面。于是打算通过activity切换的方式实现。但是游戏退出重进之后总会出现fatal 11线程报错。于是有了以下修改。我是底层小白。折腾了好久总算鼓捣出一个能用的版本。优化的地方应该有很多。不过就没去好好优…...

spring注解方式整合Dubbo

系列文章目录 文章目录系列文章目录一、创建一个父工程项目二、创建子模块(dubbo-api模块)二、创建子模块(dubbo-provider模块)三、创建子模块(dubbo-consumer模块)总结一、创建一个父工程项目 这里我们通过Spring Initializer 来帮我们构建一个spring-dubbo这个父项目,点击nex…...

Git详解

Git1.Git简介1.1 Git是什么1.2 Git的作用1.3 Git的简介1.4 Git的下载和安装1.5 Git的安装目录结构如下2.Git代码托管服务2.1 常用的Git代码托管服务1.Git简介 1.1 Git是什么 Git是一个分布式版本控制工具&#xff0c;主要用于管理开发过程中的源代码文件&#xff08;Java类、x…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...