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

【线性表 - 数组和矩阵】

数组是一种连续存储线性结构,元素类型相同,大小相等,数组是多维的,通过使用整型索引值来访问他们的元素,数组尺寸不能改变。

  • 知识点
  • 数组与矩阵相关题目

# 知识点

数组的优点:

  • 存取速度快

数组的缺点:

  • 事先必须知道数组的长度
  • 插入删除元素很慢
  • 空间通常是有限制的
  • 需要大块连续的内存块
  • 插入删除元素的效率很低

# 数组与矩阵相关题目

把数组中的 0 移到末尾

283. Move Zeroes (Easy)在新窗口打开

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
public void moveZeroes(int[] nums) {int idx = 0;for (int num : nums) {if (num != 0) {nums[idx++] = num;}}while (idx < nums.length) {nums[idx++] = 0;}
}

改变矩阵维度

566. Reshape the Matrix (Easy)在新窗口打开

Input:
nums =
[[1,2],[3,4]]
r = 1, c = 4Output:
[[1,2,3,4]]Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
public int[][] matrixReshape(int[][] nums, int r, int c) {int m = nums.length, n = nums[0].length;if (m * n != r * c) {return nums;}int[][] reshapedNums = new int[r][c];int index = 0;for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {reshapedNums[i][j] = nums[index / n][index % n];index++;}}return reshapedNums;
}

找出数组中最长的连续 1

485. Max Consecutive Ones (Easy)在新窗口打开

public int findMaxConsecutiveOnes(int[] nums) {int max = 0, cur = 0;for (int x : nums) {cur = x == 0 ? 0 : cur + 1;max = Math.max(max, cur);}return max;
}

有序矩阵查找

240. Search a 2D Matrix II (Medium)在新窗口打开

[[ 1,  5,  9],[10, 11, 13],[12, 13, 15]
]
public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;int m = matrix.length, n = matrix[0].length;int row = 0, col = n - 1;while (row < m && col >= 0) {if (target == matrix[row][col]) return true;else if (target < matrix[row][col]) col--;else row++;}return false;
}

有序矩阵的 Kth Element

378. Kth Smallest Element in a Sorted Matrix ((Medium))在新窗口打开

matrix = [[ 1,  5,  9],[10, 11, 13],[12, 13, 15]
],
k = 8,return 13.

解题参考: Share my thoughts and Clean Java Code在新窗口打开

二分查找解法:

public int kthSmallest(int[][] matrix, int k) {int m = matrix.length, n = matrix[0].length;int lo = matrix[0][0], hi = matrix[m - 1][n - 1];while (lo <= hi) {int mid = lo + (hi - lo) / 2;int cnt = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n && matrix[i][j] <= mid; j++) {cnt++;}}if (cnt < k) lo = mid + 1;else hi = mid - 1;}return lo;
}

堆解法:

public int kthSmallest(int[][] matrix, int k) {int m = matrix.length, n = matrix[0].length;PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();for(int j = 0; j < n; j++) pq.offer(new Tuple(0, j, matrix[0][j]));for(int i = 0; i < k - 1; i++) { // 小根堆,去掉 k - 1 个堆顶元素,此时堆顶元素就是第 k 的数Tuple t = pq.poll();if(t.x == m - 1) continue;pq.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y]));}return pq.poll().val;
}class Tuple implements Comparable<Tuple> {int x, y, val;public Tuple(int x, int y, int val) {this.x = x; this.y = y; this.val = val;}@Overridepublic int compareTo(Tuple that) {return this.val - that.val;}
}

一个数组元素在 [1, n] 之间,其中一个数被替换为另一个数,找出重复的数和丢失的数

645. Set Mismatch (Easy)在新窗口打开

Input: nums = [1,2,2,4]
Output: [2,3]
Input: nums = [1,2,2,4]
Output: [2,3]

最直接的方法是先对数组进行排序,这种方法时间复杂度为 O(NlogN)。本题可以以 O(N) 的时间复杂度、O(1) 空间复杂度来求解。

主要思想是通过交换数组元素,使得数组上的元素在正确的位置上。

public int[] findErrorNums(int[] nums) {for (int i = 0; i < nums.length; i++) {while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {swap(nums, i, nums[i] - 1);}}for (int i = 0; i < nums.length; i++) {if (nums[i] != i + 1) {return new int[]{nums[i], i + 1};}}return null;
}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;
}

