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

【前端面经】数组算法题解

目录

      • 题目一:两数之和
      • 题目二:最长无重复字符子串
      • 题目三:合并两个有序数组
      • 题目四:寻找数组中的峰值

题目一:两数之和

描述:给定一个整数数组 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 [];
}

在这段代码中:

  1. map 是一个 JavaScript Map 对象,用于存储数组元素及其下标。
  2. 循环遍历数组 nums
  3. 对于每个元素 nums[i],计算 complement = target - nums[i],即当前元素需要搭配的另一个数。
  4. 检查 map 中是否存在这个 complement。如果存在,说明找到了两个数,它们的和等于 target
  5. map.get(complement) 返回 complement 在数组中的下标,i 是当前元素的下标。所以 return [map.get(complement), i]; 返回的是这两个数的下标。

示例解释
假设输入 nums = [2, 7, 11, 15]target = 9

  • 初始化一个空的 Map
  • 第一次循环:i = 0nums[0] = 2,计算 complement = 9 - 2 = 7map 中没有 7,所以将 2 存入 map,变为 map = {2: 0}
  • 第二次循环:i = 1nums[1] = 7,计算 complement = 9 - 7 = 2map 中有 2,其下标为 0。所以返回 [map.get(2), 1],即 [0, 1]

返回的 [0, 1] 表示数组 nums 中下标为 01 的两个元素(即 27),它们的和等于目标值 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;
}

题目三:合并两个有序数组

描述:给定两个有序整数数组 nums1nums2,将 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;
}

相关文章:

【前端面经】数组算法题解

目录 题目一&#xff1a;两数之和题目二&#xff1a;最长无重复字符子串题目三&#xff1a;合并两个有序数组题目四&#xff1a;寻找数组中的峰值 题目一&#xff1a;两数之和 描述&#xff1a;给定一个整数数组 nums 和一个目标值 target&#xff0c;请你在该数组中找出和为目…...

java架构设计-COLA

参考&#xff1a;https://github.com/alibaba/COLA 架构 要素&#xff1a;组成架构的重要元素 结构&#xff1a;要素直接的关系 意义&#xff1a;定义良好的结构&#xff0c;治理应用复杂度&#xff0c;降低系统熵值&#xff0c;改善混乱状态 创建COLA应用&#xff1a; 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 匿名内部类&#xff08;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.顺序表的底层结构是数组&#xff0c;在数组的基础上增加了增&#xff0c;删&#xff0c;查&#xff0c;改等方法。 2.顺序表的分类&#xff1a;静态顺序表和动态顺序表 静态顺序表的…...

【牛客面试必刷TOP101】Day33.BM70 兑换零钱(一)和BM71 最长上升子序列(一)

文章目录 前言一、BM70 兑换零钱(一)题目描述题目解析二、BM71 最长上升子序列(一)题目描述题目解析总结 前言 一、BM70 兑换零钱(一) 题目描述 描述&#xff1a; 给定数组arr&#xff0c;arr中所有的值都为正整数且不重复。每个值代表一种面值的货币&#xff0c;每种面值的货币…...

重构与优化-优化函数调用(5)

Rename Method Rename Method(“函数改名”),它的核心目标是通过修改方法的名称来更好地反映其功能,提高代码的可读性和维护性。这项重构不仅适用于Java,也同样适用于其他面向对象的编程语言。下面是进行Rename Method重构时的一些关键点和步骤: 关键目的 提升代码清晰…...

6月18日(周二)A股行总结:A股震荡收涨,车路云概念全日强势,10年、30年国债期货齐创新高

车路云概念股发力上涨&#xff0c;中海达、华铭智能等多股20CM涨停。半导体板块走强&#xff0c;中芯国际港股上涨近&#xff13;% 。白酒板块下跌&#xff0c;贵州茅台跌1.3% 。30年期及10年期国债期货主力合约均创上市以来新高。 周二&#xff0c;A股全日窄幅震荡 沪指收涨0…...

今年的618,似乎很平淡!

电商平台取消预售制度的第一个大促&#xff0c;快递业表现如何&#xff1f; 今年的618大促与往年有些不同&#xff0c;自4月起&#xff0c;天猫、京东、快手等主流平台相继官宣取消预售&#xff0c;打出“现货开卖”标签&#xff0c;这意味着消费者不用再被“烧脑”的优惠计算…...

