Tag:算法

All the articles with the tag "算法".

• 如何判断一个单向链表是否是循环链表？

  Posted on:2024年9月3日 |  at 01:42

  判断一个单向链表是否是循环链表，常用的两种方法是哈希表法和快慢指针法（也称为Floyd 判圈算法）。这两种方法都能有效地检测链表是否有环，但它们的时间复杂度和空间复杂度不同。 1. 哈希表法 原理：使用一个哈希表来记录链表中每个节点的引用。如果在遍历过程中遇到一个已经在哈希表中的节点，则说明链表有环。 步骤： 创建一个空的哈希表。 遍历链表的每个节点： 如果当前节点已经存在于哈希表中，则链表有环。

• 深度遍历与广度遍历有什么区别？

  Posted on:2024年8月22日 |  at 11:02

  深度遍历（Depth-First Search, DFS）和广度遍历（Breadth-First Search, BFS）是图和树结构中常用的遍历方法。它们在访问节点的顺序和策略上有明显的不同。以下是它们的主要区别： 1. 深度遍历（DFS） 策略：优先深入到每个分支的尽头，然后回溯到上一个节点，继续探索其他未访问的分支。 数据结构：通常使用栈（可以是显式栈或递归调用的系统栈）来实现。 特点： 遍

• base64 的编码原理是什么？

  Posted on:2024年8月15日 |  at 23:43

  Base64 是一种编码方法，用于将二进制数据（如图像、音频、文件等）编码为 ASCII 字符串。这种编码方式将数据转换为一组可打印字符，通常用于在需要文本数据的环境中传输二进制数据，例如在电子邮件、JSON 数据、XML 数据等场景中。Base64 编码原理如下： 1. 编码过程 1.1 数据分组 Base64 编码将输入数据按每 3 个字节（24 位）一组进行分组。 每个 3 字节的数据块由

• 移动零

  Posted on:2024年8月15日 |  at 13:59

  给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。 解法1： function zeroMove(array) { let len = array.length; let j = 0; for (let i =

• 介绍下深度优先遍历和广度优先遍历，如何实现？

  Posted on:2024年8月14日 |  at 23:40

  深度优先遍历（DFS）和广度优先遍历（BFS）是两种常见的图或树的遍历算法。它们用于遍历和搜索图或树的数据结构。下面是对这两种遍历算法的详细介绍和实现方法。 深度优先遍历（DFS） 描述： 深度优先遍历 是一种优先深入到树或图的深层节点的遍历策略。它尽可能深入到每一个分支的末端，然后回溯到上一层继续遍历。 实现方式： 递归实现： 使用递归函数遍历每个节点。 栈实现： 使用栈来模拟递归过程，手动维护

• 常见数组排序算法有哪些？

  Posted on:2024年8月14日 |  at 12:12

  如图所示： 快速排序： 先从数列中取出一个数作为“基准”。 分区过程：将比这个“基准”大的数全放到“基准”的右边，小于或等于“基准”的数全放到“基准”的左边。 再对左右区间重复第二步，直到各区间只有一个数。 var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor

• 合并K个升序链表

  Posted on:2024年8月10日 |  at 21:17

  给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2： 输入：

• 请手写“快速排序”

  Posted on:2024年7月22日 |  at 15:42

  算法简介 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 算法描述和实现 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下： 从数列中挑出一个元素，称为 “基准”（pivot）； 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素

• 请手写“归并排序”

  Posted on:2024年7月22日 |  at 15:42

  算法简介 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 算法描述 具体算法描述如下： 把长度为n的输入序列分成两个长度为n/2的子序列； 对这两个子序列分

• 请手写“希尔排序”

  Posted on:2024年7月22日 |  at 15:42

  算法简介 希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。 算法描述 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述： 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 按增量序列个数k，对序列进行k 趟排序； 每趟排序，根据对

• 请手写“插入排序”

  Posted on:2024年7月22日 |  at 15:42

  算法简介 插入排序（Insertion-Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 算法描述 一般来说，插入排序都采用in-place在数组

• 请手写“选择排序”

  Posted on:2024年7月22日 |  at 15:42

  算法简介 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 算法步骤 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序

• 请手写“冒泡排序”

  Posted on:2024年7月22日 |  at 15:42

  算法描述 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 算法步骤 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完

• 最大的钻石

  Posted on:2024年7月22日 |  at 15:42

  1 楼到 n 楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从 1 楼到 n 楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到「最大」的一颗？ 题中包含一个隐藏条件：随机放置。所有的分析都是基于随机放置给出的。换句话说，如果放置钻石是人为干预大小，那么本题的所以分析则全部不成立。 其实这个问题的原型叫做秘书问题，该类问题全部属于最佳停止问题。 这类问题都有着统一的解法： 所以

• 请手写“堆排序”

  Posted on:2024年7月22日 |  at 15:42

  算法简介 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 算法描述 具体算法描述如下： 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序

• 什么是时间复杂度？

  Posted on:2024年7月22日 |  at 11:42

  时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。 随着n的不断增大，时间复杂度不断增大，算法花费时间越多。 常见的时间复杂度 常数阶O(1) 对数阶O(log2 n) 线性阶O(n) 线性对数阶O(n log2 n) 平方阶O(n^2) 立方阶O(n^3) k次方阶O(n^K) 指数阶O(2^n) 计算方法 选取相对增长最高的项 最高项系数是都化为1 若是常数的话用O(1)

• 怎么实现洗牌算法？

  Posted on:2024年7月22日 |  at 11:40

  洗牌算法是将原来的数组进行打散，使原数组的某个数在打散后的数组中的每个位置上等概率的出现，即为乱序算法。 请使用 js 实现一个洗牌算法。 洗牌算法(shuffle)的js实现 Fisher-Yates 先看最经典的 Fisher-Yates 的洗牌算法 这里有一个该算法的可视化实现 其算法思想就是 从原始数组中随机抽取一个新的元素到新数组中 从还没处理的数组（假如还剩n个）中，产生一个[0, n

• 去除字符串中出现次数最少的字符，不改变原字符串的顺序。

  Posted on:2024年7月22日 |  at 11:39

  实现删除字符串中出现次数最少的字符，若出现次数最少的字符有多个，则把出现次数最少的字符都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。 “ababac” —— “ababa” “aaabbbcceeff” —— “aaabbb” 可以通过以下步骤使用 JavaScript 去除字符串中出现次数最少的字符，同时不改变原字符串的顺序： 定义一个对象来存储每个字符出现的次数。 遍历字

• 实现一个函数，判断输入是不是回文字符串。

  Posted on:2021年7月7日 |  at 00:12

  “回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。 解法一 function isPlalindrome(input) { if (typeof input !== 'string') return false; return input.split('').reverse().join('') === input; } 解法二 function isPl