web前端培训4个常见的算法问题分享

前端是一个不断变化的领域,总是有很多新的东西需要我们去学习,这给我们带来了不小的学习成本。

但从长远来看,许多事情也不会改变。一旦你掌握了这些底层技能,就刻意持续一生,这就是掌握了底层逻辑的好处。例如,算法。

当我们在前端谈论算法时,有两种观点:

有人认为算法在前端完全不重要,前端工程师没必要学算法。

也有人声称前端程序员也是程序员,需要深入学习算法,就像算法工程师一样。

我认为这两种观点都有些极端。

首先,算法在前端项目中也有很多应用。例如:

VirtualDOM是React和Vue中的核心机制之一。它需要使用哈希表数据结构和diff算法。

在解析模板语法和生成AST时,我们需要使用树形数据结构。

浏览器的浏览历史,以及各种撤消和重做功能,都需要用到栈。

所以算法对我们前端开发者来说肯定是有用的。

但同时我们也需要明白:前端更注重工程。

前端工程师最重要的是什么?在我看来,最重要的是工程能力。

所谓工程能力,本质上就是解决问题的能力。无论是编码技能还是架构思维,其本质都是服务于解决问题的最终目标。

完成项目是我们的终极目标,算法只是手段。

作为前端工程师,你不需要在算法领域投入太多精力。您无需获得ACM奖或完全理解厚书IntroductiontoAlgorithms。

所以在这里,我选择了前端面试中经常出现的算法题,然后经过总结整理,今天将其分享给你。

1、如何对数组进行排序?

排序算法是计算机科学中最古老、最基本的主题之一。大约有十几种常见的排序算法。

当然,我们不必完全掌握这些排序算法。如果我们需要先选择一个排序算法来学习,那么我认为应该是快速排序。

为什么?因为:

快速排序本身被广泛使用。

JavaScript中Array的sort方法是通过V8引擎中的快速排序实现的。

(准确的说,当数组元素少于10个时,V8使用插入排序算法,当数组元素多于10个时,使用快速排序算法。)

“快速排序”的思路很简单,整个排序过程只需要三个步骤:

选择数组中的一个元素作为“枢轴”。我们可以选择任何元素作为枢轴,但中间的元素更直观。

所有小于枢轴的元素都被移动到枢轴的左侧;所有大于或等于枢轴的元素都被移动到枢轴的右侧。

对于枢轴左右的两个子集,重复第一步和第二步,直到所有子集中只剩下一个元素。

例如,我们有一个需要排序的数组:

letarr=[86,24,64,48,15,30,90,49]

执行

首先,定义一个参数为数组的快速排序函数。

varquickSort=function(arr){

};

然后,检查数组中的元素个数,如果小于等于1,则返回。

varquickSort=function(arr){

if(arr.length=1){returnarr;}

};

接下来,选择枢轴,将其与原始数组分开,并定义两个空数组来存储两个子集。

varquickSort=function(arr){

  if(arr.length=1){returnarr;}

  varpivotIndex=Math.floor(arr.length/2);

  varpivot=arr.splice(pivotIndex,1)[0];

  varleft=[];

  varright=[];

};

然后,开始遍历数组,小于主元的元素放入左子集中,大于主元的元素放入右子集中。

varquickSort=function(arr){

  if(arr.length=1){returnarr;}

  varpivotIndex=Math.floor(arr.length/2);

  varpivot=arr.splice(pivotIndex,1)[0];

  varleft=[];

  varright=[];

  for(vari=0;iarr.length;i++){

     if(arr[i]pivot){

        left.push(arr[i]);

     }else{

        right.push(arr[i]);

     }

  }

};

最后,通过使用递归重复这个过程,得到排序后的数组。

varquickSort=function(arr){

  if(arr.length=1){returnarr;}

  varpivotIndex=Math.floor(arr.length/2);

  varpivot=arr.splice(pivotIndex,1)[0];

  varleft=[];

  varright=[];

  for(vari=0;iarr.length;i++){

     if(arr[i]pivot){

        left.push(arr[i]);

     }else{

        right.push(arr[i]);

     }

  }

  returnquickSort(left).concat([pivot],quickSort(right));

};

用法:

2、如何在排序后的数组中找到某个值?

对数组进行排序后,让我们使用排序后的数组。

假设我们有一个有序数组,我们想检查这个数组中是否存在某个值。那么我们应该怎么做呢?

我们可以遍历数组以确定该值是否存在于数组中,但是这种方法效率太低。

对于排序数组,我们有一个更有效的方法,就是二分查找。

执行二分搜索的基本步骤是:

以整个数组的中间元素作为搜索键开始。

如果搜索键的值等于项目,则返回搜索键的索引。

或者搜索键的值小于区间中间的项,则将区间缩小到下半部分。

否则,将其缩小到上半部分。

从第二点开始反复检查,直到找到值或区间为空。

例如,这是一个排序数组:

[15,24,30,48,49,64,86,90,,,]

如果我们要检查这个数组中是否存在48:

执行

functionbinarySearch(arr,x){

//leftindexofthecurrentinterval

letl=0;

//rightindexofthecurrentinterval

letr=arr.length-1;

//middleindexofthecurrentinterval

letmid;

while(r=l){

mid=l+Math.floor((r-l)/2);

//Iftheelementispresentatthemiddle

//itself

if(arr[mid]==x){

returnmid;

}

//Ifelementissmallerthanmid,then

//itcanonlybepresentinleftsubarray

if(arr[mid]x){

r=mid-1;

}

//Elsetheelementcanonlybepresent

//inrightsubarray

if(arr[mid]x){

l=mid+1;

}

}

//Wereachherewhenelementisnot

//presentinarray

return-1;

}

用法:

比较

二分搜索比正常的线性搜索更快。

但是,你只能在排序数组上使用二进制搜索!

3、如何反转单链表?

链表是表示一系列节点的数据结构,其中每个节点包含两条信息:节点的值和指向列表中下一个节点的指针/引用。链表的开头称为头,链表末尾的节点称为尾,指向空值;null。

与数组相比,链表的主要好处是更容易在列表中插入或删除节点。另一方面,不允许随机访问数据,因为与数组不同,链表没有索引。

链表也广泛用于前端项目。例如,React的Fiber使用链表。

我们可以这样创建一个链表:

functionNode(value){

this.value=value

this.next=null

}

lethead=newNode(1)

head.next=newNode(3)

head.next.next=newNode(9)

head.next.next.next=newNode(6)

head.next.next.next.next=newNode(2)

如果我们被要求反转一个链表,我们需要让尾部成为头部:

我们可以迭代或递归地反转链表,但我们将只


转载请注明:http://www.aierlanlan.com/rzgz/4664.html