[Резюме интервью] Вспомните провал интервью Билибили (2)

внешний интерфейс опрос

Прошлая статья получила такое внимание.Спасибо за ваши лайки и комментарии.Это дало мне большую мотивацию продолжать обновлять эту серию.Я также надеюсь, что они могут быть полезны всем. Краб всех.

портал

Основы алгоритма: плоский массив, дедупликация и сортировка

Без лишних слов, давайте сразу к теме.

let arr = [
  [
    ['1-7', '2-6'],
    '4-6',
    [
      ['2-0', '1-4'],
      ['3-9'],
      '4-5',
    ],
  ]
]

// Q1: 完成数组 flat 函数
function flat(arr) {
  // code
  return arr
}

arr = flat(arr);
console.log(arr);

// Q2: 计算 arr 中所有的值：'1-7' => 1 * 7 = 7， 返回一个数字组成的数组
function calc(arr) {
  // code
  return arr;
}

arr = calc(arr);
console.log(arr);

// Q3: 对这个数组排序和去重
function sortAndReduce(arr) {
  // code
  return arr;
}

arr = sortAndReduce(arr);
console.log(arr);

Q1: Плоский массив

Назад во времени

Эта структура массива относительно глубокая, что должно быть тестовым центром всей темы. Похоже, вам нужно использовать рекурсию, нет! Должен быть лучший способ, 🤔 Тогда используйте ES 2019Array.prototype.flatфункция! Затем интервьюер проголосовал против него. Пока я писал и думал, интервьюер спросил мои мысли и закончил вопрос.

Сценарий 1: Рекурсия

Если есть студенты, которые не знакомы с рекурсией, вы можете взглянуть на мои заметки по чтению.[Схема алгоритма] Примечания к прочтению: Глава 3 Рекурсия.

Рекурсивное ядро ​​лежит в двух этапах: найдите базовые условия и условия рекурсии.

function flat(arr) {
  const result = []; // 利用闭包缓存我们的结果
  function _flat(arr) {
    arr.forEach(element => {
      if(Array.isArray(element)) { // 递归条件
        _flat(element);
      } else { // 基准条件
        result.push(element); // 将符合结果的值推入我们的结果数组中
      }
    })
  }
  _flat(arr);
  arr = result;
  return arr;
}

// 更加简练的版本
// 感谢 @zwlafk
const flat = arr => [].concat(...arr.map(v => Array.isArray(v) ? flat(v) : v));

Сценарий 2: Итерация — поиск в ширину

Эта идея была написана мной с использованием главы алгоритма поиска в ширину в «Графических алгоритмах».

  1. Создайте массив и сохраните результаты
  2. создать очередь
  3. инициализация
  4. Используйте цикл while для перебора каждого элемента в списке
  5. вытолкнуть первый элемент из очереди
    • Если это массив, поместите дочерние элементы в очередь по порядку.
    • Если строка, подтолкнуть дочерний элемент к результату
  6. Когда длина списка равна 0, обход завершен

Но упорядоченность результатов поиска в ширину не гарантируется.

function flat(arr) {
  const result = []; // 储存结果
  const list = []; // 队列
  function _forEach(arr) {
    arr.forEach(el => {
      if(Array.isArray(el)) list.push(el); // item 如果是数组，将子项依次推入队列
      else result.push(el); // item 如果是字符串，将子项推入结果
    });
  }
  _forEach(arr); // 初始化
  while(list.length > 0) { // 当 list 长度为0时候，遍历完成
    const item = list.shift();
    _forEach(item);
  }
  arr = result;
  return arr;
}

СДЕЛАТЬ:

  • Вышеуказанные два метода - это только мое скромное мнение, я надеюсь увидеть все более и более совершенные алгоритмы в области комментариев.

Решение 3. Оппортунистические toStrings

Спасибо @IWANABETHATGUY за обучение.

// 首页你得确定你的数据里面没有字符串 ',' 哦
function flat(arr) {
  arr = arr.toString().split(',')
  return arr;
}

// or 
// 异曲同工
function flat(arr) {
  arr = arr.join(',').split(',')
  return arr;
}

Сценарий 4: Итерация — поиск в глубину

Спасибо @IWANABETHATGUY за обучение.

Принцип аналогичен побочному ширину, проходящей массив, имитируя поведение стека. Преимущество заключается в том, что он может гарантировать упорядоченный выход.

function flat(arr) {
  let result = [];
  let stack = []; // 模拟栈的行为

  function forEachRight(arr) {
    for (let i = arr.length - 1; i >= 0; i--) { // 先进后出
      const item = arr[i];
      if(Array.isArray(item)) stack.push(item);
      else result.push(item);
    }
  }
  if (arr.length > 0) forEachRight(arr);
  while (stack.length > 0) { // 当栈空了，遍历完成
    let current = s.pop();
    if(current.length > 0) {
       forEachRight(current); // 感谢 @Drowned-fish 朋友的建议
    }
  }
  return ret;
}

Q2: Расчет массива '1-7' => 1 * 7 = 7

Эта задача не сложная, она заключается в изучении использования некоторых общих методов и непосредственно кода.

function calc(arr) {
  // 随手骚一下，不建议 eval
  arr = arr.map(el => eval(el.replace('-', '*')));
  return arr;
}

// or

function calc(arr) {
  arr = arr.map(el => {
    const [n1, n2] = el.split('-');
    return +n1 * +n2;
  });
  return arr;
}

Q3: Сортировка массивов и дедупликация

Дедупликацию массива можно выполнить с помощью ES6 Set. Портал:ES6 Установить структуру данных, без дальнейшего уточнения. Сортировка массива может быть достигнута с помощью функции Array.prototype.sort. Однако очевидно, что при изучении содержания алгоритма нативный метод нельзя использовать напрямую, а сортировка и дедупликация выполняются одновременно, поэтому производительность однозначно лучше.

Ранее я писал сравнение и реализацию нескольких обычных методов сортировки,[Ориентация на собеседовании по JS] Введение в сортировку выбором, сортировку сегментами, пузырьковую сортировку и быструю сортировку, здесь я напрямую использую быструю сортировку для завершения работы по сортировке и дедупликации.

function sortAndReduce(arr) {
  if(arr.length < 2) {
    return arr;
  } else {
    const pivot = arr[0]; // 基准值
    const lowArr= []; // 小的放左边
    const hightArr = []; // 大的放右边
    arr.forEach(current => {
      if(current > pivot) hightArr.push(current);
      else if(current < pivot) lowArr.push(current);
    })
    return sortAndReduce(lowArr).concat(pivot, sortAndReduce(hightArr));
  }
}

Суммировать:

  • Книга в конечном счете поверхностна. Еще предстоит пройти долгий путь, прежде чем научиться быть успешным. Это интервью дало мне понять, что причиной нервозности является отсутствие прочной основы.
  • Не говоря уже о том, чтобы почистить leetcode.
Категории