标签: 算法

HZFEStudio | 2个月前 | 算法前端相关

算法:找到数组中重复的数字

题目描述 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例: js 输入:[2, 3, 1, 0, 2, 5, 3] 输出:2 或 3 解法一: 哈希表 [在线链接](https://codesandbox.io/s/hzfe-suan-fa-shu-zu-zhong-chong-fu-shu-zi-ha-xi-biao-forked-p8df3?file=/index.html) 从题目中分析,只需要找到任意一个重复的数字,那么可以利用哈希表,用数字的值作为 key 去存储,如果遇到已经存在的 key,则直接返回,这样就找到了重复的数字。 算法步骤 1. 声明哈希表用来保存遍历的值。 2. 开始遍历数组。 3. 获取当前值,判断值是否已经存在,若存在,则返回结果并结束循环;若不存在,则继续下一步。 4. 储存当前值进哈希表。 5. 处理数组下一位

 409 |  4 |  4 算法前端相关

HZFEStudio | 2个月前 | 算法前端相关

算法:二叉搜索树的第 k 个结点

题目描述 给定一棵二叉搜索树,请找出其中第 k 大的节点。 示例 1: js 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4 示例 2: js 输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 4 解题基本知识 二叉搜索树(Binary Search Tree)又名二叉查找树、二叉排序树。它是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。 解法一: 递归 [在线链接](https://codesandbox.io/s/erchasousuoshudedi-k-dadejiedian-vfpbh?file=/index.html) 利用二叉搜索树

 188 |  0 |  0 算法前端相关

HZFEStudio | 2个月前 | 算法前端相关

编码:将列表还原为树状结构

需求来源分析: 在需要存储树结构的情况下,一般由于使用的关系型数据库(如 MySQL),是以类似表格的扁平化方式存储数据。因此不会直接将树结构存储在数据库中,通常是通过邻接表、路径枚举、嵌套集或闭包表来存储。 其中,邻接表是最常用的方案之一,其存储模型如下: | id | pid | data | | -- | -- | -- | | 1 | 0 | a | | 2 | 1 | b | | 3 | 1 | c | 该模型代表了如下的树状结构: js { id: 1, pid: 0, data: 'a', children: [ {id: 2, pid: 1, data: 'b'}, {id: 3, pid: 1, data: 'c'}, ] } 大部分情况下,会交给应用程序来构造树结构。 典型题目 js const list = [ { pid: null, id: 1, data: "1" }, { pid: 1, id: 2, data: "2-1" }, { pid: 1, id: 3,

 229 |  0 |  0 算法前端相关

HZFEStudio | 2022-06-30 | 算法前端相关

算法:反转链表

题目描述 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: js 输入: 1 2 3 4 5 NULL 输出: 5 4 3 2 1 NULL 解法一:迭代(双指针) [在线链接](https://codesandbox.io/s/hzfe-suanfa-omcjw?file=/index.html) 本方法是对链表进行遍历,然后在访问各节点时修改 next 的指向,达到反转链表的目的。 1. 初始化 cur 和 pre 两个节点,分别指向 head 和 null。 2. 对链表进行循环,声明 temp 节点用来保存当前节点的下一个节点。 3. 修改当前节点 cur 的 next 指针指向为 pre 节点。 4. pre 节点修改为 cur 节点。 5. cur 节点修改为 t

 193 |  0 |  0 算法前端相关

HZFEStudio | 2022-06-29 | 算法

算法:平衡二叉树

题目描述 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树。 示例 1: js 给定二叉树 [3, 9, 20, null, null, 15, 7] 3 / \ 9 20 / \ 15 7 返回 true。 示例 2: js 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false。 限制:0 <= 树的结点个数 <= 10000 基本知识点 二叉树的每个节点最多有两个子节点,平衡二叉树中任意一个节点的左右子树高度相差不能大于 1,满二叉树和完全二叉树都是平衡二叉树,普通二叉树有可能是平衡二叉树。 题解 解法一 思路 若想判断二叉树是不是平衡二叉树,只需要判断左右子树的高度差是不是不超过 1 即可。同时,要满足一个树是平衡二叉树,它的子树也必须

 163 |  2 |  0 算法

动感超人, | 2022-06-27 | 算法

说说你对树的理解?相关的操作有哪些?

一、是什么 在计算机领域,树形数据结构是一类重要的非线性数据结构,可以表示数据之间一对多的关系。以树与二叉树最为常用,直观看来,树是以分支关系定义的层次结构 二叉树满足以下两个条件: 本身是有序树 树中包含的各个结点的不能超过 2,即只能是 0、1 或者 2 如下图,左侧的为二叉树,而右侧的因为头结点的子结点超过2,因此不属于二叉树: 同时,二叉树可以继续进行分类,分成了满二叉树和完成二叉树: 满二叉树:如果二叉树中除了叶子结点,每个结点的度都为 2 完成二叉树:如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布

 97 |  0 |  0 算法

动感超人, | 2022-06-27 | 算法

说说你对算法中时间复杂度,空间复杂度的理解?如何计算?

一、前言 算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别 衡量不同算法之间的优劣主要是通过 时间 和 空间 两个维度去考量: 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述 通常会遇到一种情况,时间和空间维度不能够兼顾,需要在两者之间取得一个平衡点是我们需要考虑的 一个算法通常存在最好、平均、最坏三种情况,我们一般关注的是最坏情况 最坏情况是算法运行时间的上界,对于某些算法来说,最坏情况出现的比较频繁,也意味着平均情况和最坏情况一样差 二、时间复杂度 时间复杂度是指执行这个算法所需要的计算工作量,其复杂度反映了程序执行时间「随输入规模增长而增长的量级」,在很大程度上能很好地反映出算法的优劣与否 一个算法花费的时间与算法中语句的「执行次数成正比」,执行次数越多,花费的时间就越多 算法的复杂度通常用大O符号表述,

 74 |  0 |  0 算法

动感超人, | 2022-06-27 | 算法

说说你对数据结构的理解?有哪些?区别?

一、是什么 数据结构是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合 前面讲到,一个程序 = 算法 + 数据结构,数据结构是实现算法的基础,选择合适的数据结构可以带来更高的运行或者存储效率 数据元素相互之间的关系称为结构,根据数据元素之间关系的不同特性,通常有如下四类基本的结构: 集合结构:该结构的数据元素间的关系是“属于同一个集合” 线性结构:该结构的数据元素之间存在着一对一的关系 树型结构:该结构的数据元素之间存在着一对多的关系 图形结构:该结构的数据元素之间存在着多对多的关系,也称网状结构 由于数据结构种类太多,逻辑结构可以再分成为: 线性结构:有序数据元素的集合,其中数据元素之间的关系是一对一的关系,除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的 非线性结构:各个数据元素不再保持在一个线性序列中,每个数据元素可能与零个或者多个其他数据元素发生关联 ![c6e05cc0899a44da8f93db5eba644e9d](https://static.developers.pub/c6e05c

 58 |  0 |  0 算法

动感超人, | 2022-06-27 | 算法

说说你对栈、队列的理解?应用场景?

一、栈 栈(stack)又名堆栈,它是一种运算受限的线性表,限定仅在表尾进行插入和删除操作的线性表 表尾这一端被称为栈顶,相反地另一端被称为栈底,向栈顶插入元素被称为进栈、入栈、压栈,从栈顶删除元素又称作出栈 所以其按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据,具有记忆作用 关于栈的简单实现,如下: js class Stack { constructor() { this.items = []; } / 添加一个(或几个)新元素到栈顶 @param { } element 新元素 / push(element) { this.items.push(element) } / 移除栈顶的元素,同时返回被移除的元素 / pop() { return this.items.pop() } / 返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它) /

 72 |  0 |  0 算法

动感超人, | 2022-06-27 | 算法

说说常见的排序算法有哪些?区别?

一、是什么 排序是程序开发中非常常见的操作,对一组任意的数据元素经过排序操作后,就可以把他们变成一组一定规则排序的有序序列 排序算法属于算法中的一种,而且是覆盖范围极小的一种,彻底掌握排序算法对程序开发是有很大的帮助的 对与排序算法的好坏衡量,主要是从时间复杂度、空间复杂度、稳定性 时间复杂度、空间复杂度前面已经讲过,这里主要看看稳定性的定义 稳定性指的是假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变 即在原序列中,r[i] = r[j],且 r[i] 在 r[j] 之前,而在排序后的序列中,r[i] 仍在 r[j] 之前,则称这种排序算法是稳定的;否则称为不稳定的 二、有哪些 常见的算法排序算法有: 冒泡排序 选择排序 插入排序 归并排序 快速排序 冒泡排序 一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来 思路如下: 比较相邻的元素,如果第一个比第二个大,就交换它们两个 对每一对相邻元素作同样的工作

 67 |  0 |  0 算法

动感超人, | 2022-06-27 | 算法

说说你对集合的理解?常见的操作有哪些?

一、是什么 集合(Set),指具有某种特定性质的事物的总体,里面的每一项内容称作元素 在数学中,我们经常会遇到集合的概念: 有限集合:例如一个班集所有的同学构成的集合 无限集合:例如全体自然数集合 在计算机中集合道理也基本一致,具有三大特性: 确定性:于一个给定的集合,集合中的元素是确定的。即一个元素,或者属于该集合,或者不属于该集合,两者必居其一 无序性:在一个集合中,不考虑元素之间的顺序,只要元素完全相同,就认为是同一个集合 互异性:集合中任意两个元素都是不同的 二、操作 在 ES6 中,集合本身是一个构建函数 Set ,用来生成 Set 数据结构,如下: js const s = new Set(); 关于集合常见的方法有: add():增 delete():删 has():改 clear():查 add() 添加某个值,返回 Set 结构本身 当添加实例中已经存在的元素, set 不会进行处理添加 js s.add(1).add(2).add(2); // 2只

 58 |  0 |  0 算法

动感超人, | 2022-06-27 | 算法

说说你对选择排序的理解?如何实现?应用场景?

一、是什么 选择排序(Selection sort)是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度,所以用到它的时候,数据规模越小越好 其基本思想是:首先在未排序的数列中找到最小(or最大)元素,然后将其存放到数列的起始位置 然后再从剩余未排序的元素中继续寻找最小(or最大)元素,然后放到已排序序列的末尾 以此类推,直到所有元素均排序完毕 举个例子,一个数组为 56、12、80、91、29,其排序过程如下: 第一次遍历时,从下标为 1 的位置即 56 开始,找出关键字值最小的记录 12,同下标为 0 的关键字 56 交换位置。此时数组为 12、56、80、91、20 第二次遍历时,从下标为 2 的位置即 56 开始,找出最小值 20,同下标为 2 的关键字 56 互换位置,此时数组为12、20、80、91、56 ![98

 64 |  0 |  0 算法

动感超人, | 2022-06-27 | 算法

说说你对快速排序的理解?如何实现?应用场景?

一、是什么 快速排序(Quick Sort)算法是在冒泡排序的基础上进行改进的一种算法,从名字上看就知道该排序算法的特点是快、效率高,是处理大数据最快的排序算法之一 实现的基本思想是:通过一次排序将整个无序表分成相互独立的两部分,其中一部分中的数据都比另一部分中包含的数据的值小 然后继续沿用此方法分别对两部分进行同样的操作,直到每一个小部分不可再分,所得到的整个序列就变成有序序列 例如,对无序表49,38,65,97,76,13,27,49进行快速排序,大致过程为: 首先从表中选取一个记录的关键字作为分割点(称为“枢轴”或者支点,一般选择第一个关键字),例如选取 49 将表格中大于 49 个放置于 49 的右侧,小于 49 的放置于 49 的左侧,假设完成后的无序表为:{27,38,13,49,65,97,76,49} 以 49 为支点,将整个无序表分割成了两个部分,分别为{27,38,13}和{65,97,76,49},继续采用此种方法分别对两个子表进行排序 前部分子表以 27 为支点,排序后的子表为{13,27,38},此部分已经有序;后部分子

 67 |  0 |  0 算法

动感超人, | 2022-06-27 | 算法

说说你对归并排序的理解?如何实现?应用场景?

一、是什么 归并排序(Merge Sort)是建立归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用 将已有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,再使子序列段间有序 例如对于含有 n 个记录的无序表,首先默认表中每个记录各为一个有序表(只不过表的长度都为 1) 然后进行两两合并,使 n 个有序表变为 n/2 个长度为 2 或者 1 的有序表(例如 4 个小有序表合并为 2 个大的有序表) 通过不断地进行两两合并,直到得到一个长度为 n 的有序表为止 例如对无序表{49,38,65,97,76,13,27}进行归并排序分成了分、合两部分: 如下图所示: 归并合过程中,每次得到的新的子表本身有序,所以最终得到有序表 上述分成两部分,则称为二路归并,如果分成三个部分则称为三路归并,以此类推 ...

 68 |  0 |  0 算法

动感超人, | 2022-06-27 | 算法

说说你对链表的理解?常见的操作有哪些?

一、是什么 链表(Linked List)是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的,由一系列结点(链表中每一个元素称为结点)组成 每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域 节点用代码表示,则如下: js class Node { constructor(val) { this.val = val; this.next = null; } } data 表示节点存放的数据 next 表示下一个节点指向的内存空间 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到 O(1) 的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时

 68 |  0 |  0 算法