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

数据结构练习题——Java实现

20240531-时间复杂度

1、消失的数字

方法一:位运算

两个数字一样的数组,其中一个数组中少了一个数字,定义一个变量分别异或两个数组,结果即为缺少的数字

    class Solution {public int missingNumber(int[] nums) {int xor = 0;int n = nums.length;//获取数组长度for (int i = 0; i < n; i++) {//因为该数组少一个数,所以i < nxor ^= nums[i];}for (int i = 0; i <= n; i++) {//假设该数组数字为0~n,不少数字,所以i <= nxor ^= i;}//分别遍历两数组进行异或操作,相同数字异或得零//其他数字均出现两次,只有一个数字出现一次return xor;}}

方法二:数学规律

1到n的等差数列的总和,减去当前数组元素的总和,即为缺少的数字

class Solution {public int missingNumber(int[] nums) {int n = nums.length;//等差数列总和 = (首项 + 尾项)* 项数 / 2int total = (1 + n) * n / 2;//当前数组的总和int sum = 0;for(int i=0;i<n;i++){sum += nums[i];}//缺少值 = 等差数列总和 - 数组总和return total - sum;}
}

 2、旋转数组

这个不会,暂且搁置

3、给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是(   )

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

选B了

解析:

正确答案A,数组元素有序,所以a,b两个数可以分别从开始和结尾处开始搜索,根据首位元素的和是否大于sum,决定搜索的移动,整个数组被搜索一遍,就可以得到结果,所以时间复杂度为O(n)

4、设某算法的递推公式是T(n)=T(n-1)+n,T(0)=1,则求该算法中第n项的时间复杂度为()

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

解析:

5、分析以下函数的时间复杂度

void fun(int n) {int i=l;while(i<=n)i=i*2;
}

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

解析:

D,此函数有一个循环,但是循环没有被执行n次,i 每次都是2倍进行递增,所以只会被执行

6、分析以下函数的空间复杂度

public static int[][] get2Array(int n){int[][] array = new int[n][];for(int i = 0; i < n; i++) {array[i] = new int[n-i];n--;}return array;
}

A.O(1)

B.O(N)

C.O(N^2)

D.O(logN)

解析:

相关文章:

数据结构练习题——Java实现

20240531-时间复杂度 1、消失的数字 方法一&#xff1a;位运算 两个数字一样的数组&#xff0c;其中一个数组中少了一个数字&#xff0c;定义一个变量分别异或两个数组&#xff0c;结果即为缺少的数字 class Solution {public int missingNumber(int[] nums) {int xor 0;int…...

行为设计模式之状态模式

文章目录 概述定义结构图 2.代码示例小结 概述 定义 状态模式(state pattern)的定义: 允许一个对象在其内部状态改变时改变它的行为。 对象看起来似乎修改了它的类。 状态模式就是用于解决系统中复杂对象的状态转换以及不同状态下行为的封装问题.。状态模式将一个对象的状态…...

找回以前的视频:技术与实践3个指南

你们有没有发现现在视频已经成为我们生活中不可或缺的一部分了&#xff1f;不管是在工作场合做演示、在学习时看教学视频&#xff0c;还是在休闲娱乐时追剧看电影&#xff0c;视频都扮演着超级重要的角色。 然而误删或手机故障的发生很可能将以前的视频清除。本文将深入探讨手…...

GCN 代码解析(一) for pytorch

Graph Convolutional Networks 代码详解 前言一、数据集介绍二、文件整体架构三、GCN代码详解3.1 utils 模块3.2 layers 模块3.3 models 模块3.4 模型的训练代码 总结 前言 在前文中&#xff0c;已经对图卷积神经网络&#xff08;Graph Convolutional Neural Networks, GCN&am…...

2024年云计算、信号处理与网络技术国际学术会议(ICCCSPNT 2024)

2024年云计算、信号处理与网络技术国际学术会议&#xff08;ICCCSPNT 2024&#xff09; 2024 International Academic Conference on Cloud Computing, Signal Processing, and Network Technology&#xff08;ICCCSPNT 2024&#xff09; 会议简介&#xff1a; 2024年云计算、…...

希尔排序法

希尔排序为插入排序的优化&#xff0c;即将数组分组&#xff0c;将每一组进行插入排序&#xff0c;每一组排成有序后&#xff0c;最后整体就变有序了。 上面gap2&#xff0c;即5&#xff0c;14&#xff0c;18&#xff0c;27&#xff0c;68为一组&#xff1b;13&#xff0c;20&a…...

thinkphp6.0版本下子查询sql处理

目录 一&#xff1a;背景 二&#xff1a;查询实例 三&#xff1a;总结 一&#xff1a;背景 我们在实际业务的开发过程中&#xff0c;经常会碰到这样的场景&#xff0c;查询某些部门的客户信息&#xff0c;查询下过订单的客户信息。这里查询客户信息实际上就用到了子查询&…...

flowable工作流 完成任务代码 及扩展节点审核人(实现多级部门主管 审核等)详解【JAVA+springboot】

低代码项目 使用flowable 工作流 完成任务代码 详解 可以看到 complete()方法 传递了流程变量参数var 前端传递此参数就可以实现 流程中 审批 更新流程变量参数var 也可以进行更多扩展 实现流程中更新表单内容功能 启动流程实例代码 实现对于流程自定义 动态节点审核人 功…...

【电源专题】一体成型电感为什么需要注意耐压问题

对于电感,我们在电路上使用的很多,如升压、降压、滤波等电路中基本上使用到了电感。电感的种类有很多,电感从不同的角度会有不同的分类。如可以根据否屏蔽、工艺类型、磁性材料类型等可分为多类,这在文章:【分立元件】电感器(inductor)——简介中有做了一些简单的介绍。…...

如何看待时间序列与机器学习?

GPT-4o 时间序列与机器学习的关联在于&#xff0c;时间序列数据是一种重要的结构化数据形式&#xff0c;而机器学习则是一种强大的工具&#xff0c;用于从数据中提取有用的模式和信息。在很多实际应用中&#xff0c;时间序列与机器学习可以结合起来&#xff0c;发挥重要作用。…...

vue图标不显示

静态:有可能路径错误 <img src"../../assets/images/index1.png"> <img src"/assets/images/index2.png"> 动态&#xff1a;需要解析 <div v-for"item in userList" :key"item.id"> <img :src"getUrl(i…...

文件夹如何加密码全攻略,5个文件夹加密方法新手也能学

文件夹如何加密码&#xff1f;在这个互联网时代&#xff0c;隐私保护越来越受到大家的重视。我们在日常工作中&#xff0c;有时候会接触一些比较重要的文件&#xff0c;为了不让这些文件信息被泄露&#xff0c;所以我们可以给文件夹设置密码保护。那要怎么给文件夹设置密码呢&a…...

useState和store的区别

useState 和 useStore 是 React 应用中用于管理数据状态的两种不同的 Hook。它们在功能和用途上有一些区别&#xff1a; useState useState 是 React 提供的一个 Hook&#xff0c;用于在函数组件中添加局部状态。每个 useState 调用都会返回一个数组&#xff0c;包含两个元素…...

vscode远程登录阿里云服务器【使用密钥方式--后期无需再进行密码登录】【外包需要密码】

1&#xff1a;windows主机上生成【私钥】【公钥】 1.1生成公钥时不设置额外密码 1.2生成公钥时设置额外密码【给外包人员使用的方法】 2&#xff1a;在linux服务器中添加【公钥】 3&#xff1a;本地vscode连接linux服务器的配置 操作流程如下 1.1本地终端中【生成免密登录…...

解决uniapp里的onNavigationBarSearchInputClicked不生效

如何在uniapp里使用onNavigationBarSearchInputClicked。 1、在page.json里配置 "pages": [{"path": "pages/index/index","style": {"navigationBarTitleText": "首页","navigationStyle": "cu…...

Windows下搭建Cmake编译环境进行C/C++文件的编译

文章目录 1.下载Cmake2.安装MinGW-w643.进行C/C文件的编译 1.下载Cmake 网址&#xff1a;https://cmake.org/download/ 下载完成后安装&#xff0c;勾选“Add CMake to the system PATH for the current user" 点击Finish完成安装&#xff0c;在cmd窗口验证一下是否安…...

实用新型专利申请材料的撰写与准备

在科技创新日益活跃的今天&#xff0c;实用新型专利的申请与保护显得尤为重要。实用新型专利作为一种重要的知识产权形式&#xff0c;对于推动科技进步、促进经济发展具有重要意义。 首先我们需要明确实用新型专利的定义。实用新型专利是指对产品的形状、构造或者其结合所提出…...

代码随想录算法训练营第60天|● 84.柱状图中最大的矩形

84. 柱状图中最大的矩形 和昨天的思路完全一样 单调栈直接解了 双指针法特别麻烦 class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights.insert(0,0)heights.append(0)stack[0]res0for i in range(1,len(heights)):while stack and heights…...

让AI给你写代码(9.3):一点改进,支持扩展本地知识库

改进目标&#xff0c;当输入提示问题后&#xff0c;能匹配到本地知识库的需求&#xff0c;然后AI按匹配到的需求给出代码并进行自动测试&#xff1b; 如果无法匹配到本地需求&#xff0c;可以直接输入生成逻辑&#xff0c;再由AI生成&#xff0c;然后支持用户把新需求插入本地库…...

探索煤化工厂巡检机器人的功能、应用及前景

大家都知道、煤化工厂是以煤为原料生产化工产品的工厂&#xff0c;存在易燃易爆、高温、中毒等隐患等。因此&#xff0c;对煤化工厂进行巡检是非常必要的。巡检旨在是定时对厂内设备运行异常、泄漏等问题&#xff0c;并及时进行处理&#xff0c;保障工作场所的安全。除了以上存…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...