【前端面经】数组算法题解
目录
- 题目一:两数之和
- 题目二:最长无重复字符子串
- 题目三:合并两个有序数组
- 题目四:寻找数组中的峰值
题目一:两数之和
描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能重复出现。
示例:
输入:nums = [2, 7, 11, 15], target = 9
输出:[0, 1]
解释:因为 nums[0] + nums[1] = 2 + 7 = 9
技巧和思路:
- 哈希表:使用哈希表来存储数组中的元素及其下标。遍历数组时,每次检查当前元素是否存在于哈希表中。如果存在,则找到了一组和为目标值的元素;如果不存在,则将当前元素和下标存入哈希表。
代码实现:
function twoSum(nums, target) {let map = new Map();for (let i = 0; i < nums.length; i++) {let complement = target - nums[i];if (map.has(complement)) {return [map.get(complement), i];}map.set(nums[i], i);}return [];
}
在这段代码中:
map是一个 JavaScriptMap对象,用于存储数组元素及其下标。- 循环遍历数组
nums。 - 对于每个元素
nums[i],计算complement = target - nums[i],即当前元素需要搭配的另一个数。 - 检查
map中是否存在这个complement。如果存在,说明找到了两个数,它们的和等于target。 map.get(complement)返回complement在数组中的下标,i是当前元素的下标。所以return [map.get(complement), i];返回的是这两个数的下标。
示例解释:
假设输入 nums = [2, 7, 11, 15],target = 9。
- 初始化一个空的
Map。 - 第一次循环:
i = 0,nums[0] = 2,计算complement = 9 - 2 = 7,map中没有7,所以将2存入map,变为map = {2: 0}。 - 第二次循环:
i = 1,nums[1] = 7,计算complement = 9 - 7 = 2,map中有2,其下标为0。所以返回[map.get(2), 1],即[0, 1]。
返回的 [0, 1] 表示数组 nums 中下标为 0 和 1 的两个元素(即 2 和 7),它们的和等于目标值 9。
题目二:最长无重复字符子串
描述:给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
示例:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
技巧和思路:
- 滑动窗口:使用两个指针来表示字符串的当前窗口。右指针不断向右移动,扩展窗口,如果遇到重复字符,则移动左指针,缩小窗口。用一个集合来记录窗口中的字符,保持窗口内字符不重复。
代码实现:
function lengthOfLongestSubstring(s) {let set = new Set();let left = 0, right = 0;let maxLength = 0;while (right < s.length) {if (!set.has(s[right])) {set.add(s[right]);maxLength = Math.max(maxLength, right - left + 1);right++;} else {set.delete(s[left]);left++;}}return maxLength;
}
题目三:合并两个有序数组
描述:给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。假定 nums1 有足够的空间来保存 nums2 中的元素。
示例:
输入:
nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3
输出:[1, 2, 2, 3, 5, 6]
技巧和思路:
- 双指针从后向前:因为
nums1有足够的空间,可以从两个数组的末尾开始比较,将较大的元素放到nums1的末尾。这种方法避免了在数组中频繁插入元素,优化了时间复杂度。
代码实现:
function merge(nums1, m, nums2, n) {let i = m - 1, j = n - 1, k = m + n - 1;while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) {nums1[k--] = nums1[i--];} else {nums1[k--] = nums2[j--];}}while (j >= 0) {nums1[k--] = nums2[j--];}
}
题目四:寻找数组中的峰值
描述:峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个峰值的索引即可。
示例:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素,你的函数应该返回其索引 2。
技巧和思路:
- 二分查找:利用二分查找的思想,通过比较中间元素与其左右相邻元素的大小,缩小查找范围。
代码实现:
function findPeakElement(nums) {let left = 0, right = nums.length - 1;while (left < right) {let mid = Math.floor((left + right) / 2);if (nums[mid] > nums[mid + 1]) {right = mid;} else {left = mid + 1;}}return left;
}
相关文章:
【前端面经】数组算法题解
目录 题目一:两数之和题目二:最长无重复字符子串题目三:合并两个有序数组题目四:寻找数组中的峰值 题目一:两数之和 描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目…...
java架构设计-COLA
参考:https://github.com/alibaba/COLA 架构 要素:组成架构的重要元素 结构:要素直接的关系 意义:定义良好的结构,治理应用复杂度,降低系统熵值,改善混乱状态 创建COLA应用: mvn …...
【进阶篇-Day3:JAVA接口新特性、代码块、内部类、Lambda表达式、组件等的介绍】
目录 1、接口新特性1.1 JDK8的新特性1.2 JDK9的新特性 2、代码块2.1 代码块的定义2.2 代码块的分类 3、内部类3.1 内部类的定义3.2 内部类成员访问3.3 学习内部类的原因3.4 内部类的分类3.4.1 成员内部类3.4.2 静态内部类3.4.3 局部内部类3.4.4 匿名内部类(1&#x…...
72-UDP协议工作原理及实战
#ifndef UDPCOMM_H #define UDPCOMM_H#include <QMainWindow> #include <QUdpSocket> // 用于发送和接收UDP数据报 #include <QtNetwork>QT_BEGIN_NAMESPACE namespace Ui { class udpComm; } QT_END_NAMESPACEclass udpComm : public QMainWindow {Q_OBJECT…...
数据结构——顺序表的实现
数据结构——顺序表的实现 一 关于顺序表的简单知识二 动态顺序表 一 关于顺序表的简单知识 1.顺序表的底层结构是数组,在数组的基础上增加了增,删,查,改等方法。 2.顺序表的分类:静态顺序表和动态顺序表 静态顺序表的…...
【牛客面试必刷TOP101】Day33.BM70 兑换零钱(一)和BM71 最长上升子序列(一)
文章目录 前言一、BM70 兑换零钱(一)题目描述题目解析二、BM71 最长上升子序列(一)题目描述题目解析总结 前言 一、BM70 兑换零钱(一) 题目描述 描述: 给定数组arr,arr中所有的值都为正整数且不重复。每个值代表一种面值的货币,每种面值的货币…...
重构与优化-优化函数调用(5)
Rename Method Rename Method(“函数改名”),它的核心目标是通过修改方法的名称来更好地反映其功能,提高代码的可读性和维护性。这项重构不仅适用于Java,也同样适用于其他面向对象的编程语言。下面是进行Rename Method重构时的一些关键点和步骤: 关键目的 提升代码清晰…...
6月18日(周二)A股行总结:A股震荡收涨,车路云概念全日强势,10年、30年国债期货齐创新高
车路云概念股发力上涨,中海达、华铭智能等多股20CM涨停。半导体板块走强,中芯国际港股上涨近3% 。白酒板块下跌,贵州茅台跌1.3% 。30年期及10年期国债期货主力合约均创上市以来新高。 周二,A股全日窄幅震荡 沪指收涨0…...
今年的618,似乎很平淡!
电商平台取消预售制度的第一个大促,快递业表现如何? 今年的618大促与往年有些不同,自4月起,天猫、京东、快手等主流平台相继官宣取消预售,打出“现货开卖”标签,这意味着消费者不用再被“烧脑”的优惠计算…...
嵌入式中间件_3.嵌入式中间件的一般架构
根据嵌入式中间件的不同类型和其应用对象的不同,其架构也有所不同,通常嵌入式中间件没有统一的架构,这里仅仅列举两种中间件架构。 1.消息中间件 1.1消息中间件原理架构 消息中间件是消息传输过程中保存消息的一种容器。它将消息从它的源中…...
Java基础 - 练习(二)打印菱形
Java基础练习 打印菱形,先上代码: // 方法一:基础,好理解 public static void diamond() {//控制行数for (int i 1; i < 4; i) {//空格的个数for (int k 1; k < 4 - i; k) {System.out.print(" ");}//控制星星…...
链表OJ--超详细解析
链表OJ 文章目录 链表OJ1. 反转链表2. 返回K值3. 链表的中间节点4. 回文链表5. 相交链表6. 带环链表6.1 为什么一定会相遇,有没有可能会错过,或者出现永远追不上的情况,请证明6.2 slow一次走一步,fast如果一次走3步,走…...
JavaFX 分隔符
Separator类表示水平或垂直分隔线。它分割元素,不产生任何动作。 我们可以设计风格,应用视觉效果,并为分隔符设置动画。 默认情况下,分隔符是水平的。我们可以使用setOrientation方法改变它的方向。 Separator类扩展了Node类。…...
mysql安装配置教程(Linux+Windows)
mysql安装配置教程(LinuxWindows) 文章目录 mysql安装配置教程(LinuxWindows)摘要在 Linux 上安装和配置 MySQL1. 安装 MySQLUbuntu/DebianCentOS/RHEL 2. 配置 MySQL初始化 MySQL登录 MySQL创建数据库和用户配置 MySQL 文件 3. 测…...
MySQL数据库与基本操作(增删改查)
一、数据库的基本概念 数据库要学习的四个基本概念,主要是:数据、数据库系统、数据库、数据管理系统。数据(Date)是描述事物的记录,数据库系统(DBS),数据库管理系统(DBMS…...
【学习总结】SpringBoot中使用单例模式+ScheduledExecutorService实现异步多线程任务(若依源码学习)
最近在学习若依这个开源项目,发现他记录登录日志的时候使用了异步线程去记录日志,觉得这个方案也挺不错的,在此学习记录下来,以后在工作中也能提供一种思路,其他小伙伴如果有觉得不错的方案也可以在评论区里留言&#…...
shell脚本编程(概念、编程和语句)
一、shell脚本概述 1、shell脚本概念 Shell 脚本是利用 shell 的功能所写的一个程序。这个程序是使用纯文本文件,将一些 shell 的语法与命令(含外部命令)写在里面,搭配正则表达式、管道命令与数据流重定向等功能。 2、Shell 脚…...
设置角色运动的动画
(1) 打开Assets-UnityTechnologies-Animation-Animators,Create-Animation-Controller,命名为JohnLemon (2) 打开JohnLemon,出现下图 (3) 依次将Assets-UnityTechnologies-Animation-Animation中的JohnIdle和JohnWalk拖放到Base Layer窗口中 (4) 右击Idl…...
OKR:2024年目标和关键成果常见问题
什么是目标和关键结果(OKR)? 目标和关键结果(#OKR#)是一种由结果驱动的目标制定方法。在企业中,OKR经常被用来指导基于结果的成功。使用结果而不是任务作为驱动力,OKRs 鼓励通过度量指标对实现成…...
轻量级 ioc/aop 框架 loveqq 1.0 发布,完全替换掉若依底层 spring 及其 starter
loveqq-framework 轻量级 ioc/aop 框架,比 spring 更强大的条件注解推断,打包后支持 jar index 启动。 本次更新: 正式更名为:loveqq-famework 新增:loveqq-boot-starter-mybatis 新增:loveqq-boot-start…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
