1. Алгоритмы сортировки
Пузырьковая сортировка в JavaScript:
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
Сортировка слиянием в JavaScript:
function mergeSort(arr) {
if (arr.length === 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
Быстрая сортировка в JavaScript:
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}
function partition(arr, left, right) {
const pivot = arr[right];
let i = left - 1;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Сортировка кучей в JavaScript:
function heapSort(arr) {
buildMaxHeap(arr);
for (let i = arr.length - 1; i >= 1; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
return arr;
}
function buildMaxHeap(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
}
function heapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Важно отметить, что эти алгоритмы имеют разную временную и пространственную сложность, и некоторые из них могут лучше подходить для конкретных случаев использования, чем другие. При выборе алгоритма сортировки важно учитывать размер данных, желаемую временную сложность и желаемую пространственную сложность.
2. Алгоритм поиска
Вот пример бинарного поиска, поиска в ширину и поиска в глубину в JavaScript:
Двоичный поиск в JavaScript:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Первый в ширину в JavaScript:
// Breadth-First Search
function breadthFirstSearch(root, target) {
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
if (node.value === target) {
return node;
}
queue.push(...node.children);
}
return null;
}
Сначала в глубину в JavaScript:
// Depth-First Search
function depthFirstSearch(root, target) {
if (root.value === target) {
return root;
}
for (const child of root.children) {
const result = depthFirstSearch(child, target);
if (result) {
return result;
}
}
return null;
}
В приведенном выше примере binarySearch принимает массив arr и целевое значение и возвращает индекс целевого значения в массиве, если оно существует, или -1, если оно не существует.
breadthFirstSearch берет дерево, представленное корневым узлом и целевым значением, и возвращает узел в дереве с целевым значением, если он существует, или null, если он не существует.
depthFirstSearch берет дерево, представленное корневым узлом и целевым значением, и возвращает узел в дереве с целевым значением, если он существует, или null, если он не существует.
а. Пример использования функции binarySearch в JavaScript:
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 6;
const result = binarySearch(arr, target);
if (result === -1) {
console.log(`${target} not found in the array`);
} else {
console.log(`${target} found at index ${result}`);
}
В этом примере функция binarySearch вызывается с массивом arr и целевым значением 6. Функция возвращает 5, который является индексом 6 в массиве. Затем код проверяет результат и выводит соответствующее сообщение на консоль.
б. Пример использования функции breadthFirstSearch в JavaScript:
const tree = {
value: 1,
children: [
{
value: 2,
children: [
{ value: 4, children: [] },
{ value: 5, children: [] },
]
},
{
value: 3,
children: [
{ value: 6, children: [] },
{ value: 7, children: [] },
]
},
]
};
const target = 5;
const result = breadthFirstSearch(tree, target);
if (!result) {
console.log(`${target} not found in the tree`);
} else {
console.log(`${target} found with value ${result.value}`);
}
В этом примере функция breadthFirstSearch вызывается с деревом, представленным корневым узлом, и целевым значением 5. Функция возвращает узел в дереве со значением 5, который является дочерним узлом корневого узла. Затем код проверяет результат и выводит соответствующее сообщение на консоль.
в. Пример использования функции depthFirstSearch в JavaScript:
const tree = {
value: 1,
children: [
{
value: 2,
children: [
{ value: 4, children: [] },
{ value: 5, children: [] },
]
},
{
value: 3,
children: [
{ value: 6, children: [] },
{ value: 7, children: [] },
]
},
]
};
const target = 5;
const result = depthFirstSearch(tree, target);
if (!result) {
console.log(`${target} not found in the tree`);
} else {
console.log(`${target} found with value ${result.value}`);
}
В этом примере функция depthFirstSearch вызывается с деревом, представленным корневым узлом, и целевым значением 5. Функция возвращает узел в дереве со значением 5, который является дочерним узлом корневого узла. Затем код проверяет результат и выводит соответствующее сообщение на консоль.
3. Динамическое программирование
Динамическое программирование — это метод решения проблем путем их разбиения на более мелкие подзадачи и повторного использования решений этих подзадач для поиска решения исходной проблемы. Ключевая идея динамического программирования состоит в том, чтобы избежать избыточных вычислений, запоминая промежуточные результаты и повторно используя их по мере необходимости.
Вот пример того, как использовать динамическое программирование в JavaScript для решения задачи нахождения n-го числа Фибоначчи:
function fibonacci(n, memo = {}) {
if (n <= 0) return 0;
if (n === 1) return 1;
if (memo[n]) return memo[n];
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
console.log(fibonacci(10));
В этом примере функция fibonacci использует технику запоминания для сохранения промежуточных результатов в объекте, переданном в качестве аргумента. Это позволяет функции повторно использовать решения подзадач, улучшая временную сложность вычислений. Функция возвращает n-е число Фибоначчи, доступ к которому можно получить, вызвав fibonacci(10) в этом примере.
4. Алгоритм рекурсии
Рекурсия — это метод, при котором функция вызывает саму себя, чтобы решить проблему, разделив ее на более мелкие подзадачи. Подзадачи решаются рекурсивно, а решения подзадач объединяются, чтобы найти решение исходной проблемы. Рекурсия полезна для решения проблем с рекурсивной структурой, когда решение проблемы может быть выражено в терминах решений более мелких экземпляров той же проблемы.
Вот пример использования рекурсии в JavaScript для вычисления факториала заданного числа:
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
console.log(factorial(5));
В этом примере функция factorial вызывает себя рекурсивно, пока не будет достигнут базовый случай, где n === 1. Функция возвращает произведение n и факториала n - 1, что является результатом рекурсивного вызова. Решение исходной задачи получается путем объединения решений подзадач таким образом. Факториал 5 можно вычислить, вызвав factorial(5), который вернет 120.
5. Алгоритм «разделяй и властвуй»
Разделяй и властвуй — это алгоритмический метод, при котором проблема делится на более мелкие подзадачи, которые легче решить. Затем решения подзадач объединяются, чтобы найти решение исходной проблемы. Подход «разделяй и властвуй» полезен для решения проблем, которые можно разбить на более мелкие подзадачи, похожие на исходную проблему.
Вот пример того, как использовать разделяй и властвуй в JavaScript, чтобы найти максимальное число в массиве:
function max(array, start, end) {
if (start === end) return array[start];
const mid = Math.floor((start + end) / 2);
const leftMax = max(array, start, mid);
const rightMax = max(array, mid + 1, end);
return Math.max(leftMax, rightMax);
}
const array = [1, 2, 3, 4, 5];
console.log(max(array, 0, array.length - 1));
В этом примере функция max использует подход «разделяй и властвуй», чтобы найти максимальное число в массиве. Массив делится на две половины, и максимальное число в каждой половине находится путем рекурсивного вызова функции max. Конечным результатом является максимальное из двух результатов, то есть максимальное число во всем массиве. Вызов max(array, 0, array.length - 1) вернет 5, что является максимальным числом в массиве.
6. Техника хеширования
Хэширование — это метод, используемый в информатике для сопоставления данных произвольного размера с данными фиксированного размера. Хэш-функция принимает входные данные, известные как сообщение или прообраз, и возвращает строку символов фиксированного размера, известную как хэш или дайджест. Один и тот же ввод всегда будет давать один и тот же хэш, но даже небольшое изменение ввода приведет к совершенно другому хешу.
В JavaScript хэши можно генерировать с помощью модуля crypto, обеспечивающего криптографическую функциональность. Вот пример использования модуля crypto для генерации хэша SHA-256:
const crypto = require('crypto');
function hash(message) {
return crypto.createHash('sha256')
.update(message)
.digest('hex');
}
const message = 'Hello, world!';
console.log(hash(message));
В этом примере функция hash использует модуль crypto для создания хэша SHA-256 входного сообщения. Вызов hash(message) вернет строку шестнадцатеричных символов, представляющую хэш входного сообщения. Один и тот же ввод всегда будет давать один и тот же хэш, поэтому этот метод можно использовать для проверки целостности данных.