嵌入式中间件_3.嵌入式中间件的一般架构

根据嵌入式中间件的不同类型和其应用对象的不同&#xff0c;其架构也有所不同&#xff0c;通常嵌入式中间件没有统一的架构&#xff0c;这里仅仅列举两种中间件架构。 1.消息中间件 1.1消息中间件原理架构 消息中间件是消息传输过程中保存消息的一种容器。它将消息从它的源中…...

Java基础 - 练习(二)打印菱形

Java基础练习 打印菱形&#xff0c;先上代码&#xff1a; // 方法一&#xff1a;基础&#xff0c;好理解 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 为什么一定会相遇&#xff0c;有没有可能会错过&#xff0c;或者出现永远追不上的情况&#xff0c;请证明6.2 slow一次走一步&#xff0c;fast如果一次走3步&#xff0c;走…...

JavaFX 分隔符

Separator类表示水平或垂直分隔线。它分割元素&#xff0c;不产生任何动作。 我们可以设计风格&#xff0c;应用视觉效果&#xff0c;并为分隔符设置动画。 默认情况下&#xff0c;分隔符是水平的。我们可以使用setOrientation方法改变它的方向。 Separator类扩展了Node类。…...

mysql安装配置教程(Linux+Windows)

mysql安装配置教程&#xff08;LinuxWindows&#xff09; 文章目录 mysql安装配置教程&#xff08;LinuxWindows&#xff09;摘要在 Linux 上安装和配置 MySQL1. 安装 MySQLUbuntu/DebianCentOS/RHEL 2. 配置 MySQL初始化 MySQL登录 MySQL创建数据库和用户配置 MySQL 文件 3. 测…...

MySQL数据库与基本操作(增删改查)

一、数据库的基本概念 数据库要学习的四个基本概念&#xff0c;主要是&#xff1a;数据、数据库系统、数据库、数据管理系统。数据&#xff08;Date&#xff09;是描述事物的记录&#xff0c;数据库系统&#xff08;DBS&#xff09;&#xff0c;数据库管理系统&#xff08;DBMS…...

【学习总结】SpringBoot中使用单例模式+ScheduledExecutorService实现异步多线程任务(若依源码学习)

最近在学习若依这个开源项目&#xff0c;发现他记录登录日志的时候使用了异步线程去记录日志&#xff0c;觉得这个方案也挺不错的&#xff0c;在此学习记录下来&#xff0c;以后在工作中也能提供一种思路&#xff0c;其他小伙伴如果有觉得不错的方案也可以在评论区里留言&#…...

shell脚本编程(概念、编程和语句)

一、shell脚本概述 1、shell脚本概念 Shell 脚本是利用 shell 的功能所写的一个程序。这个程序是使用纯文本文件&#xff0c;将一些 shell 的语法与命令&#xff08;含外部命令&#xff09;写在里面&#xff0c;搭配正则表达式、管道命令与数据流重定向等功能。 2、Shell 脚…...

设置角色运动的动画

(1) 打开Assets-UnityTechnologies-Animation-Animators&#xff0c;Create-Animation-Controller,命名为JohnLemon (2) 打开JohnLemon&#xff0c;出现下图 (3) 依次将Assets-UnityTechnologies-Animation-Animation中的JohnIdle和JohnWalk拖放到Base Layer窗口中 (4) 右击Idl…...

OKR:2024年目标和关键成果常见问题

什么是目标和关键结果&#xff08;OKR&#xff09;&#xff1f; 目标和关键结果&#xff08;#OKR#&#xff09;是一种由结果驱动的目标制定方法。在企业中&#xff0c;OKR经常被用来指导基于结果的成功。使用结果而不是任务作为驱动力&#xff0c;OKRs 鼓励通过度量指标对实现成…...

轻量级 ioc/aop 框架 loveqq 1.0 发布,完全替换掉若依底层 spring 及其 starter

loveqq-framework 轻量级 ioc/aop 框架&#xff0c;比 spring 更强大的条件注解推断&#xff0c;打包后支持 jar index 启动。 本次更新&#xff1a; 正式更名为&#xff1a;loveqq-famework 新增&#xff1a;loveqq-boot-starter-mybatis 新增&#xff1a;loveqq-boot-start…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...