До чтения
Статья будет разделена на три части: верхнюю, среднюю и нижнюю, включая некоторые распространенные вопросы по алгоритму собеседования, большинство из которых взяты из книги «Предложение меча». из них из моей коллекции. Способов решения проблемы много, надеюсь креветки прокомментируют и обсудят или поправят меня
1. Обход массива
Вопрос: В массиве каждая строка сортируется по возрастанию слева направо, а каждый столбец сортируется по возрастанию сверху вниз. Завершение: введите такой двумерный массив и целое число и определите, содержит ли массив целое число.
Идеи: заказываются массивы, она может уменьшить количество прохождений в соответствии с законом. Пересекающиеся от верхнего правого угла, если числа не равны, то это может быть размер некоторых чисел может быть удален через строки / столбцы на основе количества целей.
function findNumInSortedArray(arr, num) {
if (!Array.isArray(arr) || typeof num != 'number' || isNaN(num)) {
return;
}
let rows = arr.length;
let columns = arr[0].length;
let row = 0;
let column = columns -1;
while(row < rows && column >=0 ){
if (arr[row][column] == num) {
return true;
} else if (arr[row][column] > num) {
column --;
} else {
row ++ ;
}
}
return false;
}
2. Замена струн
Название: Реализуйте функцию, которая заменяет каждый пробел в строке на %20. Если ввести «мы счастливы», вывести «мы%20являемся%20счастливы»
Идея: Обычную замену и замену обхода можно использовать двумя способами.
//使用正则
function replaceStr(str){
if (typeof str !== 'string') {
console.log('str is not string');
return;
}
return str.replace(/\s/g, '%20')
}
//使用遍历替换,需要遍历str，识别空格然后替换字符串
function replaceStr2(str) {
if (typeof str !== 'string') {
console.log('str is not string');
return;
}
let strArr = [];
let len = str.length;
let i = 0;
while(i < len) {
if (str[i] === ' ' ) {
strArr[i] = '%20';
} else {
strArr[i] = str[i];
}
}
return strArr.join('');
}
3. Распечатайте связанный список в обратном порядке.
Заголовок: введите головной узел связанного списка и напечатайте значение каждого узла от конца до начала.
Идея: вы можете перевернуть связанный список и распечатать его снова, но это разрушит структуру связанного списка. Вы также можете использовать стек для хранения узлов, а затем распечатать
function displayLinkList(head) {
let stack = [];
let node = head;
while(node) {
stack.push(node);
node = node.next;
}
for (let len = stack.length - 1; len >=0 ; len--) {
console.log(stack[i].ele);
}
}
4. Перестроить бинарное дерево
Название: Введите результаты прямого и обратного обхода бинарного дерева, пожалуйста, восстановите бинарное дерево. Предполагается, что результаты входного обхода в прямом и обратном порядке не содержат повторяющихся чисел. Например, введите последовательность обхода в прямом порядке {1,2,4,7,3,5,6,8} и последовательность обхода в неупорядоченном порядке {4,7,2,1,5,3,8,6}, затем перестройте бинарное дерево и возврат.
Идея: При прямом обходе бинарного дерева первое число всегда является значением корневого узла дерева, а при неупорядоченном обходе значение корневого узла находится в середине последовательности. Найдите корневой узел, определите левое и правое поддеревья, а затем рекурсивно выполните цикл.Ключ состоит в том, чтобы по очереди смонтировать «корневой» узел (определить, находится ли он слева или справа). Предварительный порядок определяет корневой узел, а средний порядок определяет левый и правый узлы.
//节点定义
function TreeNode(ele) {
this.ele = ele;
this.right = null;
this.left = null;
}
function constructBinaryTree(preOrders, inOrders) {
if (!inOrders.length) {
return null;
}
let rootIndex = 0;
let l_preOrders = [];
let l_inOrders = [];
let r_preOrders = [];
let r_inOrders = [];
//确定根节点
let head = new TreeNode(preOrders[0]);
for (let i = 0; i < inOrders.length; i++ ) {
if (preOrders[0] === inOrders[i]) {
rootIndex = i;
}
}
//确定左右子节点树
for (let i = 0; i < rootIndex; i++) {
l_preOrders.push(preOrders[ i + 1]);
l_inOrders.push(inOrders[i]);
}
for (let i = rootIndex + 1; i < inOrders.length; i ++ ) {
r_preOrders.push(preOrders[i]);
r_inOrders.push(inOrders[i]);
}
head.left = constructBinaryTree(l_preOrders, l_inOrders);
head.right = constructBinaryTree(r_preOrders, r_inOrders);
return head;
}
function getTreeFromPreInOrders(preOrders, inOrders) {
if (Array.isArray(preOrders) && Array.isArray(inOrders)) {
return constructBinaryTree(preOrders, inOrders);
}
console.error('preOrders or inOrders is no Array');
}
5. Взаимная реализация стека и очереди
Стек: FIFO, очередь: FIFO
-
Тема: Реализация очереди с двумя стеками
Идея: все данные стека a помещаются в стек b по очереди, затем данные, которые изначально были введены в стек a, окажутся на вершине стека b, тогда удаление очереди из очереди эквивалентно удалению стека b, и вход в очередь, эквивалентный толчку стека a. Когда стек b пуст, извлеките все данные из стека a в стек b.
let stack_a = [];
let stack_b = [];
function push (node ) {
stack_a.push(node);
}
function pop () {
if (stack_b.length === 0 ) {
for (let i = 0, len = stack_a.length; i < len; i ++ ) {
stack_b.push(stack_a.pop());
}
}
return stack_b.pop();
}
-
Тема: Реализация стека с использованием двух очередей
Идея: Две очереди, взять одну очередь в качестве области хранения, а очередь с данными поочередно извлекает данные из очереди в кеш-очередь, затем, когда очередь с данными выходит до последних данных, именно эти данные и нужно выталкивать стека. Данные, помещенные в стек, ставятся в очередь с данными. Если две пустые, то любая из них будет поставлена в очередь.
let queue_a = [];
let queue_b = [];
function push(node) {
if (queue_a.length && queue_b.length) {
return console.log('wrong !');
}
if (queue_a.length) {
queue_a.push(node);
} else if (queue_b.length) {
queue_b.push(node);
} else {
queue_a.push(node);
}
}
function pop() {
if (queue_a.length && !queue_b.length) {
for (let i = 0, len = queue_a.length; i < len; i++) {
if (i == len -1) {
return queue_a.shift();
} else {
queue_b.push(queue_a.shift());
}
}
} else if (!queue_a.length && queue_b.length) {
for (let i = 0, len = queue_b.length; i < len; i++) {
if (i == len -1) {
return queue_b.shift();
} else {
queue_a.push(queue_b.shift());
}
}
} else if (queue_a.length && queue_b.length) {
console.log('wrong!');
} else {
return null;
}
return null;
}
6. Поверните наименьшее число массива
Название: Перемещение первых элементов числа в конец массива, что называется поворотом массива. Введите поворот возрастающего отсортированного массива, выведите наименьший элемент повернутого массива. Например, массив {3,4,5,1,2} представляет собой поворот {1,2,3,4,5}, а минимальное значение массива равно 1.
Идея: чтобы найти наибольшее значение в возрастающем порядке, вы можете попробовать метод дихотомии. Первый элемент массива должен быть больше последнего элемента.Выберите средний элемент и сравните его с последним элементом.Если он больше последнего элемента, это означает, что наименьший элемент находится в правильном диапазоне, в противном случае он в левом диапазоне.
function findMinFromRotateArr(arr) {
if (!Array.isArray(arr)) {
return console.error('wrong!')
}
let start = 0;
let end = arr.length - 1;
while((end - start) > 1) {
let mid = Math.floor(((end + start)) / 2) ;
if (arr[mid] >= arr[end]) {
start = mid;
} else {
end = mid;
}
}
return arr[end];
}
7. Последовательность Фибоначчи
Вопрос: При n = 0 f(n) = 0, при n = 1 f(n) = 1, при n > 1 f(n) = f(n-1) + f(n-2) . Теперь вас просят ввести целое число n, выведите n-й элемент последовательности Фибоначчи.
Идея: Последовательность Фибоначчи — это классическая математическая задача. Это можно решить с помощью рекурсии и цикла.Обратите внимание, что при рекурсии, если n относительно велико, это приведет к большому потреблению памяти.
//递归解法
function fibonacci(n) {
if (n <= 0) {
return 0;
}
if(n == 1) {
return 1;
}
return fibonacci(n - 2) + fibonacci(n-1);
}
//循环解法
function fabonacci(n) {
if (n <= 0) {
return 0;
}
if(n == 1) {
return 1;
};
let fn_2 = 0;
let fn_1 = 1;
let fn = 0;
for (let i = 2; i <= n; i++) {
fn = fn_1 + fn_2;
fn_2 = fn_1;
fn_1 = fn;
}
return fn;
}
-
Проблема изменения Фибоначчи 1 Надпись: Лягушка может подпрыгнуть на 1 ступеньку за раз или на 2 ступеньки за раз. Найдите, сколькими способами лягушка может запрыгнуть на n-ступенчатую лестницу.
Идея: метод прыжка за n шагов -> f(n), если прыгает первый раз на один уровень, то следующий метод прыжка f(n-1), если первый прыгает 2 шага, то метод прыжка f ( п-2). Тогда f(n) = f(n-1) + f(n-2), что является последовательностью Фибоначчи.
-
Задача преобразования Фибоначчи 2 Заголовок: Заголовок: [] Это прямоугольник 2x1, который можно расположить горизонтально или вертикально, сколькими способами он может покрыть небольшой прямоугольник, например 8*2x1?
//大矩形：[][][][][][][][] // [][][][][][][][]Идея: Если маятник расположить вертикально, то он будет занимать 1 столбец Если его расположить горизонтально, то маятниковый метод займет 2 столбца Тогда из прямоугольника из 8 столбцов, при размещении его в первый раз, либо расположите его вертикально , а затем накройте его.7 столбиков прямоугольников, либо сбоку, затем накройте 6 столбцов прямоугольников. Таким образом, это можно представить как f(8) = f(7) + f(6). Все еще проблема Фибоначчи
8. Битовая операция
Битовые операции в js: & (и), | (или), ~ (не), ^ (исключающее или), > (сдвиг вправо), >>> (беззнаковый сдвиг вправо)
-
Вопрос: Введите целое число и выведите количество единиц в двоичном представлении числа. Отрицательные числа представлены в дополнении.
Идея: вы можете использовать правый сдвиг и побитовые операции И. Определить, является ли самая правая цифра двоичного числа целого числа 1 (и 1 и), а затем сдвинуться вправо, пока она не станет 0
//缺陷版：
//缺陷在于不能针对负数情况。因为带符号的数字，其二进制最高位有一个数字为符号标志，负数为1
function numOf1(n) {
if(n.toString().indexOf('.') != -1) {
return console.error('n is not a int');
}
let num = 0;
while(n) {
if (n & 1) {
num ++ ;
}
n = n >> 1;
}
return num;
}
//改进：将1进行左移与i比较，这样来判断i二进制各个位是不是1
//如果是32位存储，那么会循环32次
function numOf1(n){
if(n.toString().indexOf('.') != -1) {
return console.error('n is not a int');
}
let nums = 0;
let flag = 1;
while(flag) {
if(flg & n) {
nums ++;
}
flag = flag << 1;
}
return nums;
}
//究极版：这个的原理是 一个二进制与其减去1的二进制进行位与运算后，产生的数与原先的二进制数相比，
//从右边看会少去一个1。问题可以简化到二进制数有多少个1，就会进行以上多少次的循环，这个是效率最高的
function numsOf1(n) {
if(n.toString().indexOf('.') != -1) {
return console.error('n is not a int');
}
let nums = 0;
while(n) {
nums ++ ;
n = (n - 1) & n;
}
return nums;
}
9, целая степень значения
Вопрос: Дана база с плавающей запятой типа double и целочисленный показатель типа int. Найдите показатель степени основания. Не используйте библиотечные функции
Идея: Первая реакция на решение проблемы — использовать цикл for для накопления произведений, но некоторые ситуации можно игнорировать: входное значение 0 и отрицательная целая степень. И как уменьшить количество обходов
function power(base, exponent) {
if (base == 0 && exponent < 0) {
return console.error('base should not be 0');
}
let absExponent = exponent < 0 ? -exponent : exponent;
let result = 1;
for (let i = 1; i <= absExponent; i++) {
result *= base;
}
if (exponent < 0) {
result = 1 / result;
}
return result;
}
//使用递归减少乘积次数
//使用位与运算可判断奇偶， 整数右移一位可取数除2的整数
//可以通过互乘减少运算次数，如 数的8次方是数的4次幂的2次幂，数的4次幂是数的2次幂的2次幂 ...
function power (base, exponent) {
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
let result = power(base, exponent >> 1);
result *= result;
//为奇数
if (exponent & 1 == 1) {
result *= base;
}
return result;
}
10. Удалить узел связанного списка
Заголовок: определите функцию для удаления узла, передайте параметры в качестве головного узла и удаляемого узла, а временная сложность должна быть O (1).
Идея: чтобы удалить обычный связанный список, он проходит через удаляемый узел, а затем указывает свой предыдущий узел на следующий узел. Но каждое удаление необходимо пройти, а временная сложность составляет O (n). Если вы напрямую присваиваете значение следующего узла удаляемого узла удаляемому узлу, а затем удаляете следующий узел, разве это не эквивалентно удалению?
function deleteNode(headNode, deleteNode) {
if (!headNode || !deleteNode) {
return ;
}
//删除的节点是头结点
if (headNode == deleteNode) {
headNode = null;
}
//删除的节点是尾节点
else if (deleteNode.next == null) {
let node = headNode;
while(node.next != deleteNode) {
node = node.next;
}
node.next = null;
deleteNode = null;
}
//删除的节点是中间节点
else {
let nextNode = delete.next;
deleteNode.ele = nextNode.ele;
deleteNode.next = nextNode.next;
nextNode = null;
}
}
//整体时间：[(n-1)O(1) + O(n)]/n -> O(1)
11. Настройте порядок массива
Вопрос: Введите массив целых чисел и реализуйте функцию для корректировки порядка чисел в массиве таким образом, чтобы все нечетные числа находились в первой половине массива, а все четные числа — во второй половине массива.
Идея: Массив можно обходить в обычных условиях, если число четное, то число можно вынуть и поставить в конец массива, а число за ним сдвинуть вперед на единицу. В то же время также можно использовать два указателя, один указывает на начало массива p1, а другой указывает на конец массива p2.Если p1 указывает на четное число, а p2 указывает на нечетное число, две стороны будут будет 4 ситуации, которые можно обработать по очереди.
function reOrderArray(arr)
{
// write code here
if (!Array.isArray(arr)) {
return ;
};
let start = 0;
let end = arr.length - 1;
while(start <= end) {
let isOddS = arr[start] & 1;
let isEvenE = !(arr[end] & 1);
if (isOddS && !isEvenE) {
start ++;
} else if (isOddS && isEvenE) {
start ++;
end --;
} else if(!isOddS && isEvenE) {
end --;
} else {
let temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start ++ ;
end --;
}
}
return arr;
}
12. k-й узел производной в связном списке
Вопрос: Введите связанный список и выведите k-й узел снизу связанного списка.
Идея: общая идея состоит в том, чтобы пройти по связанному списку в первый раз, чтобы получить его длину, а затем подсчитать k-й узел снизу, затем это n+1-k-й узел, а затем пройти по связанному списку во второй раз. Недостатком является то, что его нужно дважды просмотреть связанный список. Метод однократного обхода связанного списка: берем два указателя, один указатель указывает на головной узел, другой указатель указывает на k-1-й узел, а затем два указателя обходят одновременно, когда второй указатель указывает на конец связанного списка, затем первый Указатель будет указывать на k-й узел производной
//注意边界情况：头结点为空，节点数小于k个，k不大于0
function findKthToTial (head, k) {
if (!head || k <= 0) {
return null;
}
let startNode = head;
let endNode = head;
for (let i = 0; i < k - 1; i++) {
if (!endNode.next) {
return null;
}
endNode = endNode.next;
}
while(endNode.next) {
startNode = startNode.next;
endNode = endNode.next;
}
return startNode;
}
13. Обратно связанный список
Заголовок: введите связанный список, переверните связанный список и выведите заголовок нового связанного списка.
Идея: пройти по связанному списку и указать следующий узел на предыдущий узел
function resverseList(head) {
if (!head) {
return null;
}
if (head.next == null) {
return head;
}
let node = head;
let nextNode = null;
let reservedNode = null;
let newHead = head;
while (node.next) {
nextNode = node.next;
reservedNode = nextNode.next;
nextNode.next = newHead;
node.next = reservedNode;
newHead = nextNode;
}
return newHead;
}
14. Объединить два отсортированных связанных списка
Заголовок: Введите два монотонно возрастающих связанных списка и выведите связанный список после объединения двух связанных списков.Конечно, нам нужен объединенный связанный список, чтобы удовлетворить монотонно неубывающему правилу
Идея: взять узлы двух связанных списков по очереди и сравнить их
function mergeLinkList(head1, head2) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
let mergeHead = null;
if (head1.ele < head2.ele ) {
mergeHead = head1;
mergeHead.next = mergeLinkList(haed1.next, head2);
} else {
mergeHead = head2;
mergeHead.next = mergeLinkList(head1, head2.next);
}
return mergeHead;
}
15. Включение бинарного дерева
Введите два бинарных дерева A и B, чтобы определить, является ли B подструктурой A.
Идея: Сначала найдите корневой узел A, содержащий B, а затем сравните левое и правое поддеревья в соответствии с этим узлом.
//树节点定义
function Node(ele) {
this.ele = ele;
this.left = null;
this.right = null;
}
//判断树A有树B
function hasSubTree(pRootA, pRootB) {
if(pRootA == null || pRootB == null) {
return false;
}
let result = false;
if (pRootA.ele === pRootB.ele） {
result = doesTreeAHaveTreeB(pRootA, pRootB);
}
if (!result) {
result = hasSubTree(pRootA.left, pRootB);
}
if (!result) {
result = hasSubTree(pRootA.right, pRootB)
}
return result;
}
function doesTreeAHaveTreeB(pRootA, pRootB) {
//先要判断 pRootB
if (pRootB == null) {
return false;
}
if(pRootA == null) {
return true;
}
if (pRootA.ele != pRootB.ele) {
return false;
}
return doesTreeAHaveTreeB(pRootA.left, pRootB.left) && doesTreeAHaveTreeB(pRootA.right, pRootB.right)
}
16. Зеркальное отображение бинарного дерева
Название: Завершите функцию, которая принимает на вход двоичное дерево, и функция выводит его зеркальное отображение.
Идея: выполнить предварительный обход, для нелистовых узлов, если есть два узла, поменять их местами
function mirror(root) {
if (root == null) {
return ;
}
let temp = root.left;
root.left = root.right;
root.right = temp;
if (root.left) {
mirror(root.left);
}
if (root.right) {
mirror(root.right);
}
}
17. Распечатайте матрицу по часовой стрелке
Вопрос: / Введите матрицу, распечатайте каждое число по часовой стрелке снаружи внутрь, например, если ввести следующую матрицу: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Затем распечатайте по очереди выпадают числа 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10.
Идея: Суть в том, что условие циклической печати состоит в том, что количество столбцов > количество столбцов для начала печати x2, а количество строк > количество строк для начала печати x2
function printMatrix (arr) {
if (!Array.isArray(arr)) {
return;
}
let rows = arr.length;
let columns = arr[0].length;
let start = 0;
while( columns > start * 2 && rows > start * 2) {
printMatrixInCicle(arr, columns, rows, start);
start ++ ;
}
}
function printMatrixInCicle (arr, columns, rows, start) {
let endX = columns - 1 - start;
let endY = rows -1 - start;
//从左到右打印一行
for (let i = start; i <= endX; ++i) {
console.log(arr[start][i]);
}
//从上到下打印一列
if (start < endY) {
for (let i = start + 1; i <= endY; ++ i) {
console.log(arr[endY][i]);
}
}
//从右向左打印一行
if (start < endX && start < endY) {
for (let i = endX -1 ; i >= start; --i) {
console.log(arr[endY][i]);
}
}
//从下到上打印一行
if (start < endX && start < endY - 1) {
for (let i = endY -1 ; i >= start + 1; --i) {
console.log(arr[i][start]);
}
}
}
Дорогие зрители, если вы думаете, что можете,biaozhiwang.github.ioпод звездой