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

算法 稀疏数组 数组优化 数组压缩 二维数组转稀疏数组 算法合集(二)

 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. 五子棋游戏&#xff0c;玩家对战一半停战休息&#xff0c;此时需要存储当前对战双方棋子信息 a. 采用二维数组存储&#xff1a; 0为空&#xff0c; 1代表黑棋 2代表蓝色棋子 b. 棋盘为11行&#xff0c;11列 > int [][] chessArray new int [11][11]; c. 出现的问题&am…...

交换机端口安全实验

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

c# 本地化中英文切换

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

rabbitmq的优先级队列

在我们系统中有一个 订单催付 的场景&#xff0c;我们的客户在天猫下的订单 , 淘宝会及时将订单推送给我们&#xff0c;如果在用户设定的时间内未付款那么就会给用户推送一条短信提醒&#xff0c;很简单的一个功能对吧&#xff0c;但是&#xff0c;tianmao商家对我们来说&#…...

SpringBoot的Cacheable缓存注解

当我们的应用程序需要频繁地读取和写入数据时&#xff0c;为了提高应用程序的性能&#xff0c;我们通常会使用缓存技术。Spring Boot 提供了一种简单而强大的缓存框架&#xff0c;它可以轻松地将数据缓存到 Redis 中。 在 Spring Boot 中可以在方法上简单的加上注解实现缓存。…...

uniapp的 picker 日期时间选择器

效果图&#xff1a; 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

页面分为两个表格&#xff0c;当两边的表格数据量大时&#xff0c;分页样式就会受到影响&#xff0c;可以将跳转按钮的个数减少 页面分页代码如下 页面效果...

[开发|java] 将数组使用环境变量传递配置给typesafe配置示例

参考文献 如何将一组值作为环境变量提供给 typesafe/lightbend 配置 示例 假设需要如下配置要设置环境传递 whitlist [/oauth/render,/oauth/callback]需要使用如下的方式传递到 conf 文件中: whitlist [] whitlist.0 /oauth/render whitlist.1 /oauth/render...

MAC苹果电脑如何压缩rar文件?

作为开发者&#xff0c;想必主力开发机肯定都以苹果的MacBook为主&#xff0c;究其原因&#xff0c;为非是因为其对开发者的友好性&#xff0c;且可同时进行iOS 以及android的app开发&#xff0c;但是windows在这方面就欠缺太多了&#xff0c;虽然很多人说可以使用&#xff0c;…...

浅析编程中的语法糖

1、理解语法糖 1.1.什么是语法糖&#xff1f; 语法糖是一种编程语言的特性&#xff0c;它并不引入新功能&#xff0c;而是通过提供更简洁、易读的语法形式&#xff0c;使代码编写和理解变得更加轻松。它有点像是一种“甜蜜”的语法&#xff0c;让我们在不改变底层逻辑的情况下…...

【【萌新的STM32学习23----数据通信的基本类型】】

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

标准库STL容器使用值语义

C自学精简实践教程 目录(必读) 标准库STL的容器都是值语义的。 即&#xff0c;无法将一个变量放到容器里。容器里存放的只是我们放进去的变量的拷贝&#xff08;副本&#xff09;。 示例&#xff1a; #include <iostream> #include <vector> using namespace s…...

dockerfile 命令详解(三)

CMD 和 ENTRYPOINT 区别 CMD #指定这个容器启动的时候要运行的命令&#xff0c;只有最后一个会生效&#xff0c;可被替代 ENTRYPOINT #指定这个容器启动的时候要运行的命令&#xff0c;可以追加命令 FROM #基础镜像&#xff0c;一切从这里开始构建 MAINTAINER #…...

使用这个插件,fiddler抓包直接生成httprunner脚本

har2case可以将.har文件转化成yaml格式或者json格式的httprunner的脚本文件&#xff0c;生成.har格式文件可以借助 fiddler 或 Charles 抓包工具 友情提示&#xff1a; 录制脚本&#xff0c;只是一个过渡&#xff0c;从0到1的一个过渡&#xff0c;如果让你直接写脚本&#xf…...

干翻Dubbo系列第十五篇:Rest协议基于SpringBoot的规范化开发

文章目录 文章说明 一&#xff1a;Rest协议简介 二&#xff1a;搭建开发环境 1&#xff1a;父项目里边引入的新的版本内容 2&#xff1a;Api中的操作 3&#xff1a;Provider模块 三&#xff1a;编码 1&#xff1a;API模块 2&#xff1a;Provider模块 3&#xff1a;Co…...

文件上传后端处理页面

最近想搭建一个完整的网站&#xff0c;加深理解&#xff0c;困难重重啊&#xff0c;遇到很多问题 前端&#xff1a;非常原始的代码&#xff0c;没有用任何框架 <form method"post" enctype"multipart/form-data" action"upfile.php"><…...

小红书母婴类产品同质化严重,如何在市场中脱颖而出?

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

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支持建设的&#xff0c;随着企业的规模扩大、服务请求的增长&#xff0c;服务质量不可避免出现了急剧的下降。IT支持团队进入消防员模式&#xff0c;他们只能奔波于解决请求&#xff0c;避免服务失败。没有ITIL所定义的流程体系&#xff0c;IT团队失…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; 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如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

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

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

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

12.找到字符串中所有字母异位词

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