算法 稀疏数组 数组优化 数组压缩 二维数组转稀疏数组 算法合集(二)
1. 五子棋游戏,玩家对战一半停战休息,此时需要存储当前对战双方棋子信息
a. 采用二维数组存储:
0为空,
1代表黑棋
2代表蓝色棋子
b. 棋盘为11行,11列 ==> int [][] chessArray = new int [11][11];
c. 出现的问题:整个数组,只存储了两个值。有点浪费内存空间==>延伸出将0,或其他相同数值抽出来,组成一个新的数组。与代码中抽出公共方法,有异曲同工之妙~
2. 稀疏数组(sparse array) :当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。(例如保存棋盘数据,地图信息等)
3. 稀疏数组的处理方法是:
1) 记录数组一共有几行几列,有多少个不同的值
2) 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
4. 思路分析:
a. 遍历原始二维数组,获取有效的数据个数(非0值个数sum);
b. 创建稀疏数组 int [][] new sparseArr = new [sum + 1][3];
c. 稀疏数组第一行存储原始数组信息,总共11行11列有2条有效数据,存入稀疏数组。所以稀疏数组需要sum+1行。
c. 循环原始数组,将黑棋,蓝棋目前的位置信息,存入稀疏数组
d. 打印下稀疏数组
e. 稀疏数组转换为原始数组(原以为直接两层循环,再判断稀疏数组值是否在此循环内,进行使用,需要多层循环,思路不对。是稀疏数组向原始数组转换(解压缩),用非稀疏数组展示保存的棋盘数据)
package com.nami.algorithm.study.day01;/*** beyond u self and trust u self.** @Author: lbc* @Date: 2023-08-28 17:23* @email: 594599620@qq.com* @Description: keep coding*/
public class SparseArray {public static void main(String[] args) {// 创建一个原始的二维数组 11 * 11// 0: 表示没有棋子, 1 表示 黑子 2 表蓝子int chessArr1[][] = new int[11][11];chessArr1[1][2] = 1;chessArr1[2][3] = 2;chessArr1[4][5] = 2;// 输出原始的二维数组System.out.println("原始的二维数组~~");for (int[] row : chessArr1) {for (int data : row) {System.out.printf("%d\t", data);}System.out.println();}int sum = 0;for (int[] row : chessArr1) {for (int data : row) {if (data > 0) sum++;}}int sparseArr[][] = new int[sum + 1][3];// 给稀疏数组赋值sparseArr[0][0] = 11;sparseArr[0][1] = 11;sparseArr[0][2] = sum;// 遍历二维数组,将非 0 的值存放到 sparseArr 中int count = 0; //count 用于记录是第几个非 0 数据for (int i = 0; i < 11; i++) {for (int j = 0; j < 11; j++) {if (chessArr1[i][j] != 0) {count++;sparseArr[count][0] = i;sparseArr[count][1] = j;sparseArr[count][2] = chessArr1[i][j];}}}// 输出稀疏数组的形式System.out.println();System.out.println("得到稀疏数组为~~~~");for (int i = 0; i < sparseArr.length; i++) {System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);}System.out.println();//将稀疏数组 --》 恢复成 原始的二维数组//1. 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];//2. 在读取稀疏数组后几行的数据(从第二行开始),并赋给 原始的二维数组 即可for (int i = 1; i < sparseArr.length; i++) {chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];}// 输出恢复后的二维数组System.out.println();System.out.println("恢复后的二维数组");for (int[] row : chessArr2) {for (int data : row) {System.out.printf("%d\t", data);}System.out.println();}}}
推荐尚硅谷算法视频
总结:
稀疏数组是对于原始数组的抽象,提取不同值进行存储。 稀疏数组第一行存储原始数组的行信息,列信息,非0值或不同值得个数,进行保存。使用时是稀疏数组向原始数组进行转换使用。它的作用相当于对数组进行压缩。解压缩,同压缩文件流程差不多意思
相关文章:

算法 稀疏数组 数组优化 数组压缩 二维数组转稀疏数组 算法合集(二)
1. 五子棋游戏,玩家对战一半停战休息,此时需要存储当前对战双方棋子信息 a. 采用二维数组存储: 0为空, 1代表黑棋 2代表蓝色棋子 b. 棋盘为11行,11列 > int [][] chessArray new int [11][11]; c. 出现的问题&am…...

交换机端口安全实验
文章目录 一、实验的背景与目的二、实验拓扑三、实验需求四、实验解法1. PC配置IP地址部分2. 在SW1上开启802.1X身份验证3. 创建一个用户身份验证的用户。用户名为wangdaye,密码为1234564.创建一个端口隔离组,实现三台PC无法互相访问 摘要: 本…...

c# 本地化中英文切换
区域 线程默认区域为当前计算机所选区域 设置当前区域: Thread.CurrentThread.CurrentCulture new CultureInfo(“zh-cn”); 获取当前区域: Console.WriteLine(Thread.CurrentThread.CurrentCulture.ToString()); 区域名称: “zh-cn” 中文…...

rabbitmq的优先级队列
在我们系统中有一个 订单催付 的场景,我们的客户在天猫下的订单 , 淘宝会及时将订单推送给我们,如果在用户设定的时间内未付款那么就会给用户推送一条短信提醒,很简单的一个功能对吧,但是,tianmao商家对我们来说&#…...
SpringBoot的Cacheable缓存注解
当我们的应用程序需要频繁地读取和写入数据时,为了提高应用程序的性能,我们通常会使用缓存技术。Spring Boot 提供了一种简单而强大的缓存框架,它可以轻松地将数据缓存到 Redis 中。 在 Spring Boot 中可以在方法上简单的加上注解实现缓存。…...

uniapp的 picker 日期时间选择器
效果图: dateTimePicker.js function withData(param){return param < 10 ? 0 param : param; } function getLoopArray(start,end){var start start || 0;var end end || 1;var array [];for (var i start; i < end; i) {array.push(withData(i))…...

element ui-Pagination
页面分为两个表格,当两边的表格数据量大时,分页样式就会受到影响,可以将跳转按钮的个数减少 页面分页代码如下 页面效果...
[开发|java] 将数组使用环境变量传递配置给typesafe配置示例
参考文献 如何将一组值作为环境变量提供给 typesafe/lightbend 配置 示例 假设需要如下配置要设置环境传递 whitlist [/oauth/render,/oauth/callback]需要使用如下的方式传递到 conf 文件中: whitlist [] whitlist.0 /oauth/render whitlist.1 /oauth/render...
MAC苹果电脑如何压缩rar文件?
作为开发者,想必主力开发机肯定都以苹果的MacBook为主,究其原因,为非是因为其对开发者的友好性,且可同时进行iOS 以及android的app开发,但是windows在这方面就欠缺太多了,虽然很多人说可以使用,…...
浅析编程中的语法糖
1、理解语法糖 1.1.什么是语法糖? 语法糖是一种编程语言的特性,它并不引入新功能,而是通过提供更简洁、易读的语法形式,使代码编写和理解变得更加轻松。它有点像是一种“甜蜜”的语法,让我们在不改变底层逻辑的情况下…...

【【萌新的STM32学习23----数据通信的基本类型】】
萌新的STM32学习23----数据通信的基本类型 数据通信的基本概念 数据通信方式可以分为串行通信,并行通信 串行通信: 数据逐位按顺序依次传输 并行: 数据各位通过多条线同时传输 串行通信: 传输效率低,抗干扰能力强&am…...

标准库STL容器使用值语义
C自学精简实践教程 目录(必读) 标准库STL的容器都是值语义的。 即,无法将一个变量放到容器里。容器里存放的只是我们放进去的变量的拷贝(副本)。 示例: #include <iostream> #include <vector> using namespace s…...
dockerfile 命令详解(三)
CMD 和 ENTRYPOINT 区别 CMD #指定这个容器启动的时候要运行的命令,只有最后一个会生效,可被替代 ENTRYPOINT #指定这个容器启动的时候要运行的命令,可以追加命令 FROM #基础镜像,一切从这里开始构建 MAINTAINER #…...

使用这个插件,fiddler抓包直接生成httprunner脚本
har2case可以将.har文件转化成yaml格式或者json格式的httprunner的脚本文件,生成.har格式文件可以借助 fiddler 或 Charles 抓包工具 友情提示: 录制脚本,只是一个过渡,从0到1的一个过渡,如果让你直接写脚本…...
干翻Dubbo系列第十五篇:Rest协议基于SpringBoot的规范化开发
文章目录 文章说明 一:Rest协议简介 二:搭建开发环境 1:父项目里边引入的新的版本内容 2:Api中的操作 3:Provider模块 三:编码 1:API模块 2:Provider模块 3:Co…...
文件上传后端处理页面
最近想搭建一个完整的网站,加深理解,困难重重啊,遇到很多问题 前端:非常原始的代码,没有用任何框架 <form method"post" enctype"multipart/form-data" action"upfile.php"><…...

小红书母婴类产品同质化严重,如何在市场中脱颖而出?
小红书是一个女性用户为主的平台,其美妆和母婴类产品是平台的主流类目。今天来分享下小红书母婴类产品同质化严重,如何在市场中脱颖而出? 一、小红书平台的母婴传播优势 尽管小红书的母婴品类,已经出现产品同质化严重的问题。但这…...

Typora上使用Mermaid语法展示流程图、时序图、甘特图
你已经安装Typora并打开了一个新文档后,可以按照以下详细步骤在Typora上使用Mermaid语法展示流程图、时序图、甘特图 流程图 使用graph LR声明开始,并使用箭头和连接符号定义节点之间的关系。例如,A --> B表示从节点A指向节点B的箭头连接。graph TB A[界面布局图] -->…...

css中文本阴影特效
文字颜色渐变 .text-clip{color:transparent;font-size: 40px;font-weight: bold;background: linear-gradient(45deg, rgba(0,173,181,1) 0%, rgba(0,173,181,.4) 100%);-webkit-background-clip: text; } 文字模糊 .text-blurry{text-align: center;color: transparent;text-…...

ITIL帮助台怎样帮助企业建设IT服务?
大多数企业都是从邮件开始IT支持建设的,随着企业的规模扩大、服务请求的增长,服务质量不可避免出现了急剧的下降。IT支持团队进入消防员模式,他们只能奔波于解决请求,避免服务失败。没有ITIL所定义的流程体系,IT团队失…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...