类似题目:

  • 448. Find All Numbers Disappeared in an Array (Easy)在新窗口打开,寻找所有丢失的元素
  • 442. Find All Duplicates in an Array (Medium)在新窗口打开,寻找所有重复的元素。

找出数组中重复的数,数组值在 [1, n] 之间

287. Find the Duplicate Number (Medium)在新窗口打开

要求不能修改数组,也不能使用额外的空间。

二分查找解法:

public int findDuplicate(int[] nums) {int l = 1, h = nums.length - 1;while (l <= h) {int mid = l + (h - l) / 2;int cnt = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] <= mid) cnt++;}if (cnt > mid) h = mid - 1;else l = mid + 1;}return l;
}

双指针解法,类似于有环链表中找出环的入口:

public int findDuplicate(int[] nums) {int slow = nums[0], fast = nums[nums[0]];while (slow != fast) {slow = nums[slow];fast = nums[nums[fast]];}fast = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;
}

数组相邻差值的个数

667. Beautiful Arrangement II (Medium)在新窗口打开

Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

题目描述: 数组元素为 1~n 的整数,要求构建数组,使得相邻元素的差值不相同的个数为 k。

让前 k+1 个元素构建出 k 个不相同的差值,序列为: 1 k+1 2 k 3 k-1 ... k/2 k/2+1.

public int[] constructArray(int n, int k) {int[] ret = new int[n];ret[0] = 1;for (int i = 1, interval = k; i <= k; i++, interval--) {ret[i] = i % 2 == 1 ? ret[i - 1] + interval : ret[i - 1] - interval;}for (int i = k + 1; i < n; i++) {ret[i] = i + 1;}return ret;
}

数组的度

697. Degree of an Array (Easy)在新窗口打开

Input: [1,2,2,3,1,4,2]
Output: 6

题目描述: 数组的度定义为元素出现的最高频率,例如上面的数组度为 3。要求找到一个最小的子数组,这个子数组的度和原数组一样。

public int findShortestSubArray(int[] nums) {Map<Integer, Integer> numsCnt = new HashMap<>();Map<Integer, Integer> numsLastIndex = new HashMap<>();Map<Integer, Integer> numsFirstIndex = new HashMap<>();for (int i = 0; i < nums.length; i++) {int num = nums[i];numsCnt.put(num, numsCnt.getOrDefault(num, 0) + 1);numsLastIndex.put(num, i);if (!numsFirstIndex.containsKey(num)) {numsFirstIndex.put(num, i);}}int maxCnt = 0;for (int num : nums) {maxCnt = Math.max(maxCnt, numsCnt.get(num));}int ret = nums.length;for (int i = 0; i < nums.length; i++) {int num = nums[i];int cnt = numsCnt.get(num);if (cnt != maxCnt) continue;ret = Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);}return ret;
}

对角元素相等的矩阵

766. Toeplitz Matrix (Easy)在新窗口打开

1234
5123
9512In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.
public boolean isToeplitzMatrix(int[][] matrix) {for (int i = 0; i < matrix[0].length; i++) {if (!check(matrix, matrix[0][i], 0, i)) {return false;}}for (int i = 0; i < matrix.length; i++) {if (!check(matrix, matrix[i][0], i, 0)) {return false;}}return true;
}private boolean check(int[][] matrix, int expectValue, int row, int col) {if (row >= matrix.length || col >= matrix[0].length) {return true;}if (matrix[row][col] != expectValue) {return false;}return check(matrix, expectValue, row + 1, col + 1);
}

嵌套数组

565. Array Nesting (Medium)在新窗口打开

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

题目描述: S[i] 表示一个集合,集合的第一个元素是 A[i],第二个元素是 A[A[i]],如此嵌套下去。求最大的 S[i]。

