前端面试拼图-数据结构与算法

摘要:总结一些前端算法题,持续更新!

一、数据结构与算法

时间复杂度-程序执行时需要的计算量(CPU)

空间复杂度-程序执行时需要的内存空间

前端开发:重时间,轻空间

1.把一个数组旋转k步

array = [1, 2, 3, 4, 5, 6, 7] 旋转数组k=3, 结果[5, 6, 7, 1, 2, 3, 4]

思路1:把末尾的元素挨个pop,然后unshift到数组前面;

思路2:把数组拆分,最后concat拼接到一起

/**
* 旋转数组k步使用pop和unshift
*/
function rotate1(arr: number[], k: number): number[] {
  const length = arr.length
  if (!k || length === 0) return
  const step = Math.abs( k%length)   // abs 取绝对值,k不是数值是返回NaN
  // 时间复杂度o(n^2), 空间复杂度o(1)
  for (let i = 0; i<step; i++) {    // 任何值与NaN做计算返回false
    const n = arr.pop()
    if (n != null  ) {
      arr.unshift(n)  //数组是一个有序结构,unshift操作会非常慢!!!O(n);splice和shift也很慢
    }
  }
  return arr
}
/**
* 旋转数组k步使用concat
*/
function rotate2(arr: number[], k: number): number[] {
  const length = arr.length
  if (!k || length === 0) return
  const step = Math.abs( k%length)   // abs 取绝对值
  const part1 = arr.slice(-step)  // O(1)
  const part2 = arr.slice(0,length-step)
  // 时间复杂度o(1), 空间复杂度O(n)
  return part1.concat(part2)
}

常见内置API中的复杂度:

  • unshift: unshift 方法将给定的值插入到类数组对象的开头,并返回新的数组长度。时间复杂度为 O(n),其中 n 是数组的长度,因为在插入时需要将原有的元素逐一往后移动一位;空间复杂度为 O(1)。
  • splice: splice 方法用于从数组中添加或删除元素,并返回被删除的元素组成的新数组。splice 的时间复杂度为 O(n),其中 n 是数组的长度,因为在删除或插入元素后,需要移动数组中的其他元素以保持连续性;空间复杂度为 O(n),因为需要创建一个新的数组。
  • shift: shift 方法用于从数组的开头删除一个元素,并返回被删除的元素。shift 的时间复杂度为 O(n),其中 n 是数组的长度,因为在删除元素后,需要将数组中的其他元素往前移动一位以保持连续性;空间复杂度为 O(1),因为不需要额外的空间来存储。
  • concat: concat 方法用于将两个或多个数组合并成一个新数组。时间复杂度为 O(1),数组末尾操作;空间复杂度为 O(n+m),m、n是原数组长度,因为新的数组需要存储。
  • slice: slice 方法用于从数组中提取出指定范围的元素,并返回一个新数组(不改变原数组)。时间复杂度为 O(1);空间复杂度为 O(n),因为需要创建一个新的数组来存储提取的元素。

2.判断字符串是否为括号匹配

一个字符串s可能包括{}()[]三种括号,判断s是否是括号匹配

考察的数据结构是栈,先进后出;ApI: push pop length

栈 VS数组区别

栈:逻辑结构;理论模型,不管如何实现,不受任何语言限制

数组:物理结构;真实功能实现,受限于编程语言

