【面试题】算法
一、简单算法的实现
1.用两个堆栈实现队列
class Quene{
constructor(){
this.inputStack = [];
this.outputStack = [];
}
enquene(item){
return this.inputStack.push(item);
}
dequene(){
if(this.outputStack.length <= 0){
while(this.inputStack.length > 0){
var queneItem = this.inputStack.pop();
this.outputStack.push(queneItem);
}
}
return this.outputStack.pop();
}
}
//使用
var q = new Quene();
q.enquene(5);
q.enquene(4);
q.enquene(3);
console.log(q.inputStack + 'input1');
console.log(q.outputStack + 'output1');
q.dequene();
console.log(q.outputStack + 'output2');
2.深克隆(深复制)
function deepClone(obj,newObj = { }){
for(let key in obj){
if(typeof obj[key] === 'object'){
newObj[key] = Array.isArray(obj[key]) ? [ ] : { };
deepClone(obj[key],newObj[key]);
}else{
newObj[key] = obj[key];
}
}
return newObj;
}
3.函数节流(throttle)与函数去抖(debounce)
【什么是throttle】
如果将水龙头拧紧直到水是以水滴的形式流出，那你会发现每隔一段时间，就会有一滴水流出。
也就是会说预先设定一个执行周期，当调用动作的时刻大于等于执行周期则执行该动作，然后进入下一个新周期。
var throttle = function(delay,action){
vat last = 0;
return function(){
var curr = +new Date();
if(curr - last > delay){
action.apply(this,arguments);
last = curr;
}
}
}
【适用场景】
（1）计算鼠标移动距离/拖拽时的mousemove事件（连续拖拽时，不需要一直触发响应函数，每隔delay毫秒触发一次即可）
（2）射击游戏的 mousedown/keydown 事件（单位时间只能发射一颗子弹）
（3）搜索联想（keyup）(连续输入时，每隔delay毫秒向后端发送一次请求)
（4）监听滚动事件判断是否到页面底部自动加载更多：给 scroll 加了 debounce 后，只有用户停止滚动后，才会判断是否到了页面底部；如果是 throttle 的话，只要页面滚动就会间隔一段时间判断一次
【什么是debounce】
如果用手指一直按住一个弹簧，它将不会弹起直到你松手为止。
也就是说当调用动作n毫秒后，才会执行该动作，若在这n毫秒内又调用此动作则将重新计算执行时间。
var debounce = function(idle,action){
var timer;
return function(){
var ctx = this,
args = arguments;
clearTimeout(timer);
timer = setTimeout(function(){
action.apply(ctx,args);
},idle);
}
}
【适用场景】
（1）每次 resize/scroll 触发统计事件（连续resize/scroll视为一次触发，统计计数只加1）
（2）文本输入的验证（连续输入文字，停止输入后发送 AJAX 请求进行验证。输入期间不发送请求）
（3）监听滚动事件判断是否到页面底部自动加载更多。给 scroll 加了 debounce 后，只有用户停止滚动后，才会判断是否到了页面底部；如果是 throttle 的话，只要页面滚动就会间隔一段时间判断一次
【throttle和debounce适用场景区分】（个人理解）
在连续的动作停止后才需要触发的响应，使用debounce函数作为响应函数。
在连续的动作进行期间，就需要每隔一段时间触发一次的响应，使用throttle函数作为响应函数。
二、计算机科学中经典算法的JS实现
1.冒泡排序
var arr = [2,3,1,4,5];
function bubbleSort(arr){
for(var i = 0; i<arr.length-1; i++){
for(var j = 0; j<arr.length-i-1; j++){
if(arr[j] > arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
2.快速排序
function quickSort(arr,left,right){
var len = arr.length,
partitionIndex,
left = typeof left === 'number' ? left : 0,
right = typeof right === 'number' ? right : len -1;
if(left < right){
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
//分割坐标获取
function partition(arr,left,right){
var pivot = left,
index = pivot + 1;
for(var i = index; i<=right; i++){
if(arr[i] < arr[pivot]){
swap(arr,i,index);
index++;
}
}
swap(arr,pivot,index-1);
return index-1;
}
//交换
function swap(arr,i,j){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
三、js常见算法题
1.深克隆
// 判断是不是基本类型
function isEasyType(item) {
const type = Object.prototype.toString.call(item)
if ([
'[object Boolean]',
'[object Number]',
'[object String]',
'[object Undefined]',
'[object Null]'
].includes(type)){
return true
}
}
function deepClone(obj) {
const type = Object.prototype.toString.call(obj)
// 对象类型
if (type === '[object Object]') {
const copyObj = {}
Object.keys(obj).forEach(key => {
if(isEasyType(obj[key])) {
copyObj[key] = obj[key]
} else {
copyObj[key] = deepClone(obj[key])
}
})
return copyObj
} else if (type === '[object Array]') {
// 数组类型
const copyArr = []
obj.forEach(item => {
if (isEasyType(item)) {
copyArr.push(item)
} else {
copyArr.push(deepClone(item))
}
})
return copyArr
} else if (type === '[object Function]') {
// 函数类型
const copyFunc = Function('return '+ obj.toString())()
return copyFunc
} else if (type === '[object Date]') {
// 日期类型
const copyDate = new Date(obj.getTime());
return copyDate
} else if (type === '[object RegExp]') {
// 正则类型
const copyReg = new RegExp(obj);
return copyReg
}
}
#待续......
