手写代码面试题合集

持续更新，为了高效率访问，也算自己复习！！把遇到的手写题，抽空都撸了一遍。满满干货，不墨迹，直接上代码。总结道这篇博客里，下次面试前快速过一遍，临阵磨刀～

实现 sleep 函数

// 运行log函数后，希望得到结果：打印1，等待一秒钟，打印2，实现sleep函数
function log() {
  console.log(1);
  sleep(1000);
  console.log(2);
}
log();

// 解1：阻塞主线程
function sleep(time) {
  let t = Date.now();
  while (Date.now() - t <= time) {}
}
// 解2：async/await调用
function sleep(time) {
  return new Promise((res) => {
    setTimeOut(() => {
      resolve();
    }, time);
  });
}

柯里化(currying)

// 题目：实现add函数, 输出6
add(1, 2, 3);
add(1)(2)(3);
add(1, 2)(3);
add(1)(2, 3);

// 解1：不确定参数数量，一个方法
function add(...agrg1) {
  let t = function (...agrg2) {
    return add(
      Array.from(agrg1)
        .concat(Array.from(agrg2))
        .reduce((a, b) => {
          return a + b;
        })
    );
  };
  t.toString = () => {
    return Array.from(agrg1).reduce((a, b) => {
      return a + b;
    });
  };
  return t;
}

console.log(add(1, 2, 3)); // 6
console.log(add(1)(2)(3)); // 6
console.log(add(1, 2)(3)); // 6
console.log(add(1)(2, 3)); // 6
// 解2：确定参数数量，两个方法
function currying(fn, ...args) {
  if (args.length >= fn.length) {
    return fn(...args);
  } else {
    return (...args2) => currying(fn, ...args, ...args2);
  }
}
// add只可以接受三个参数
let add = function (a, b, c) {
  return a + b + c;
};
// 利用currying函数改造add函数，使add函数具备柯里化
const curry_add = currying(add);

console.log(curry_add(1, 2, 3)); // 6
console.log(curry_add(1)(2)(3)); // 6
console.log(curry_add(1, 2)(3)); // 6
console.log(curry_add(1)(2, 3)); // 6

约瑟夫环问题

// N个人围成一圈，第一个人从1开始报数，报M的将被淘汰，下一个人接着从1开始报。如此反复，最后剩下两个，求最后的胜利者。
function f(n) {
  if (n <= 2) {
    return n === 1 ? [1] : [1, 2];
  }
  let temp = [];
  for (let i = 1, len = n + 1; i < len; i++) {
    temp.push(i);
  }
  return fun_inner(temp);
  function fun_inner(temp, count) {
    if (temp.length == 2) {
      return temp;
    }
    count = count || 1;
    for (let i = 0, len = temp.wlength; i < len; i++) {
      count++;
      if (count === 3) {
        temp.splice(i, 1);
        count = 1;
      }
    }
    return fun_inner(temp, count);
  }
}
console.log(f(10)); // [4, 10]
console.log(f(11)); // [3, 9]
console.log(f(12)); // [6, 9]

字符串相加

let addStrings = function (a, b) {
  let res = [];
  let temp = 0;
  if (a.length > b.length) {
    let t = a.length - b.length;
    for (let i = 0; i < t; i++) {
      b = "0" + b;
    }
  } else {
    let t = b.length - a.length;
    for (let i = 0; i < t; i++) {
      a = "0" + a;
    }
  }
  for (let len = Math.max(a.length, b.length) - 1; len >= 0; len--) {
    let i = len;
    let t_a = Number(a.charAt(i) || 0);
    let t_b = Number(b.charAt(i) || 0);
    let count = String(t_a + t_b + temp);
    temp = 0;
    if (count.length > 1) {
      temp = Number(count.charAt(0));
      res.push(count.charAt(1));
    } else {
      res.push(count);
    }
  }
  if (temp !== 0) {
    res.push(temp);
  }
  return res.reverse().join("");
};

插入排序

let insertion = function (arr) {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    let cur = i;
    let j = i - 1;
    while (j >= 0) {
      if (arr[cur] < arr[j]) {
        [arr[cur], arr[j]] = [arr[j], arr[cur]];
        cur = j; // 交换后i值变了，那把交换后的i找回来就可以了
      }
      j--;
    }
  }
  return arr;
};

选择排序