/**
* 判断是否括号匹配
*/
function matchBracket(str: string): boolean {
  const length = str.length
  if(length === 0) return true
  
  const stack = []
  const leftSymbols = '{[('
  const rightSymbols = '}])'
  
  for (let i = 0; i <length; i++) {
    const s = str[i]
    if (leftSymbols.includes(s)) {
      stack.push(s)  // 左括号,压栈
    } else if (rightSymbols.includes(s)) {
      // 左括号,判断栈顶(是否出栈)
      const top = stack[stack.length-1]
      if (isMatch(top, s)) {
        stack.pop
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}
/**
* 判断左右括号是否匹配
*/
functionn isMatch(left: string, right: string): boolean {
  if (left === '{' && right === '}') return true
  if (left === '[' && right === ']') return true
  if (left === '(' && right === ')') return true
  return false
}

时间复杂度O(n); 空间复杂度O(n)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/368014.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

UnityShader(十四)纹理

目录 前言&#xff1a; 单张纹理实现效果&#xff1a; 效果&#xff1a; 前言&#xff1a; 纹理最初的目的是用一张图片来控制模型的外观。使用纹理映射技术我们可以把一张图“贴”在模型表面&#xff0c;逐纹素&#xff08;文素的名字是为了和像素进行区分&#xff09;控制…

开源软件:引领技术创新、商业模式与安全的融合

序 在信息技术日新月异的今天&#xff0c;开源软件以其独特的魅力和影响力&#xff0c;正逐渐成为软件产业的新常态。开源软件的低成本、高度可协作性和透明度等特点&#xff0c;不仅吸引了无数企业和个人用户的青睐&#xff0c;更为软件行业带来了前所未有的繁荣景象。 一、…

代码随想录算法训练营DAY11 | 栈与队列 (2)

一、LeetCode 20 有效的括号 题目链接&#xff1a;20.有效的括号https://leetcode.cn/problems/valid-parentheses/ 思路&#xff1a;遇到左括号直接进栈&#xff1b;遇到右括号判断站顶是否有匹配的括号&#xff0c;没有就返回flase&#xff0c;有就将栈顶元素出栈&#xff1…

利用OpenCV实现物流与生产线自动化的革命性突破

背景介绍&#xff1a; 在当今高度自动化的时代&#xff0c;物流和生产线上的每一个环节都关乎企业的核心竞争力。传统的生产方式往往依赖于人工检测和操作&#xff0c;这不仅效率低下&#xff0c;而且容易出错。为了解决这一问题&#xff0c;越来越多的企业开始寻求利用计算机视…

pintia6-2符号函数 6-1两点距离

pintia的函数题&#xff0c;只需要把函数写上去就可以了&#xff0c;6-2函数题比较简单&#xff0c;三个if就可以解决: 6-1则套用数学公式即可&#xff0c;注意把函数名复制粘贴过去&#xff0c;以免抄错

Blender教程(基础)-切分工具-11

再菜单栏左侧、鼠标左键长按切割工具弹出选项&#xff0c;选择切分工具即可找到切分工具。 一、切割使用 A键全选需要切分的物体&#xff0c;再选择切分后再操作物体上单机长按鼠标左键划分切分范围 选择好切分位置后点击确定如下图所示&#xff1a;Enter键确认切分 二、…

CSS 外边距合并、塌陷和BFC

外边距合并 CSS中的外边距合并指的是当两个相邻元素都设置了上下外边距时&#xff0c;它们之间会发生重叠。这种现象被称为"margin collapsing"&#xff08;外边距合并&#xff09;或者"margin collapse"&#xff08;外边距塌陷&#xff09;。 可以看出上…

2024年第四届能源与环境工程国际会议(CoEEE 2024) | Ei Scopus检索

会议简介 Brief Introduction 2024年第四届能源与环境工程国际会议(CoEEE 2024) 会议时间&#xff1a;2024年5月22日-24日 召开地点&#xff1a;意大利米兰 大会官网&#xff1a;www.coeee.org CoEEE 2024将围绕“能源与环境工程”的最新研究领域而展开&#xff0c;为研究人员、…

【Springcloud篇】学习笔记十(十七章):Sentinel实现熔断与限流——Hystrix升级

第十七章_Sentinel实现熔断与限流 1.Sentinel介绍 1.1是什么 随着微服务的流行&#xff0c;服务和服务之间的稳定性变得越来越重要。 Sentinel 以流量为切入点&#xff0c;从流量控制、熔断降级、系统负载保护等多个维度保护服务的稳定性。 用来代替Hystrix Sentinel 具有…

Web路由列表

什么是Web路由列表 在Web开发中&#xff0c;路由列表通常用于将请求的URL映射到相应的处理函数。尽管路由列表可以用不同的数据结构来实现&#xff0c;但在很多情况下是一个字典&#xff08;在Python中&#xff09;或其他类似的键值对结构。 路由列表&#xff08;Django&#…

远程手机搭建Termux环境,并通过ssh连接Termux

背景 Termux只能通过鼠标点击&#xff0c;无法使用电脑键盘&#xff0c;输入速度很慢&#xff0c;你想通过ssh 连接Termux&#xff0c;获得友好体验搞了个云手机&#xff0c;想像普通手机那样充当服务器想把自己的手机公开到局域网中供同事调试想把自己的模拟器公开到局域网中…

vue3-逻辑复用

什么是组合式函数 _无状态逻辑的函数_&#xff1a;它在接收一些输入后立刻返回所期望的输出。 比如 时间格式化的函数。 有状态逻辑的函数: 有状态逻辑负责管理会随时间而变化的状态。 比如 跟踪当前鼠标在页面中的位置。 在 Vue 应用的概念中&#xff0c;“组合式函数”(…

爬虫学习笔记-scrapy安装及第一个项目创建问题及解决措施

1.安装scrapy pycharm终端运行 pip install scrapy -i https://pypi.douban.com/simple 2.终端运行scrapy startproject scrapy_baidu,创建项目 问题1:lxml版本低导致无法找到 解决措施:更新或者重新安装lxml 3.项目创建成功 4.终端cd到项目的spiders文件夹下,cd scra…

JS 引导动画

前言 引导动画是程序在某一时刻播放的动画&#xff0c;通常用于向用户介绍程序的功能和特点。 实现效果 实现方式 引导动画的实现方式有很多种&#xff0c;这里我使用的是 CSS 的 clip-path 属性。 技术选型 这里我为什么要选择 clip-path 属性而不是 mask 属性呢&#xf…

SpringbootWeb案例

准备工作 需求说明 部门管理 部门管理功能开发包括&#xff1a;查询部门列表、删除部门、新增部门、修改部门   员工管理功能开发包括&#xff1a;查询员工列表(分页、条件)、删除员工、新增员工、修改员工 环境搭建 环境搭建步骤&#xff1a;1. 准备数据库表(dept、emp)…

ubuntu 安装 kvmQemu no active connection to install on

更新 apt sudo apt update检查虚拟化是否开启 0 不开&#xff0c;其余数字表示开启&#xff0c;开不开都可以&#xff0c;不开性能弱&#xff0c;只能跑 x86 系统 egrep -c (vmx|svm) /proc/cpuinfo安装 sudo apt install -y qemu-kvm virt-manager libvirt-daemon-system virt…

2.3作业

写一个shell脚本判断用户输入的是否是数字

我要成为嵌入式高手之2月3日Linux高编第一天!!

学习框架 一、IO编程 多任务编程&#xff08;进程、线程&#xff09; 网络编程 数据库编程 二、数据结构 学习笔记 Linux软件编程&#xff1a; 一. Linux 1、Linux: 操作系统的内核&#xff0c;真正的操作系统叫Ubuntu、Redhat、CentOS..... 内核&#xff08;纯c实现的代码…

pdmodel从动态模型转成静态onnx

1.下载项目 git clone https://github.com/jiangjiajun/PaddleUtils.git 2.新建两个新的文件夹 第一个文件夹放两个必要文件 第二个文件夹可以设置为空&#xff0c;用来存放转换后的模型 如图&#xff1a; 3.在终端运行 python paddle/paddle_infer_shape.py --model_dir …

DevOps落地笔记-10|环境管理:交付测试环境的迅猛方法

上一讲我主要介绍在开发过程中如何处理应用程序在不同环境的配置问题&#xff0c;通过有效管理应用程序的配置&#xff0c;最终实现一包到底。不同的环境不仅会带来应用程序本身的配置管理问题&#xff0c;环境本身的创建、管理、一致性等问题也需要解决。环境管理的问题也是我…