public int arrayNesting(int[] nums) {int max = 0;for (int i = 0; i < nums.length; i++) {int cnt = 0;for (int j = i; nums[j] != -1; ) {cnt++;int t = nums[j];nums[j] = -1; // 标记该位置已经被访问j = t;}max = Math.max(max, cnt);}return max;
}

分隔数组

769. Max Chunks To Make Sorted (Medium)在新窗口打开

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

题目描述: 分隔数组,使得对每部分排序后数组就为有序。

public int maxChunksToSorted(int[] arr) {if (arr == null) return 0;int ret = 0;int right = arr[0];for (int i = 0; i < arr.length; i++) {right = Math.max(right, arr[i]);if (right == i) ret++;}return ret;
}

相关文章:

【线性表 - 数组和矩阵】

数组是一种连续存储线性结构&#xff0c;元素类型相同&#xff0c;大小相等&#xff0c;数组是多维的&#xff0c;通过使用整型索引值来访问他们的元素&#xff0c;数组尺寸不能改变。 知识点数组与矩阵相关题目 # 知识点 数组的优点: 存取速度快 数组的缺点: 事先必须知道…...

Springboot 开发 -- 跨域问题技术详解

一、跨域的概念 跨域访问问题指的是在客户端浏览器中&#xff0c;由于安全策略的限制&#xff0c;不允许从一个源&#xff08;域名、协议、端口&#xff09;直接访问另一个源的资源。当浏览器发起一个跨域请求时&#xff0c;会被浏览器拦截&#xff0c;并阻止数据的传输。 这…...

【Qt】之【项目】整理可参考学习的git项目链接(持续更新)

Tcp 通信相关 IM即时通讯设计 高并发聊天服务&#xff1a;服务器 qt客户端&#xff08;附源码&#xff09; - DeRoy - 博客园 未使用protobuf通讯协议格式 github&#xff1a;GitHub - ADeRoy/chat_room: IM即时通讯设计 高并发聊天服务&#xff1a;服务器 qt客户端 QT编…...

2024年5月个人工作生活总结

本文为 2024年5月工作生活总结。 研发编码 golang 多个defer函数执行顺序 golang 函数中如有多个defer&#xff0c;倒序执行。示例代码&#xff1a; func foo() {defer func() {fmt.Println("111")}()defer func() {fmt.Println("2222")}()defer func()…...

Kafka Java API

1、增加依赖 <dependency><groupId>org.apache.kafka</groupId><artifactId>kafka-clients</artifactId><version>1.0.0</version> </dependency>2、三个案例 案例1&#xff1a;生产数据 import org.apache.kafka.clients.p…...

pushd: not found

解决方法&#xff1a; pushd 比 cd 命令更高效的切换命令&#xff0c;非默认&#xff0c;可在脚本开头添加&#xff1a; #! /bin/bash ubuntu 编译时出现/bin/sh: 1: pushd: not found的问题-CSDN博客...

【第十三节】C++控制台版本坦克大战小游戏

目录 一、游戏简介 1.1 游戏概述 1.2 知识点应用 1.3 实现功能 1.4 开发环境 二、项目设计 2.1 类的设计 2.2 各类功能 三、程序运行截图 3.1 游戏主菜单 3.2 游戏进行中 3.3 双人作战 3.4 编辑地图 一、游戏简介 1.1 游戏概述 本项目是一款基于C语言开发的控制台…...

酷得单片机方案 2.4G儿童遥控漂移车

电子方案开发定制&#xff0c;我们是专业的 东莞酷得智能单片机方案之2.4G遥控玩具童车具有以下比较有特色的特点&#xff1a; 1、内置充电电池&#xff1a;这款小车配备了可充电的电池&#xff0c;无需频繁更换电池&#xff0c;既环保又方便。充电方式可能为USB充电或者专用…...

【为什么 Google Chrome 打开网页有时极慢?尤其是国内网站,如知网等】

要通过知网搜一点资料&#xff0c;发现怎么都打不开。而且B站&#xff0c;知乎这些速度也变慢了&#xff01;已经检查过确定不是网络的问题。 清空了记录&#xff0c;清空了已接受Cookie&#xff0c;清空了缓存内容……没用&#xff01;&#xff01;&#xff01; 不断搜索&am…...

FastAPI - 数据库操作5

先安装mysql驱动程序 pipenv install pymysql安装数据库ORM库SQLAlchemy pipenv install SQLAlchemy修改文件main.py文件内容 设置数据库连接 # -*- coding:utf-8 –*- from fastapi import FastAPIfrom sqlalchemy import create_engineHOST 192.168.123.228 PORT 3306 …...

HTML静态网页成品作业(HTML+CSS)—— 冶金工程专业展望与介绍介绍网页(2个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有2个页面。 二、作品演示 三、代…...

Flutter基础 -- Dart 语言 -- 注释函数表达式

目录 1. 注释 1.1 单行注释 1.2 多行注释 1.3 文档注释 2. 函数 2.1 定义 2.2 可选参数 2.3 可选参数 默认值 2.4 命名参数 默认值 2.5 函数内定义 2.6 Funcation 返回函数对象 2.7 匿名函数 2.8 作用域 3. 操作符 3.1 操作符表 3.2 算术操作符 3.3 相等相关的…...

“仿RabbitMQ实现消息队列”---整体架构与模块说明

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C从入门到精通》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、概念性框架理解 我们主要实现的内容&#xff1a; 1.Broker服务器&#xff1a;消息队列服务器&#xff08;服务端&…...

springboot如何快速接入minio对象存储

1.在项目中添加 Minio 的依赖&#xff0c;在使用 Minio 之前&#xff0c;需要在项目中添加 Minio 的依赖。可以在 Maven 的 pom.xml 文件中添加以下依赖&#xff1a; <dependency><groupId>io.minio</groupId><artifactId>minio</artifactId>&l…...

第六届“智能设计+运维”国产工业软件研讨会暨2024年天洑软件用户大会圆满召开

2024年5月23-24日&#xff0c;第六届“智能设计运维”国产工业软件研讨会暨2024年天洑软件用户大会在南京举办。来自国产工业软件研发企业、制造业企业、高校、科研院所的业内大咖&#xff0c;能源动力、船舶海事、车辆运载、航空航天、新能源汽车、动力电池、消费电子、石油石…...

05.k8s弹性伸缩

5.k8s弹性伸缩 k8s弹性伸缩,需要附加插件heapster监控 弹性伸缩&#xff1a;随着业务访问量的大小&#xff0c;k8s系统中的pod比较弹性&#xff0c;会自动增加或者减少pod数量&#xff1b; 5.1 安装heapster监控 1:上传并导入镜像,打标签 ls *.tar.gz for n in ls *.tar.gz…...

【数据结构】详解二叉树

文章目录 1.树的结构及概念1.1树的概念1.2树的相关结构概念1.3树的表示1.4树在实际中的应用 2.二叉树的结构及概念2.1二叉树的概念2.2特殊的二叉树2.2.1满二叉树2.2.2完全二叉树 2.3 二叉树的性质2.4二叉树的存储结构2.4.1顺序结构2.4.2链表结构 1.树的结构及概念 1.1树的概念…...

MapDB:轻量级、高性能的Java嵌入式数据库引擎

MapDB&#xff1a;轻量级、高性能的Java嵌入式数据库引擎 在今天的软件开发中&#xff0c;嵌入式数据库因其轻便、高效和易于集成而备受欢迎。对于Java开发者来说&#xff0c;MapDB无疑是一个值得关注的选项。MapDB是一个纯Java编写的嵌入式数据库引擎&#xff0c;它提供了高性…...

Rye: 一个革新的Python包管理工具

文章目录 Rye: 一个革新的Python包管理工具Rye的诞生背景Rye的核心特性Rye的安装与使用Rye的优势与挑战Rye的未来展望结语 Rye: 一个革新的Python包管理工具 在Python生态系统中&#xff0c;包管理一直是一个复杂且令人头疼的问题。随着Python社区的不断发展&#xff0c;出现了…...

如何在C#代码中判断当前C#的版本和dotnet版本

代码如下&#xff1a; using System.Reflection; using System.Runtime.InteropServices;var csharpVersion typeof(string).Assembly.GetCustomAttributes(typeof(AssemblyFileVersionAttribute), false).OfType<AssemblyFileVersionAttribute>().FirstOrDefault()?.…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...

设计模式-3 行为型模式

一、观察者模式 1、定义 定义对象之间的一对多的依赖关系&#xff0c;这样当一个对象改变状态时&#xff0c;它的所有依赖项都会自动得到通知和更新。 描述复杂的流程控制 描述多个类或者对象之间怎样互相协作共同完成单个对象都无法单独度完成的任务 它涉及算法与对象间职责…...