Статья впервые опубликована на:GitHub.com/US TB-Вуд, умри, о ты…
написать впереди
Сегодня поговорим о двух самых основных структурах данных для фронтенд-интервью — «массиве» и «связном списке».
Вот некоторые распространенные вопросы на собеседовании:
- Поговорим о разнице между связанным списком и массивом
- Как перевернуть односвязный список
- Найдите в массиве три числа, сумма которых равна N
- Учитывая связанный список, как удалить n-й узел из нижней части связанного списка
Вы можете сначала подумать, как ответить на вопрос выше 🤔, а затем прочитать следующий контент с ответом.
1. Разница между связанным списком и массивом
Прежде чем говорить об этой проблеме, давайте взглянем на классификацию данных по логической структуре. Есть две основные категории: линейные таблицы и нелинейные таблицы.
Линейная таблица:Данные связаны в линейную структуру, к этой категории относятся связный список и массив, о которых мы сегодня поговорим, кроме того, есть стеки, очереди и т. д.
Нелинейная таблица:Связь между данными нелинейна, например, дерево, куча, граф и т. д.
После прочтения линейной таблицы и нелинейной таблицы давайте продолжим рассмотрение:
определение массива: данные — это линейная табличная структура данных, в которой используется наборнепрерывное пространство памяти, для хранения наборатот же тип данных.
Поскольку массив хранится в памяти непрерывно, очень эффективно осуществлять произвольный доступ к элементам массива с помощью индексации. Но в то же время, чтобы обеспечить непрерывность, если вы хотите добавить элемент в массив, вам нужно переместить много данных. То же самое верно для удаления элемента из массива. Таким образом, мы приходим к выводу: произвольный доступ в массиве эффективен, но неэффективен при выполнении добавлений и удалений со средней временной сложностью O(n).
Определение связанного списка:Это непоследовательная и непоследовательная структура хранения на физической единице хранения.Логический порядок элементов данных реализуется через порядок ссылок указателей в связанном списке.
Только что было описано, что добавление и удаление элемента из массива неэффективно. Пространство хранения связанного списка является прерывистым.Используя связанный список для добавления или удаления фрагмента данных, нам не нужно перемещать данные, чтобы поддерживать непрерывность памяти, поэтому добавление и удаление элементов в связанном списке очень эффективно. Но у всего есть две стороны.То, что место для хранения связанного списка прерывисто, когда вы хотите получить доступ к элементу в связанном списке, вы не можете вычислить соответствующий узел через формулу адресации на основе первого адреса и индекса как массив . И только через указатель для обхода найти соответствующий узел. Таким образом, мы приходим к выводу: добавление и удаление операций в связанном списке очень эффективно, а случайный доступ очень неэффективен со средней временной сложностью O(n).
Благодаря введению предыдущего контента таблица используется для визуального наблюдения разницы во временной сложности между ними:
| временная сложность | множество | связанный список |
|---|---|---|
| Добавить к | O(n) | O(1) |
| удалять | O(n) | O(1) |
| произвольный доступ | O(1) | O(n) |
Итак, чтобы ответить на разницу между связанным списком и массивом:
1. Различные способы организации памяти
2. Добавить, удалить, вставить разные временные сложности
3. Связанный список поддерживает динамическое расширение
2. Как обратить односвязный список
Пример:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
Установите три переменные для представления текущего узла и узлов до и после текущего узла соответственно, и их можно будет перевернуть.
var reverseList = function(head) {
let pre = null;
for (let cur = head; cur;) {
let nextTemp = cur.next; // 保存当前头节点的下一个节点
cur.next = pre;
pre = cur;
cur = nextTemp;
}
return pre;
};
3. Найдите в массиве три числа, сумма которых равна N
Дан массив nums, содержащий n целых чисел. Определите, существуют ли в nums три элемента a, b, c, такие что a + b + c = 0? Найдите все тройки, удовлетворяющие условию и не повторяющиеся.
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
1. Отсортировать массив: если первый элемент массива больше 0 или последний элемент меньше 0, сумма не может быть равна 0;
2. Сначала выберите элемент (A), затем используйте двойные указатели для обхода элементов массива, укажите один указатель на следующий элемент (B) элемента A, а другой указатель на последний элемент массива (C) ;
3. Определить, является ли результат B+C противоположным результату A. Если B+C > (-A), переместите указатель C вперед, а если B+C
4. Если элемент указателя B равен своему предыдущему элементу, указатель B перемещается на один бит назад, если указатель C равен своему предыдущему элементу, указатель C перемещается на один бит вперед;
5. Повторите вышеуказанные шаги
Код реализации выглядит следующим образом:
var threeSum = function(nums) {
//用来存取最后结果集
let result = new Array();
//头指针
let head;
//尾指针
let end;
//固定值
let fixedVal;
//排序
nums.sort((a, b) => {
return a-b;
});
//判断数组内元素是否都为整数或负数，直接返回
if(nums[0] > 0 || nums[nums.length - 1] < 0) return result;
// 开始遍历
for (let i = 0; i < nums.length; i++) {
//固定值
fixedVal = nums[i];
// 如果前后元素相同，跳过此次循环（固定值）
if(fixedVal === nums[i-1]) continue;
//一开始的固定值为nums[0],所以头指针为 i+1 下一个元素
head = i+1;
//尾指针
end = nums.length - 1;
//如果头指针小于尾指针元素
while(head < end){
//判断固定值+头指针+尾指针是否等于0
if(nums[head] + nums[end] + fixedVal === 0){
//声明数组，存放这三个值
let group = new Array();
group.push(nums[head]);
group.push(nums[end]);
group.push(fixedVal);
result.push(group);
//存放完毕之后，不要忘记头指针和尾指针的移动(否则会产生死循环)
head += 1;
end -= 1;
//如果头指针满足小于尾指针且移动后的指针和移动前的指针元素相等，再往前移动
while(head < end && nums[head] === nums[head - 1]){
head += 1;
}
//如果头指针满足小于尾指针且移动后的指针和移动前的指针元素相等，再往后移动
while(head < end && nums[end] === nums[end + 1]){
end -= 1;
}
//小于 0 需要移动头指针，因为尝试着让数据比原有数据大一点
}else if(nums[head] + nums[end] + fixedVal < 0){
head++;
}else{
//否则，尾指针向前移动，让数据小于元数据
end--;
}
}
}
return result;
};
4. Учитывая связанный список, как удалить n-й узел из нижней части связанного списка
Учитывая связанный список, удалите n-й узел снизу связанного списка и верните головной узел связанного списка. Пример:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
Мы можем использовать два указателя вместо одного. Первый указатель перемещается вперед на n+1 шагов от начала списка, а второй указатель начинается с начала списка. Теперь два указателя разделены n узлами. Мы поддерживаем этот постоянный интервал, одновременно перемещая оба указателя вперед, пока первый указатель не достигнет последнего узла. В этот момент второй указатель будет указывать на n-й узел от последнего узла. Мы повторно связываем следующий указатель узла, на который ссылается второй указатель, чтобы он указывал на следующий следующий узел этого узла.
var removeNthFromEnd = function(head, n) {
let first = head; // 慢指针
for (let i = 0; i < n; i++) {
first = first.next;
}
if (!first) return head.next; // 当链表长度为n时，删除第一个节点
let second = head; // 快指针
while (first.next) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return head;
};
использованная литература
Можете обратить внимание на мой паблик-аккаунт «Muchen Classmate», фермера на гусиной фабрике, который обычно записывает какие-то банальные мелочи, технологии, жизнь, инсайты и срастается.