【前端面经】数组算法题解
目录
- 题目一:两数之和
- 题目二:最长无重复字符子串
- 题目三:合并两个有序数组
- 题目四:寻找数组中的峰值
题目一:两数之和
描述:给定一个整数数组 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…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
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> …...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
