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

【再临数据结构】Day1. 稀疏数组

前言

  这不单单是稀疏数组的开始,也是我重学数据结构的开始。因此,在开始说稀疏数组的具体内容之前,我想先说一下作为一个有着十余年“学龄”的学生,所一直沿用的一个学习方法:3W法。我认为,只有掌握了正确的学习方法,才能真正的达到“事半功倍”的境界。

  何为3W?其实就是3问:What?Why?How?

简单解释一下:

 1.What:界定问题,首先要搞清楚这个问题是什么。
    若连题都读不懂,就不必说如何解题了。

 2.Why:分析问题,要分析问题的本质和原因。
    在读懂题意的前提下,知道它考察的方向是什么,这样后续才能顺着这个方向去解题。

 3.How:解决问题,通过目标导向思维解决问题。
    经过前两问的思考,想必你已经透过题目明白了这道题真正考察的是什么,那么就要考虑如何去处理、解决掉它。

1.What?

  好,我们开始稀疏数组的具体内容。在了解为什么要学习它和怎样使用之前,我们要先了解稀疏数组是什么。
  我们通过具体的应用场景来了解它,比如说,你用编程语言需要写一个简单的五子棋小游戏,它需要能够正常玩,并且有存盘和读取功能。
此时你能想到的问题就是:

  1. 如何绘制棋盘并存储棋盘上落子的坐标信息。
  2. 如何实现存盘和读盘的功能。

  首先来思考第一个问题:总所周知,棋盘由行和列组成。那么,你很自然的想到了数学中的坐标系,将其落子点看做一组横纵坐标。因此你打算使用二维数组这一数据结构来模拟棋盘。用0代表没有落子,1代表落黑子,2代表落白字。
  好,问题轻松写意地解决了。你开始写代码,作为一个有着程序员精神的人,你很快地通过百度解决了第二个问题。但你的程序员灵魂并不甘于止步于此,又想琢磨如何优化,此时迎来了一个新的问题:若一个11*11大小的棋盘,只落了两个子。此时需要存盘,如何才能尽可能多的节省存储空间?
  很显然,若使用0来代表未落子的交点,那么这个二维数组中就有着许许多多的“无效数据”。只有当黑子 / 白子落在这个交点上,它才是“有效数据”。此时,稀疏数组就出现在你的面前了。

2.Why?

  为什么要使用稀疏数组而不是别的数据结构?为什么它能实现对二维数组的压缩?
  别急,一图以蔽之。
在这里插入图片描述

稀疏数组的处理方式:

1、分别记录原数组的行个数、列个数、有多少个“有效数据”。【第一行】
2、将不同有效数据的元素的行、列、值信息记录在一个小规模的数组中,从而缩小程序的规模。【其余行】

稀疏数组很简单,上面两点足以概括。

具体思路

在这里插入图片描述

二维数组转稀疏数组

1.遍历原始的二维数组,得到有效数据的个数 sum
2根据sum就可以创建稀疏数组 sparseArr int[sum+1][3]
注:此处之所以为[sum+1]的原因是第一列要存储原数组的大小及有效数的个数(sum)
3.将二维数组的有效数据数据存入到稀疏数组

稀疏数组转二维数组

1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的chessArr2= int[11][11]
⒉.在读取稀疏数组后几行的数据,并赋给原始的二维数组即可.
  以上过程再配合Java的IO操作(写入磁盘文件,文件读入内存)就可以实现类似下棋游戏过程中的“存盘”,“读取” 的操作。

3.How?

二维数组转稀疏数组

    //将二维数组压缩为稀疏数组public static int[][] toSparseArray(int[][] arr){//1.遍历二维数组,获取到二维数组中有效元素的个数int sum = 0;                    //有效元素个数//增强版双重for循环,实现遍历二维数组的操作for (int[] ints : arr) {for (int anInt : ints) {if (anInt != 0) {sum++;}}}//2.根据sum的个数及稀疏数组的设定来建立一个原数组所对应的稀疏数组int[][] sparseArray = new int[sum+1][3];//3.根据原数组的情况为稀疏数组赋值//3.1第一行存储原二维数组的信息,首先填写它的数据sparseArray[0][0] = arr.length;     //原二维数组行长度sparseArray[0][1] = arr[0].length;  //原二维数组列长度sparseArray[0][2] = sum;            //有效数的个数//3.2其余行存储有效数在原二维数组中的行、列及数值int index = 0;for(int i=0; i<arr.length; i++){for (int j=0; j<arr[0].length; j++){if (arr[i][j] != 0){index++;sparseArray[index][0] = i;sparseArray[index][1] = j;sparseArray[index][2] = arr[i][j];}}}return sparseArray;}