let selection = function (arr) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    let idx = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[idx]) {
        idx = j;
      }
    }
    [arr[idx], arr[i]] = [arr[i], arr[idx]];
  }
  return arr;
};

快速排序

let quickSort = function (arr) {
  if (arr.length <= 1) {
    return arr;
  } // 递归边界条件
  let pointIdx = Math.floor(arr.length / 2); // 在数组中间位置取一个基准点
  let point = arr.splice(pointIdx, 1)[0]; // 通过基准点找到这个值
  let left = [];
  let right = [];
  for (let i = 0, len = arr.length; i < len; i++) {
    if (arr[i] < point) {
      // 循环数组，小于point的放在left中，大的放在right中
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  // 递归，让每一个left和right继续排序，直到left或right只有一项为止
  return quickSort(left).concat(point, quickSort(right));
};

call & apply & bind 实现

window.name = 2;
let obj = {
  name: 1,
};
function fn(a, b) {
  console.log(this.name, a, b);
  return 1;
}

// call
Function.prototype.myCall = function (context) {
  context = context || window; // 如果上下文是null或者undefined，那么默认为window
  context.fn = this; // 设置执行函数到obj上，利用谁调用，谁就是this的特性，来实现this转换
  // let arg = Array.from(arguments).slice(1) 截取参数也能这么写
  let arg = [...arguments].slice(1); // 截取除了第一个参数以后的参数
  let t = context.fn(...arg); // 传参执行
  delete context.fn; // 设置完成后删除
  return t; // 并返回
};

// apply
Function.prototype.myApply = function (context) {
  context = context || window;
  context.fn = this; // 设置执行函数到obj上，利用谁调用，谁就是this的特性，来实现this转换
  let arg = [...arguments][1]; // 参数是一个数组
  if (!arg) {
    // 如果没参数，那么就不传参执行
    return context.fn();
  }
  let t = context.fn(...arg);
  delete context.fn;
  return t;
};

// bind
Function.prototype.Mybind = function (ref, ...arg) {
  // 当这个函数被new调用，需要解决两个问题
  // 1: 不应该使用ref为this，根据情况判断，如果new调用那么this为实例。普通调用this为ref
  // 2: 因为bind返回是新函数，所有要bind新函数要继承_this的原型
  let _this = this;
  let fun = function (...arg2) {
    // 1的实现：this instanceof fun表达式为true说明被new调用，那么this就是新函数的this，也就是一个新的对象，否则就是第一个参数ref
    thisArg = this instanceof fun ? this : ref;
    return _this.apply(ref, [...arg, ...arg2]);
  };

  // 2的实现：如果有prototype，那么继承
  _this.prototype && (fun.prototype = Object.create(_this.prototype));
  return fun;
};

console.log(fn(1, 2));
console.log(fn.myCall(obj, 1, 2));
console.log(fn.myApply(obj, [1, 2]));
console.log(fn.Mybind(obj, [1, 2])());

二叉树反转

let reverseTree = function (root) {
  if (!root) return null;
  if (root.left || root.right) {
    let temp = root.left;
    root.left = root.right;
    root.right = temp;
    reverseTree(root.left);
    reverseTree(root.right);
  }
  return root;
};

链表反转

var reverseList = function (head) {
  let [prev, curr] = [null, head];
  while (curr) {
    let tmp = curr.next; // 1. 临时存储当前指针后续内容
    curr.next = prev; // 2. 反转链表
    prev = curr; // 3. 接收反转结果
    curr = tmp; // 4. 接回临时存储的后续内容
  }
  return prev;
};

二叉树遍历

以前序遍历举例

// 递归版
function preTraverse(root) {
  if (root) {
    console.log(root.value);
    preOrder(root.left);
    preOrder(root.right);
  }
}
// 非递归版
function preTraverse(root) {
  if (!root) {
    return false;
  }
  let stack = [];
  let p = root;
  while (stack.length || p) {
    if (p) {
      console.log(p.val);
      stack.push(p);
      p = p.left;
    } else {
      p = stack.pop();
      p = p.right;
    }
  }
}

promise 重试

 Promise.retry = function(fn, num = 3){
    return new Promise(function(resolve, reject){
       while(num>0){
           try{
                  const res = await fn
                  resolve(res)
                  num = 0
            } catch(e){
                  if(!num) reject(e)
            }
            num --
        }
    })
}

算法, 面试题 · 2021年4月30日 · 被浏览 - 次