当前位置: 首页 > 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()?.…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

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

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...