前端面试之数据结构与算法

字符串类面试题

解析 URL Params 为对象

let url =
  "http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled";
parseParam(url);
/* 结果
{ user: 'anonymous',
  id: [ 123, 456 ], // 重复出现的 key 要组装成数组，能被转成数字的就转成数字类型
  city: '北京', // 中文需解码
  enabled: false, // 未指定值得 key 约定为 false
}
*/

// 实现方法
function parseParam(url) {
  const paramsStr = /.+\?(.+)$/.exec(url)[1]; // 将 ? 后面的字符串取出来
  const paramsArr = paramsStr.split("&"); // 将字符串以 & 分割后存到数组中
  let paramsObj = {};
  // 将 params 存到对象中
  paramsArr.forEach(param => {
    if (/=/.test(param)) {
      // 处理有 value 的参数
      let [key, val] = param.split("="); // 分割 key 和 value
      val = decodeURIComponent(val); // 解码
      val = /^\d+$/.test(val) ? parseFloat(val) : val; // 判断是否转为数字

      if (paramsObj.hasOwnProperty(key)) {
        // 如果对象有 key，则添加一个值
        paramsObj[key] = [].concat(paramsObj[key], val);
      } else {
        // 如果对象没有这个 key，创建 key 并设置值
        paramsObj[key] = val;
      }
    } else {
      // 处理没有 value 的参数
      paramsObj[param] = false;
    }
  });

  return result;
}

模版引擎的实现

let template = "我是{{name}}，年龄{{age}}，性别{{sex}}";
let data = {
  name: "姓名",
  age: 18
};
render(template, data); // 我是姓名，年龄18，性别undefined

// 自己的实现方法
function render(template, data) {
  const arr = template.match(/{{\w+}}/g);
  arr.forEach(item => {
    const key = /{{(\w+)}}/.exec(item)[1];
    template = template.replace(item, data[key]);
  });
  return template;
}

// 参数实现方法
function render(template, data) {
  const reg = /\{\{(\w+)\}\}/; // 模板字符串正则
  if (reg.test(template)) {
    // 判断模板里是否有模板字符串
    const name = reg.exec(template)[1]; // 查找当前模板里第一个模板字符串的字段
    template = template.replace(reg, data[name]); // 将第一个模板字符串渲染
    return render(template, data); // 递归的渲染并返回渲染后的结构
  }
  return template; // 如果模板没有模板字符串直接返回
}

转化为驼峰命名

var s1 = "get-element-by-id";

// 转化为 getElementById

function camel(s) {
  return s.replace(/-\w/g, x => x.slice(1).toUpperCase());
}

查找字符串中出现最多的字符和个数

例: abbcccddddd -> 字符最多的是 d，出现了 5 次

let str = "abcabcabcbbcccccc";
let num = 0;
let char = "";

// 使其按照一定的次序排列
str = str
  .split("")
  .sort()
  .join("");

// 定义正则
let reg = /(\w)\1+/g;

str.replace(reg, ($0, $1) => {
  if ($0.length > 0) {
    num = $0.length;
    char = $1;
  }
});
console.log(`字符最多的是${char}，出现了${num}次`);

字符串查找

请使用最基本的遍历来实现判断字符串 a 是否被包含在字符串 b 中，并返回第一次出现的位置（找不到返回 -1）。

a = "34";
b = "1234567"; // 返回 2
a = "35";
b = "1234567"; // 返回 -1
a = "355";
b = "12354355"; // 返回 5
isContain(a, b);

function isContain(a, b) {
  for (let i in b) {
    if (a[0] === b[i]) {
      let temp = true;
      for (let j in a) {
        // ~~操作符将正整数字符串转换为整数
        if (a[j] !== b[~~i + ~~j]) {
          temp = false;
        }
      }
      if (temp) {
        return ~~i;
      }
    }
  }
  return -1;
}

实现千分分隔符

// 保留三位小数
parseToMoney(1234.56); // return '1,234.56'
parseToMoney(123456789); // return '123,456,789'
parseToMoney(1087654.321); // return '1,087,654.321'

function parseToMoney(num) {
  let [integer, decimal] = num.toFixed(3).split(".");
  // 零宽断言，匹配位置
  integer = integer.replace(/\d(?=(\d{3})+$)/g, "$&,");
  return integer + (decimal ? `.${decimal}` : "");
}

验证电话

function isPhone(tel) {
  let reg = /^1[345678]\d{9}/;
  return reg.text(tel);
}

验证邮箱

function isEmail(email) {
  let reg = /^([0-9a-zA-Z_\-])+@([0-9a-zA-Z_\-])+(\.[0-9a-zA-Z_\-])+$/;
  return reg.text(email);
}

验证身份证

function isEmail(email) {
  let reg = /(^\d{15}$)|(^\d{18}$)|(^\d{17}[\dXx]$)/;
  return reg.text(email);
}

其他

分别用深度优先思想和广度优先思想实现一个拷贝函数

// 深度优先
const clone = (node) => {
  const children = node.children;
  if(children.length) {

  }
}