趣味算法思想

blank

趣味算法思想

隨意的前言

好久都沒有寫文章啦,React系列的文章還差一篇,但是感覺講+寫已經很膩了,所以先放一放,換一下口味吧!

今天我們來看看算法在實際問題中的應用,還是很有意思的哇~~~

對撞指針

思想:對撞指針的意思就是有兩個指針,一個從開頭,一個從結尾,兩個指針分別++,--直到碰撞

這個思想可以解決什麼問題呢?

題目:leedcode 167

給定一個從小到大有序的數組,從數組裡找到兩個數字可以等於target,並返回索引。

即:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

分析:這道題可以直接用查找的方法,一層層循環去找。但是這樣做時間複雜度為O(n2),而且完全沒有利用到我們這個數組有序的特性。

更好的解法是:兩個指針,分別從兩邊去找,相加>target,右邊指針--前移,如果<target,左邊指針++前移,一直到這兩個指針碰撞,如果找到結果可以返回相應的索引。

代碼實現:

vartwoSum=function(nums,target){varleft=0;varright=nums.length-1;//對撞的循環條件:左邊指針小於右邊指針while(left<right){if(nums[left]+nums[right]===target){return[left,right]}elseif(nums[left]+nums[right]>target){right--;}else{left++;}}};

滑動窗口

思想:

有兩個指針構成一個區間,通過往同一個方向不停的移動,來找到滿足條件的區間。

滑動窗口關鍵的是想想初始時候,兩個指針在哪,在滑動的時候,兩個指針基於什麼條件移動,移動後的位置又在哪裡。

下面來分析一個題目來看看如何用這個思想。

題目:leedcode 209

給定一個整形數組和一個數字s,找到數組中最短的一個連續子數組,使得連續子數組的數組和sum >= s,返回這個最短的連續子數組的長度值。

即:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2

分析:這裡依舊可以採取暴力解法,找出所有的子數組,再分別相加求解。但是這裡介紹更好的解法。

這裡可以看到由於需要找連續的子數組,所以依舊可以設置兩個指針,往同一方向移動。

如果兩個指針中間的值加起來>sum的時候,記錄此時數組的長度,接著左指針移動,減小sum的值;

如果< sum的話,右指針移動擴大範圍。

最後返回最短的長度值。

代碼實現:

/*** @param {number} s* @param {number[]} nums* @return {number}*/varminSubArrayLen=function(s,nums){varleft=0;varright=-1;// right的起始位置很重要,這裡選擇-1 [left, right]這個區間剛開始是沒有值的vartmpSum=0;varminLength;//循環停止的條件是左指針小於長度while(left<nums.length-1){if(tmpSum<s){//這裡要注意邊界的處理,當右指針移動到最後一個元素的時候結束if(right>=nums.length-1){returnminLength||0;}right++;//這裡tmpSum的計算也很巧妙,直接用累加的方式,節省計算量tmpSum=tmpSum+nums[right]}else{vartmp=right-left+1;if(minLength){if(tmp<minLength){minLength=tmp;}}else{minLength=tmp;}//左邊指針移動減少sum的值tmpSum=tmpSum-nums[left];left++;}}if(!minLength){return0;}returnminLength;};

查找

這裡先介紹兩種數據結構Set Map ,不了解的同學先自行學習一下,其實很簡單,Set類型就是只有key的一種數據結構,而Map類型有key,value。

而在JS中,Object類型基本跟Map類型的一樣使用,但是還是有些不同的,也可以在這邊文章裡了解不同。

接下來通過具體的例子來看看如何使用它們。

題目:leedcode 1

這個問題跟開頭的問題一樣,給定一個數組numbers,從數組裡找到兩個數字可以等於target,並返回索引。

即:

Input: numbers = [2,7,11,15], target = 9 Output: [1,2]

分析:

除了暴力的解法,我們還可以用剛剛介紹的對撞指針的思路,先給它排序,在使用對撞指針,但是我們這裡由於要返回索引,所以還要記錄排序前的索引。其實這個思路也是有點麻煩的。

這裡在介紹巧妙查找表的思路:

我們可以先定義一個Object類型的數據結構obj,它的key為target - numbers[i](比如數組第一項為2),value為索引。然後每次都看看obj[numbers[i]] 是否存在,如果存在,那我們就找到了這樣的一組數據,返回當前索引以及obj[numbers[i]]。

代碼實現:

/*** @param {number[]} nums* @param {number} target* @return {number[]}*/vartwoSum=function(nums,target){varobj={};for(vari=0;i<nums.length;i++){constitem=nums[i];if(obj[item]>=0){return[obj[item],i]}else{obj[target-item]=i;}}};

面試中常考的數組去重的問題,也可以藉助Object的查找思路,可以自行練習。

總結

因為在公司有後台處理數據,所以總覺得算法跟前端沒有太大的關係,在看React源碼的時候,裡面使用了深度查找的思想。所以我覺得學好算法對我們還是很重要的。後面接著~

本文對你有幫助的話,點個贊鼓勵一下作者唄(੭ु≧▽≦)੭ु

What do you think?

Written by marketer

blank

IMWebConf 2018 前端大會,10 月14 日重磅來襲!

blank

React大會&& FEDAY 演講視頻來啦,持續更新中…