задний план
Наша повседневная работа по разработке не может не иметь дело с данными. При отображении данных структура данных, возвращаемая интерфейсом, не может быть использована напрямую, и требуется слой преобразования; при сохранении данных структура данных, полученная через форму, может не соответствовать структуре данных, определенной интерфейсом , и требуется слой конвертации; так же есть потребности самих некоторых бизнес-сценариев, которые требуют логической проверки данных и т.д. Поэтому неизбежно использование некоторых часто используемых структур данных и алгоритмов. В этой статье в основном обсуждаются структуры данных и алгоритмы, которые можно использовать при разработке интерфейса.
структура данных
куча
Стек — это особый вид линейного списка. Его особенностью является то, что им можно управлять только на одном конце стола. Тот конец, которым можно манипулировать, называется вершиной стека, а другой конец, которым нельзя манипулировать, называется низом стека. Характеристики стека: первый пришел, последний вышел.
принцип
Примеры из жизни: булочки на пару, трубочки для бадминтона.
выполнить
Мы можем использовать JS для имитации функциональности стека. С точки зрения хранения данных вы можете использовать массив для хранения данных или связанный список для хранения данных. Поскольку массивы — это самый простой способ, вот как реализовать стеки в массивах.
Операции со стеком включают в себя вталкивание, извлечение, опустошение, получение верхнего элемента стека, получение размера стека и так далее.
class Stack {
constructor() {
// 存储数据
this.items = [];
}
push(item) {
// 入栈
this.items.push(item);
}
pop() {
// 出栈
return this.items.pop();
}
top() {
// 获取栈顶元素
return this.items[this.items.length - 1];
}
clear() {
// 清空栈
this.items = [];
}
size() {
// 获取栈的大小
return this.items.length;
}
isEmpty() {
// 判断栈是否为空
return this.items.length === 0;
}
}
заявление
- Проверить, совпадают ли скобки
Метод один анализ мыслей:
- Сначала пройдите всю строку от начала до конца;
- Когда встречается символ "(", он помещается в стек, а символ ")" извлекается из стека;
- При извлечении из стека, если стек уже пуст, вернуть false;
- При обходе строки проверьте, не пуст ли стек.
Второй метод анализа мышления:
- Объявите переменную num как 0 и пройдите всю строку от начала до конца;
- Когда встречается символ "(", число увеличивается на 1, а символ ")" уменьшается на 1;
- В процессе обхода, когда num уменьшается на 1, значение num уже равно 0 и возвращается false;
- Когда строка пройдена, проверьте, равно ли num 0.
// 方式一：栈
function isPairing(str = '') {
const stack = new Stack();
for(let i of str) {
if (i === '(') {
stack.push(i);
} else if (i === ')') {
if (stack.isEmpty()) {
return false;
} else {
stack.pop();
}
}
}
return stack.size() === 0;
}
// 方式二：计数
function isPairing(str = '') {
let num = 0;
for(let i of str) {
if (i === '(') {
num++;
} else if (i === ')') {
if (num === 0) {
return false;
} else {
num--;
}
}
}
return num === 0;
}
- Проверьте, совпадают ли HTML-теги
Анализ мыслей:
-
Объявите стек переменных, узлы и просмотрите строку HTML с самого начала, чтобы найти позицию символа "
-
Если позиция символа "
- Затем продолжайте пытаться сопоставить конечный тег HTML, если совпадение успешно и имя совпадает с именем тега в верхней части стека, вершина стека будет извлечена, в противном случае будет сообщено об ошибке;
- После того, как не удалось сопоставить закрывающий тег HTML, попробуйте сопоставить открывающую часть открывающего тега, затем выполните цикл по соответствующим парам атрибутов тега и, наконец, сопоставьте закрывающую часть открывающего тега. После завершения сопоставления поместите совпавшую метку на вершину стека и создайте количество узловых узлов;
-
Если позиция символа "
- Затем html.slice(0, pos) создайте текстовый узел.
function parseHtml(html = '') {
const startIndex = 0;
const endIndex = 0;
// 匹配标签<div>、<br/>等标签的开始部分"<div、<br"
const startTagOpen = /^<([a-zA-Z\d]+)/;
// 匹配标签<div>、<br/>等标签的闭合部分">、/>"
const startTagClose = /^\s*(\/?)>/;
// 匹配属性
const attribute = /^\s*([\w-]+)(?:="([^"]*)")?\s*/;
// 匹配闭合标签，例如</div>、</p>
const endTag = /^<\/([a-zA-Z\d]+)>/;
const stack = [];
const nodes = [];
while(html) {
// 查找<的起始位置
const index = html.indexOf('<');
if (index === 0) {
// 先匹配整体结束标签，例如</div>、</p>
let endTagMatch = html.match(endTag);
if (endTagMatch) {
if (stack[stack.length - 1]) {
if (stack[stack.length - 1].tag === endTagMatch[1]) {
// 出栈
stack.pop();
advanced(endTagMatch[0].length);
continue;
} else {
throw new Error(`起始标签和结束标签不匹配: 起始标签（${stack[stack.length - 1].tag}），结束标签（${endTagMatch[0]}）`);
}
} else {
throw new Error(`${endTagMatch[0]}没有起始标签`);
}
}
// 然后匹配起始标签的开始部分，例如<div>的<div、<p>的<p、<br/>的<br
let startTagOpenMatch = html.match(startTagOpen);
if (startTagOpenMatch) {
const node = {
nodeType: 1,
tag: startTagOpenMatch[1],
attrs: [],
children: [],
};
advanced(startTagOpenMatch[0].length);
let end, attr;
// 匹配标签属性列表
while(!(end = html.match(startTagClose)) && (attr = html.match(attribute))) {
advanced(attr[0].length);
node.attrs.push({
name: attr[1],
value: attr[2],
});
}
// 匹配起始标签的结束部分
if (end) {
if (stack.length === 0) {
nodes.push(node);
} else {
stack[stack.length - 1].children.push(node);
}
// 自闭和标签不加入栈中
if (end[1] !== '/') {
stack.push(node);
}
advanced(end[0].length);
}
}
} else {
// 文本
const node = {
nodeType: 3,
textContent: html.slice(0, index)
};
if (stack.length === 0) {
nodes.push(node);
} else {
stack[stack.length - 1].children.push(node);
}
advanced(node.textContent.length);
}
}
function advanced(n) {
html = html.substring(n);
}
return nodes;
}
parseHtml('<div id="test" class="a b"></div>');
parseHtml('<div id="test" class="a b">Hello World</div>');
parseHtml('开始<div id="test" class="a b">Hello World</div>');
parseHtml('<div id="test" class="a b"><br class="br" />Hello World</div>');
parseHtml('</div>');
parseHtml('<div></p>');
- сравнение номеров версий
Анализ мыслей:
- Номера версий v1 и v2 разбиваются на массивы по символу ".", а размер сравнивается слева направо;
- V1 больше V2 возвращает 1, V2 меньше V2 возвращает -1, V1 равно V2 возвращает 0.
/*
比较版本号大小
v1：第一个版本号
v2：第二个版本号
如果版本号相等，返回 0, * 如果第一个版本号低于第二个，返回 -1，否则返回 1.
*/
function compareVersion(v1, v2) {
if (!v1 && !v2) return 0;
if (!v1) return -1;
if (!v2) return 1;
const v1Stack = v1.split('.');
const v2Stack = v2.split('.');
const maxLen = Math.max(v1Stack.length, v2Stack.length);
for(let i = 0; i < maxLen; i++) {
// 必须转整，否则按照字符顺序比较大小
const prevVal = ~~v1Stack[i];
const currVal = ~~v2Stack[i];
if (prevVal > currVal) {
return 1;
}
if (prevVal < currVal) {
return -1;
}
}
return 0;
}
console.log(compareVersion("2.2.1", "2.2.01")); // 0
console.log(compareVersion("2.2.1", "2.2.0")); // 1
console.log(compareVersion("2.2.1", "2.1.9")); // 1
console.log(compareVersion("2.2", "2.1.1")); // 1
console.log(compareVersion("2.2", "2.2.1")); // -1
console.log(compareVersion("2.2.3.4.5.6", "2.2.2.4.5.12")); // 1
console.log(compareVersion("2.2.3.4.5.6", "2.2.3.4.5.12")); // -1
использовать
- Компиляция шаблона Vue преобразует строки шаблона в AST.
- Автоматически обновлять последнюю версию пакетов NPM.
- Стек контекста выполнения функции.
очередь
Очередь также представляет собой особый вид линейной таблицы, который характеризуется тем, что операции удаления могут выполняться только в одном конце таблицы, а операции вставки могут выполняться в другом месте таблицы. Терминал, который может выполнять операцию удаления, называетсялидер группы, а конец, который можно вставить, называетсяхвостовой конец. Удаление элемента называетсявне команды, вставив элемент с именемприсоединиться к команде. Как и стек, очередь представляет собой линейный список ограниченных операций. Характеристики очереди: First-In-First-Out (FIFO, First-In-First-Out).
принцип
Пример из жизни: Очередь купить что-нибудь.
выполнить
Мы также можем использовать JS для имитации функциональности очередей. С точки зрения хранения данных вы можете использовать массив для хранения данных или связанный список для хранения данных. Поскольку массивы — это самый простой способ, вот способ реализации очередей в массивах.
Операции с очередью включают в себя постановку в очередь, удаление из очереди, очистку очереди, получение начального элемента очереди, получение длины очереди и т. д.
class Queue {
constructor() {
// 存储数据
this.items = [];
}
enqueue(item) {
// 入队
this.items.push(item);
}
dequeue() {
// 出队
return this.items.shift();
}
head() {
// 获取队首的元素
return this.items[0];
}
tail() {
// 获取队尾的元素
return this.items[this.items.length - 1];
}
clear() {
// 清空队列
this.items = [];
}
size() {
// 获取队列的长度
return this.items.length;
}
isEmpty() {
// 判断队列是否为空
return this.items.length === 0;
}
}
заявление
- Проблема с кольцом Джозефа
Существует массив, в котором хранится 100 данных от 0 до 99. Требуется удалить число каждые два числа. Когда он достигнет конца, он перейдет к началу, чтобы продолжить, и найдет последнее число, которое нужно удалить.
Анализ мыслей
- Создайте очередь для постановки в очередь чисел от 0 до 99;
- Циклическая очередь, извлекать числа в очереди по очереди и подсчитывать номера, в настоящее время исключенные из очереди index + 1;
- Определить, равен ли текущий исключенный из очереди индекс %3 0, и если он не равен 0, войти в очередь;
- Пока длина очереди не станет равной 1, выйдите из цикла и верните число в очереди.
function ring(arr) {
const queue = new Queue();
arr.forEach(v => queue.enqueue(v));
let index = 0;
while(queue.size() > 1) {
const item = queue.dequeue();
if (++index % 3 !== 0) {
queue.enqueue(item);
}
}
return queue.head();
}
- Последовательность Фибоначчи
Последовательность Фибоначчи, также известная как последовательность Фибоначчизолотое сечениеПоследовательности, также известные как «числовые последовательности», были введены математиком Леонардо Фибоначчи на примере кролиководства.Последовательность кролика", относится к такой последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,... В математике последовательность Фибоначчи определяется рекурсивно следующим образом:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(п - 2) (n≥ 2,n∈ N*).
function fiboSequence(num) {
if (num < 2) return num;
const queue = [];
queue.push(0);
queue.push(1);
for(let i = 2; i < num; i++) {
const len = queue.length;
queue.push(queue[len - 2] + queue[len - 1]);
}
return queue;
}
- Распечатайте треугольник Янхуэй
Анализ мыслей:
- Путем наблюдения обнаруживается, что каждая строка данных в треугольнике зависит от данных предыдущей строки;
- Сначала мы создаем очередь очереди для хранения данных каждой строки для использования следующей строкой данных;
- Затем инициализируйте данные 1 первой строки в очередь.Здесь для вложения необходимы два цикла for.Внешний цикл for определяет общее количество строк, которые нужно напечатать, а внутренний цикл for генерирует данные каждой строки;
- При создании данных текущей строки источники данных в очереди последовательно извлекаются из очереди, а затем вновь созданные данные помещаются в очередь, а данные, исключенные из очереди в данный момент, записываются для использования при создании новых данных.
function printYangHui(num) {
const queue = [];
// 存储第一行数据
queue.push(1);
for(let i = 1; i <= num; i++) {
let rowArr = [];
// 填充空格
for(let j = 0; j < Math.floor((num - i) / 2); j++) {
rowArr.push('');
}
let prev = 0;
for(let j = 0; j < i; j++) {
const num = queue.shift();
queue.push(prev + num);
rowArr.push(num);
prev = num;
}
queue.push(1);
console.log(rowArr.join(' '));
}
}
printYangHui(10);
использовать
- Реализовать луковую модель
Улучшите код, чтобы получить результат 1, 2, 3.
function createApp(){
return {
use(fn){},
run(){},
}
}
const app = createApp();
app.use((next)=>{
setTimeout(function(){
next();
})
console.log(new Date() ,'1');
})
app.use((next)=>{
console.log(new Date() ,'2');
next();
})
app.use((next)=>{
console.log(new Date() ,'3');
next();
})
app.run();
- очередь сообщений
связанный список
Несколько узлов связаны в связанный список, который называется связанной структурой хранения.
Разница между связанным списком и массивом
И связанные списки, и массивы могут хранить несколько данных, так в чем же разница между связанными списками и массивами?
Массивы требуют непрерывного пространства памяти для хранения данных, а требования к памяти относительно высоки. Связанный список, с другой стороны, не требует непрерывного пространства памяти. Связный список — это набор разрозненных блоков памяти, связанных между собой указателями.
По сравнению с массивом связанный список представляет собой несколько более сложную структуру данных. Ни хорошо, ни плохо, у каждого есть свои преимущества и недостатки.
Благодаря характеристикам хранения в памяти массивы могут обеспечивать быстрый поиск элементов, но при вставке и удалении необходимо перемещать большое количество элементов. Причина в том, что соседние элементы расположены в памяти рядом друг с другом, и между ними нет промежутка, поэтому элементы не могут быть быстро добавлены. При удалении останется пробел в пространстве памяти, который естественно нужно заполнить.
Классификация
- Односвязный список
- Двусвязный список
- односторонний круговой связанный список
- двусвязный список
выполнить
const Node = function (data) {
this.data = data;
this.next = null;
}
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
node1.next = node2;
node2.next = node3;
заявление
- круговой связанный список
Учитывая связанный список, как определить, есть ли цикл в связанном списке?
Анализ мыслей:
- Сначала создайте два указателя 1 и 2, указывающих на головной узел этого связанного списка. Затем запустите большой цикл в теле цикла, позвольте указателю 1 перемещаться вниз по одному узлу за раз, позвольте указателю 2 перемещаться вниз по двум узлам за раз, а затем сравните, совпадают ли узлы, на которые указывают два указателя. Если они совпадают, считается, что связанный список имеет цикл, а если отличается, продолжается следующий цикл.
- Например, в связанном списке A->B->C->D->B->C->D оба указателя изначально указывают на узел A и входят в первый раунд цикла, указатель 1 перемещается на узел B, и указатель 2 перемещается на C. Во втором раунде цикла указатель 1 перемещается к узлу C, а указатель 2 перемещается к узлу B. В третьем цикле указатель 1 перемещается к узлу D, а указатель 2 перемещается к узлу D. В это время два указателя указывают на один и тот же узел, и определяется, что связанный список имеет цикл.
- Предположим, что расстояние от головного узла связанного списка до точки входа равно D, а длина кольца связанного списка равна S. Тогда цикл будет выполняться S раз, что можно просто понять как O(N). Помимо двух указателей, дополнительное хранилище не используется, поэтому сложность пространства составляет O (1).
const Node = function (data) {
this.data = data;
this.next = null;
}
const nodeA = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const nodeD = new Node('D');
const nodeE = new Node('E');
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeC;
function isCircularLinkedList(head) {
if (head === null || head.next === null) {
return false;
}
let point1 = head;
let point2 = head;
do {
point1 = point1.next;
point2 = point2.next && point2.next.next;
} while(point1 && point2 && point1 !== point2);
if (point1 === point2) {
return true;
}
return false;
}
console.log(isCircularLinkedList(nodeA));
- Пересекающийся связанный список
Определить, пересекаются ли два односвязных списка, и найти первый узел пересечения.
Анализ мыслей:
- Если два связанных списка без кольца пересекаются в определенном узле, как показано на рисунке выше, этот узел позже разделяется. Таким образом, если два связанных списка пересекаются, адрес хвостового узла двух связанных списков также будет одинаковым. Когда программа реализована, она проходит два односвязных списка до конечного узла. Достаточно судить, равны ли адреса конечных узлов. Временная сложность O(L1+L2).
- Как найти первый узел пересечения? При оценке того, пересекается ли он, запишите длину двух связанных списков, вычислите разницу длин len, а затем дайте более длинному связанному списку пересечь длины len, а затем одновременно просмотрите два связанных списка, чтобы определить, равны ли они. если они равны, это узел первого пересечения.
function intersectNode(head1, head2) {
if (head1 && head2) {
// 计算链表的长度
let len1 = 0, p = head1;
let len2 = 0, q = head2;
while(p.next) {
len1++;
p = p.next;
}
while(q.next) {
len2++;
q = q.next;
}
if (p === q) {
// p指向短链，q指向长链
let len = 0;
if (len1 > len2) {
len = len1 - len2;
p = head2;
q = head1;
} else {
len = len2 - len1;
p = head1;
q = head2;
}
while(len > 0) {
len--;
q = q.next;
}
while(p && q && p !== q) {
p = p.next;
q = q.next;
}
return p;
}
}
return null;
}
const Node = function (data) {
this.data = data;
this.next = null;
}
const nodeA = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const node1 = new Node('1');
const node2 = new Node('2');
const node3 = new Node('3');
const nodeD4 = new Node('D4');
const nodeE5 = new Node('E5');
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD4;
node1.next = node2;
node2.next = node3;
node3.next = nodeD4;
nodeD4.next = nodeE5;
console.log(intersectNode(nodeA, node1));
- Палиндромный связанный список
Пожалуйста, определите, является ли связанный список палиндромным связанным списком.
Анализ мыслей:
- Пройдите по связанному списку с самого начала, объединяя данные каждого связанного списка в прямом и обратном направлениях одновременно, и, наконец, сравните, равны ли строки, полученные в прямом и обратном направлениях. Если равно, то это палиндром, иначе нет.
const Node = function (data) {
this.data = data;
this.next = null;
}
const node1 = new Node('A');
const node2 = new Node('B');
const node3 = new Node('C');
const node4 = new Node('C');
const node5 = new Node('B');
const node6 = new Node('A');
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
const isPalindrome = head => {
let a = '', b = '';
while(head !== null) {
a = a + head.data;
b = head.data + b;
head = head.next;
}
return a === b;
}
console.log(isPalindrome(node1));
использовать
- Сеть прототипов
- цепочка прицелов
Дерево
Дерево — это структура данных, которая состоит из n (n>=1) конечных узлов, образующих набор с иерархическими отношениями. Его называют «деревом», потому что оно выглядит как перевернутое дерево, что означает, что у него корни вверх, а листья вниз.
Классификация
- Неупорядоченное дерево: между дочерними узлами любого узла в дереве нет последовательной связи.Этот тип дерева называется неупорядоченным деревом, также известным как свободное дерево.
- Упорядоченное дерево: между дочерними узлами любого узла в дереве существует отношение порядка.Этот тип дерева называется упорядоченным деревом.
- Двоичное дерево: Дерево с не более чем двумя поддеревьями на узел называется бинарным деревом.
- Полное бинарное дерево: дерево, в котором все узлы, кроме листовых, содержат два поддерева, называется полным бинарным деревом.
- Полное двоичное дерево: за исключением последнего слоя, все слои заполнены узлами, а в последнем слое отсутствуют последовательные узлы в правой части двоичного дерева, что называется полным двоичным деревом (куча — это полное двоичное дерево).
- Дерево Хаффмана (оптимальное бинарное дерево): Бинарное дерево с кратчайшим взвешенным путем называется деревом Хаффмана или оптимальным бинарным деревом.
выполнить
// 二叉树的实现
function Node(data) {
this.data = data;
this.left = null;
this.right = null;
}
const nodeA = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const nodeD = new Node('D');
const nodeE = new Node('E');
const nodeF = new Node('F');
const nodeG = new Node('G');
nodeA.left = nodeB;
nodeA.right = nodeC;
nodeB.left = nodeD;
nodeB.right = nodeE;
nodeC.left = nodeF;
nodeC.right = nodeG;
То, с чем мы больше всего соприкасаемся в нашей повседневной работе, — это дерево с несколькими разветвлениями.
траверс
-
обход в глубину
- обход предварительного заказа
Обход в предварительном порядке (также известный как обход корня) — это ABDECFG (корень-слева-справа).
- Неупорядоченный обход
Обход по порядку (он же обход среднего корня) — это DBEAFCG (левый-коренной-правый) (только бинарные деревья имеют обход по порядку).
- пост-порядковый обход
Пост-порядковый обход (он же пост-корневой обход) — это DEBFGCA (левый-правый-корень).
-
обход в ширину
- обход по уровням
Обход по уровням ABCDEFG.
использовать
- Сведение дерева (показ результатов распознавания OCR)
- Свести массив в дерево (дерево меток)
картина
Структура графа (Graph) представляет собой нелинейную структуру данных.В реальной жизни существует множество примеров графов, таких как транспортные сети, сети метро и т. д., которые можно абстрагировать в графовые структуры. Структура графа — это нелинейная структура, более сложная, чем древовидная структура.
Граф состоит из нескольких вершин и ребер.
Классификация
- Неориентированный граф
Если все ребра в структуре графа не имеют направления, то граф называется неориентированным.
- ориентированный граф
В структуре графа ребра являются направленными, тогда такой граф называется ориентированным графом.
- взвешенный граф
Если вы добавите значение к ребру для представления веса, такой график будет взвешенным.
- связный граф
Граф называется связным графом, если любые два узла в графе могут найти путь, соединяющий их.
выражать
Существует два способа представления графов: матрица смежности и связанный список смежности. Различные сценарии и алгоритмы могут требовать различных представлений графа.Как правило, когда количество узлов очень велико, матрица будет очень разреженной, а накладные расходы на пространство будут большими.В этом случае представление с использованием списка смежности будет занимать меньше места. . . . Если это плотная матрица или нужно быстро определить, соединены ли любые два узла ребрами и т. д., матрица смежности может быть более подходящей.
- матрица смежности
- список смежности
траверс
- обход в глубину
- обход в ширину
использовать
- Выбор категории продукта
алгоритм
LRU
LRU — это аббревиатура наименее недавно использованного, то есть наименее недавно использовавшегося, является общеупотребительным.алгоритм замены страницы, чтобы отсеять последние неиспользованные страницы.
Основная идея заключается в том, что «если к данным обращались недавно, вероятность доступа к ним в будущем будет выше».
принцип
выполнить
Анализ мыслей:
-
Выберите подходящую структуру данных.
- Хэш-таблица: временная сложность уровня O(1), подходящая для поиска данных. Однако элементы расположены не по порядку, и невозможно определить порядок доступа к элементам.
- Массивы: вставка и удаление элементов выполняются за O(n).
- Односвязный список: для удаления узла требуется посещение предшествующего узла, а для обхода предыдущего узла требуется O(n).
- Двусвязный список: узлы имеют указатели предшественников, а удаление и перемещение узлов являются изменениями указателя, оба из которых являются O (1).
Вывод: хэш-таблица + двусвязный список.
Целью использования хеш-таблицы является быстрый доступ к данным, хранящимся в двусвязном списке, и хранение ключа двусвязного списка и ссылки узла; цель использования двусвязного списка — быстрое перемещение и удалить позицию узла и сохранить ключ и соответствующие данные.
-
Настройте виртуальные узлы, чтобы облегчить и быстро получить доступ к головным и хвостовым узлам. Изначально никакие реальные узлы не добавляются, поэтому вам нужно указать указатель предшественника и указатель преемника виртуального узла на себя.
-
Реализация метода get.
-
Реализация метода put.
- Для записи новых данных необходимо сначала проверить текущее количество узлов; если количество узлов достигает максимальной емкости, необходимо сначала удалить узел в конце связанного списка, затем создать новый узел, добавить его в заголовок связанного списка и записать его в хеш-таблицу.
- Запишите существующие данные, обновите значение данных и переместите позицию узла в начало связанного списка.
function Node(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity; // 容量
this.hash = {}; // 哈希表
this.count = 0; // 当前节点数量
this.virtualNode = new Node(); // 虚拟结点
// 相互引用
this.virtualNode.next = this.virtualNode;
this.virtualNode.prev = this.virtualNode;
}
get(key) {
const node = this.hash[key];
if (node) {
this.moveToHead(node);
return node.value;
}
}
put(key, value) {
const node = this.hash[key];
if (node) {
node.value = value;
this.moveToHead(node);
} else {
if (this.count === this.capacity) {
this.removeLRUItem();
}
const newNode = new Node(key, value);
this.hash[key] = newNode;
this.addToHead(newNode);
this.count++;
}
}
remove(key) {
const node = this.hash[key];
if (node) {
this.removeFromList(node);
Reflect.deleteProperty(this.hash, key);
this.count--;
}
}
isEmpty() {
return this.count === 0;
}
moveToHead(node) {
this.removeFromList(node);
this.addToHead(node);
}
removeFromList(node) {
const prevNode = node.prev;
const nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
node.prev = null;
node.next = null;
}
addToHead(node) {
const nextNode = this.virtualNode.next;
this.virtualNode.next = node;
nextNode.prev = node;
node.prev = this.virtualNode;
node.next = nextNode;
}
removeLRUItem() {
const tailNode = this.virtualNode.prev;
this.remove(tailNode.key);
}
}
const cache = new LRUCache(5);
console.log(cache.isEmpty());
cache.put('A', 'A');
cache.put('B', 'B');
cache.put('C', 'C');
cache.put('D', 'D');
cache.put('E', 'E');
console.log(cache.get('A'));
cache.put('F', 'F');
console.log(cache.get('B'));
console.log(cache.isEmpty());
cache.remove('E');
cache.remove('F');
cache.remove('A');
cache.remove('C');
cache.remove('D');
console.log(cache.isEmpty());
console.log(cache);
использовать
- История просмотров.
- Стратегия уничтожения кеша.
❤️ Спасибо за поддержку
Выше приведено все содержание этого обмена, я надеюсь, что это поможет вам ^_^
Не забудьте, если вам нравитсяПоделиться, Нравится, ИзбранноеТри последовательных о~.
Добро пожаловать в публичный аккаунтКоманда ELabХорошая статья от принимающей фабрики~
Мы из ByteDance, который является передовым отделом энергичного образования и отвечает за предварительную разработку всех продуктов ByteDance Education.
Мы накапливаем и распространяем профессиональные знания и кейсы в направлении улучшения качества продукции, эффективности разработки, творчества и передовых технологий, а также вносим ценный опыт в отрасль. Включая, помимо прочего, мониторинг производительности, библиотеки компонентов, многотерминальные технологии, бессерверные решения, визуальное построение, аудио и видео, искусственный интеллект, дизайн и маркетинг продуктов и т. д.
Заинтересованные студенты могут отправить сообщение в отдел авторов в области комментариев или использовать внутренний push-код, чтобы сделать кирпич 🤪
Ссылка на доставку школы ByteDance / социального рекрутинга:job.toutiao.com/s/eGrF9qQ