稀疏数组还原为二维数组

    //将稀疏数组转换为原二维数组public static int[][] toErWei(int[][] arr){//1.新建一个二维数组,读取稀疏数组的第一行,根据第一行数据初始化二维数组int[][] erWei = new int[arr[0][0]][arr[0][1]];  //此时二维数组大小确定,内容全是0//2,读取稀疏数组后几行数据,并赋给初始化好的二维数组for (int i=1;i<arr.length;i++){  //i=1表示从稀疏数组的第二行开始读取//0存储行信息,1存储列信息,2存储值信息erWei[arr[i][0]][arr[i][1]]=arr[i][2];  //认真理解}return erWei;}

源码

public class sparseArray {public static void main(String[] args) {int[][] erWei = new int[11][11];for (int i=0; i<erWei.length-1; i++){for (int j=0; j<erWei[0].length-1; j++){erWei[i][j] = 0;}}//设定有效元素erWei[2][5] = 16;erWei[1][6] = 14;erWei[7][9] = 28;erWei[4][5] = 20;erWei[1][3] = 17;erWei[6][4] = 79;//输出原二维数组printArr(erWei);//转化为稀疏数组int[][] sparseArray = toSparseArray(erWei);printArr(sparseArray);//转化为二维数组int[][] ErWei = toErWei(sparseArray);printArr(ErWei);}//将二维数组压缩为稀疏数组public static int[][] toSparseArray(int[][] arr){//1.遍历二维数组,获取到二维数组中有效元素的个数int sum = 0;                    //有效元素个数//增强版双重for循环,实现遍历二维数组的操作for (int[] ints : arr) {for (int anInt : ints) {if (anInt != 0) {sum++;}}}//2.根据sum的个数及稀疏数组的设定来建立一个原数组所对应的稀疏数组int[][] sparseArray = new int[sum+1][3];//3.根据原数组的情况为稀疏数组赋值//3.1第一行存储原二维数组的信息,首先填写它的数据sparseArray[0][0] = arr.length;     //原二维数组行长度sparseArray[0][1] = arr[0].length;  //原二维数组列长度sparseArray[0][2] = sum;            //有效数的个数//3.2其余行存储有效数在原二维数组中的行、列及数值int index = 0;for(int i=0; i<arr.length; i++){for (int j=0; j<arr[0].length; j++){if (arr[i][j] != 0){index++;sparseArray[index][0] = i;sparseArray[index][1] = j;sparseArray[index][2] = arr[i][j];}}}return sparseArray;}//将稀疏数组转换为原二维数组public static int[][] toErWei(int[][] arr){//1.新建一个二维数组,读取稀疏数组的第一行,根据第一行数据初始化二维数组int[][] erWei = new int[arr[0][0]][arr[0][1]];  //此时二维数组大小确定,内容全是0//2,读取稀疏数组后几行数据,并赋给初始化好的二维数组for (int i=1;i<arr.length;i++){  //i=1表示从稀疏数组的第二行开始读取//0存储行信息,1存储列信息,2存储值信息erWei[arr[i][0]][arr[i][1]]=arr[i][2];  //认真理解}return erWei;}//输出数组信息public static void printArr(int[][] arr){for (int[] ints : arr){for (int anInt : ints) {System.out.print(anInt + " ");}System.out.println();}System.out.println("---------------------");}
}

运行结果如下:
在这里插入图片描述

在这里插入图片描述
  如上图所示,二维数组压缩为稀疏数组确实极大地节省了存储空间。同样可以通过稀疏数组在读盘时将其进行复原,达到预期需求。

相关文章:

【再临数据结构】Day1. 稀疏数组

前言 这不单单是稀疏数组的开始&#xff0c;也是我重学数据结构的开始。因此&#xff0c;在开始说稀疏数组的具体内容之前&#xff0c;我想先说一下作为一个有着十余年“学龄”的学生&#xff0c;所一直沿用的一个学习方法&#xff1a;3W法。我认为&#xff0c;只有掌握了正确的…...

二十四、MongoDB 聚合运算( aggregate )

MongoDB 聚合( aggregate ) 用于处理数据&#xff0c;比如统计平均值,求和等。然后返回计算后的数据结果 MongoDB 聚合有点类似 SQL 语句中的 COUNT( * ) aggregate() 方法 MongoDB aggregate() 为 MongoDB 数据库提供了聚合运算 语法 aggregate() 方法的语法如下 > d…...

【C++】6.模板初阶

交换两个数 任何一个类型交换还要重新写一个函数 如何解决&#xff1f; 模板->写跟类型无关的函数 1.泛型编程 泛型编程&#xff1a;编写与类型无关的通用代码&#xff0c;是代码复用的一种手段。模板是泛型编程的基础。 如何写一个函数适用所有类型的交换? #include &…...

Docker部署Airbyte

Linux环境部署前置要求机器配置2c4g(最低)&#xff0c;4c8g&#xff08;推荐&#xff09;dockerdocker-compose &#xff08;要求新版本的docker-compose&#xff09;安装airbyte,打开终端&#xff0c;进入你想安装airbyte的目录。#Clone代码 git clone https://github.com/air…...

2023王道考研数据结构笔记第一章绪论

第一章 绪论 1.1 数据结构的基本概念 1.数据&#xff1a;数据是信息的载体&#xff0c;是描述客观事物属性的数、字符以及所有能输入到计算机中并被程序识别和处理的符号的集合。 2.数据元素&#xff1a;数据元素是数据的基本单位&#xff0c;通常作为一个整体进行考虑和处理…...

告别空指针让代码变优雅,Optional使用图文例子源码解读

一、前言 我们在开发中最常见的异常就是NullPointerException&#xff0c;防不胜防啊&#xff0c;相信大家肯定被坑过&#xff01; 这种基本出现在获取数据库信息中、三方接口&#xff0c;获取的对象为空&#xff0c;再去get出现&#xff01; 解决方案当然简单&#xff0c;只…...

【C++】哈希——unordered系列容器|哈希冲突|闭散列|开散列

文章目录一、unordered系列关联式容器二、哈希概念三、哈希冲突四、哈希函数五、解决哈希冲突1.闭散列——开放定址法2.代码实现3.开散列——开链法4.代码实现六、结语一、unordered系列关联式容器 在C98中&#xff0c;STL提供了底层为红黑树结构的一系列关联式容器&#xff0c…...

mysql-面试

锁&#xff1a; mysql的锁分为全局锁、表锁、行锁、间隙锁 全局锁&#xff1a;Flush tables with read lock 可以全局设计库为只读 表锁&#xff1a;一种是表锁&#xff0c;一种是元数据锁&#xff08;meta data lock&#xff0c;MDL&#xff09; lock tables t1 read,t2 wi…...

【夏虫语冰】Win10局域网下两台电脑无法ping通: 无法访问目标主机

文章目录1、简介2、修改高级共享设置3、启用防火墙规则4、局域网内的其他主机访问NAT模式下的虚拟机4.1 虚拟机网络设置4.2 访问测试4.2.1 http测试4.2.2 curl测试4.2.3 telnet测试4.2.4 端口占用测试5、其他结语1、简介 ping 192.168.31.134ping主机ip时&#xff0c;访问无法…...

大数据框架之Hadoop:MapReduce(三)MapReduce框架原理——Join多种应用

3.7.1Reduce Join 1、工作原理 Map端的主要工作&#xff1a;为来自不同表或文件的key/value对&#xff0c;打标签以区别不同来源的记录。然后用连接字段作为key&#xff0c;其余部分和新加的标志作为value&#xff0c;最后进行输出。 Reduce端的主要工作&#xff1a;在Reduc…...

SSRF漏洞原理、危害以及防御与修复

一、SSRF漏洞原理漏洞概述SSRF&#xff08;Server-side Request Forge&#xff0c;服务端请求伪造&#xff09;是一种由攻击者构造形成由服务端发起请求的安全漏洞。一般情况下&#xff0c;SSRF攻击的目标是从外网无法访问的内部系统。正是因为它是由服务端发起的&#xff0c;所…...

CV学习笔记-ResNet

ResNet 文章目录ResNet1. ResNet概述1.1 常见卷积神经网络1.2 ResNet提出背景2. ResNet网络结构2.1 Residual net2.2 残差神经单元2.3 Shortcut2.4 ResNet50网络结构3. 代码实现3.1 Identity Block3.2 Conv Block3.3 ResNet网络定义3.4 整体代码测试1. ResNet概述 1.1 常见卷积…...

百亿数据,毫秒级返回查询优化

近年来公司业务迅猛发展&#xff0c;数据量爆炸式增长&#xff0c;随之而来的的是海量数据查询等带来的挑战&#xff0c;我们需要数据量在十亿&#xff0c;甚至百亿级别的规模时依然能以秒级甚至毫秒级的速度返回&#xff0c;这样的话显然离不开搜索引擎的帮助&#xff0c;在搜…...

cpp之STL

STL原理 STL ⼀共提供六⼤组件&#xff0c;包括容器&#xff0c;算法&#xff0c;迭代器&#xff0c;仿函数&#xff0c;适配器和空间配置器&#xff0c;彼此可以组合套⽤。容器通过配置器取得数据存储空间&#xff0c;算法通过迭代器存取容器内容&#xff0c;仿函数可以协助算…...

基于Spring Boot开发的资产管理系统

文章目录 项目介绍主要功能截图:登录首页信息软件管理服务器管理网络设备固定资产明细硬件管理部分代码展示设计总结项目获取方式🍅 作者主页:Java韩立 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目…...

Markdown总结

文字的着重标记与段落的层次划分 Tab键可以缩进列表&#xff1b; shift Tab&#xff1a;取消缩进列表 加粗&#xff08;****&#xff09;、斜体&#xff08;**&#xff09;高亮&#xff1a;xxx$$&#xff1a;特殊标记删除&#xff1a;~~xxx~~多级标题&#xff1a;######无序列…...

字节跳动软件测试岗4轮面经(已拿34K+ offer)...

没有绝对的天才&#xff0c;只有持续不断的付出。对于我们每一个平凡人来说&#xff0c;改变命运只能依靠努力幸运&#xff0c;但如果你不够幸运&#xff0c;那就只能拉高努力的占比。 2021年10月&#xff0c;我有幸成为了字节跳动的一名测试工程师&#xff0c;从外包辞职了历…...

docker - 搭建redis集群和Etcd

概述 由于业务需要&#xff0c;需要把之前的分布式架构调整成微服务&#xff0c;把老项目迁移到k8s的服务中&#xff0c;再开始编码之前&#xff0c;需要再本地环境里做相应的准备工作&#xff0c;使用docker搭建redis集群&#xff0c;Etcd主要是注册本地的rpc服务。 Liunx O…...

Java程序开发中如何使用lntelliJ IDEA?

完成了IDEA的安装与启动&#xff0c;下面使用IDEA创建一个Java程序&#xff0c;实现在控制台上打印HelloWorld!的功能&#xff0c;具体步骤如下。 1.创建Java项目 进入New Project界面后&#xff0c;单击New Project选项按钮创建新项目&#xff0c;弹出New Project对话框&…...

【Linux】理解进程地址空间

&#x1f34e;作者&#xff1a;阿润菜菜 &#x1f4d6;专栏&#xff1a;Linux系统编程 ​我们在学习C语言的时候&#xff0c;都学过内存区域的划分如栈、堆、代码区、数据区这些。但我们其实并不真正理解内存 — 我们之前一直说的内存是物理上的内存吗&#xff1f; 前言 我们…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

【Ftrace 专栏】Ftrace 参考博文

ftrace、perf、bcc、bpftrace、ply、simple_perf的使用Ftrace 基本用法Linux 利用 ftrace 分析内核调用如何利用ftrace精确跟踪特定进程调度信息使用 ftrace 进行追踪延迟Linux-培训笔记-ftracehttps://www.kernel.org/doc/html/v4.18/trace/events.htmlhttps://blog.csdn.net/…...

开疆智能Ethernet/IP转Modbus网关连接鸣志步进电机驱动器配置案例

在工业自动化控制系统中&#xff0c;常常会遇到不同品牌和通信协议的设备需要协同工作的情况。本案例中&#xff0c;客户现场采用了 罗克韦尔PLC&#xff0c;但需要控制的变频器仅支持 ModbusRTU 协议。为了实现PLC 对变频器的有效控制与监控&#xff0c;引入了开疆智能Etherne…...