предисловие
В последнее время я также пишу вопросы по алгоритмам.Я начал сомневаться в жизни и почувствовал, что я "еда".Позже я постепенно нашел чувство написания алгоритмов, и тогда я очень заинтересовался алгоритмами. На самом деле, сначала было очень больно делать алгоритм, и разочарование меня очень расстроило, но после последних двух недель я чувствую, что алгоритм не так страшен, как я себе представлял, потому что нам не нужно создайте алгоритм, нам нужно только освоить решение проблем. Идеи и методы можно освоить путем целенаправленного обучения.
Здесь я предлагаю всем, если вы хотите чистить вопросы по алгоритму, не начинайте чистить сразу со списка LeetCode, потому что вопросов по алгоритму слишком много и невозможно их все почистить, поэтому я предлагаю вам начать чистить со списка. определенный тип типа вопроса. Я рекомендую начать со связанного списка или дерева, здесь я привожу свои причины:
Во-первых, существует слишком много типов алгоритмических вопросов, таких как массивы, и существует множество форм исследования типов вопросов. Легко сдаться, если вы не видите своего прогресса в течение короткого времени. связанные списки. Форм не так много, и их относительно легко освоить. За короткий промежуток времени вы можете повысить свою уверенность в решении алгоритмических задач.
Во-вторых, как и в некоторых задачах односвязного списка, в ней используется много указателей, например, нам сложнее решать алгоритмические задачи, некоторое использование указателей. Хотя некоторые алгоритмические задачи могут быть решены с помощью классов инструментов, предоставляемых некоторыми языками, дополнительное пространство памяти будет использоваться дополнительно.Возможно, некоторые алгоритмические задачи требуют использования пространственной сложности O(1).В этом случае вы должны использовать указатель для сделай это.
В-третьих, когда вы закончите задачу односвязного списка, у вас возникнет определенное представление об использовании указателей, что впоследствии очень поможет при решении некоторых алгоритмических задач.
Поэтому я предлагаю, если вы начнете чистить вопросы, рекомендуется начать с заголовка связанного списка.
1. Необходимо оперировать обратным значением указанного узла в односвязном списке.
1.1 Идеи решения проблем и шаблоны кода
Такая тема алгоритма, ядро является ключом к расположению конкретных потребностей данного заголовка узла, просто найдите указанную позицию узла, и остальные проблемы будут решены. Мои вопросы перечислены ниже алгоритмов на несколько LeetCode, мы чувствуем это вместе.
- Возвращает CountDown Coins Node связанного списка
- Удалить N-й узел снизу связанного списка
- вращающийся связанный список
Мы решаем такого рода задачи, и идеи в основном те же.Мы можем обобщить эту аналогичную задачу в виде шаблона: такого рода задачи часто используют быстрый и медленный указатель для решения задачи, а быстрый и медленный указатель используются для решения задачи. найдите узел, который мы хотим оперировать, найдите соответствующую позицию и выполните над ней соответствующие операции в соответствии с темой. Здесь я просто сделал движущуюся картинку, сначала позволил быстрому указателю пройти k шагов, а затем позволил быстрому и медленному указателям двигаться назад вместе, и я нашел предпоследний узел связанного списка.
Код его шаблона выглядит следующим образом:
public static ListNode method(ListNode head, int k) {
//快指针，我们先让它走k步，
ListNode fast = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
//然后将快的指针和慢的指针一起走，当快指针走到链表末尾，慢指针指向的就是倒数第K个节点
ListNode temp = head;
//你要找的倒数第k个节点的前一个节点。因为如果你要操作第k个节点，一般需要找到第K个节点的前前驱节点
//像上面第2道的算法题，删除链表的第K个节点就需要用到preNode
ListNode preNode = null;
while (fast != null ) {
preNode = temp;
temp = temp.next;
fast = fast.next;
}
return temp;
}
Первая проблема алгоритма, мы можем использовать приведенный выше код шаблона, чтобы решить ее.
Во втором вопросе алгоритма нам нужно удалить k-й узел снизу. Мы по-прежнему используем приведенный выше шаблон кода, чтобы найти его. Однако, чтобы работать с k-м узлом снизу, мы должны сначала найти предыдущий узел этого узла. ,
Третий вопрос алгоритма - это умеренно сложный вопрос на летекоде. Идея такая же, как и предыдущие два алгоритма вопросов. Я не буду копировать оригинальный вопрос здесь. Вышеуказанная ссылка может быть перенесена напрямую. К теме. Смысл вопроса: учитывая связанный список, поверните связанный список и переместите каждый узел связанного списка вправоkместа, из которыхkявляется неотрицательным числом.
В этой задаче нет предела тому, что длина вращения не может превышать длину связанного списка, поэтому длина вращения может превышать длину связанного списка, поэтому основная идея этой задачи алгоритма состоит в том, чтобы найти узел что нужно повернуть:
- Вычислить длину связанного списка
- Чтобы определить длину вращения, используйте k % длины здесь;
- Используйте метод, который мы сказали выше, чтобы найти узел, который нужно повернуть.
- получить желаемый результат.
Его полный код выглядит следующим образом:
public ListNode rotateRight(ListNode head, int k) {
if(head ==null||head.next ==null){
return head;
}
//先拿到链表的长度。
int nodeLength = 0;
ListNode d = head;
while (d != null) {
nodeLength++;
d = d.next;
}
//拿到长度以后,计算需要移动几个节点。
int remaind =k % nodeLength ;
//如果mid等于0，相当于没有移动。
if (mid == 0) {
return head;
}
d = head;
//这里就是我们上面所说的快慢指针，先让快的指针走remaind
for (int i = 0; i < remaind; i++) {
d = d.next;
}
ListNode temp = head;
//记录慢指针指向的前一个节点
ListNode prev = null;
//记录快指针指向的前一个节点
ListNode tailPrev = null;
while (d != null) {
prev = temp;
tailPrev = d;
temp = temp.next;
d = d.next;
}
prev.next = null;
tailPrev.next = head;
return temp;
}
В дополнение к этому типу необходимости найти k-й узел снизу, на самом деле есть еще один тип узла, который необходимо найти.Этот узел является специальным промежуточным узлом, поэтому нам также нужно использовать указатель скорости для решения похожие проблемы.Давайте пусть Быстрый указатель делает два шага за раз, и мы позволяем медленному указателю делать один шаг за раз, так что, когда быстрый указатель достигает конца связанного списка, медленный указатель указывает на средний узел связанного списка.
public static ListNode findMidNode(ListNode head) {
ListNode fastNode = head;
ListNode slowNode = head;
ListNode prev = null;
while (fastNode != null && fastNode.next != null) {
prev = slowNode;
fastNode = fastNode.next.next;
slowNode = slowNode.next;
}
return slowNode;
}
1.2 Вопросы для упражнений
Прочитав вышеизложенное, возьмите этот вопрос на практику, исходный вопрос здесь:Переупорядочить связанный список.
Учитывая односвязный список L: L0→L1→…→L**n-1→Ln, вы не можете просто изменить значение внутри узла, вам нужно фактически обменять узел. Пример 1: Дан связанный список 1->2->3->4, изменить порядок на 1->4->2->3 Пример 2: Дан связанный список 1->2->3->4-> 5 , переставлено на 1->5->2->4->3
Прежде всего, позвольте мне рассказать о моих идеях. На самом деле, когда мы увидим этот вопрос, мы обнаружим, что этот вопрос основан на средней точке связанного списка. Связанный список разделен на две части. После второй половины связанный список перевернут, вставьте их по одному в связанный список в первой половине. В этом случае вы можете использовать шаблон, который мы упоминали выше, чтобы получить связанный список из двух частей.После получения связанного списка из двух частей вы можете объединить две части связанного списка. Как перевернуть связанный список во второй половине здесь тоже можно применить шаблон.
На самом деле есть две идеи для переворачивания связанного списка.Один находится в исходном связанном списке, а другой использует структуру данных стека.Когда пространственная сложность O(1), мы не можем использовать дополнительные структуры данных, только указатели. чтобы перевернуть список операций.
public static ListNode reverseList(ListNode head) {
ListNode curr = head, prev = null;
ListNode temp;
while (curr != null) {
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
Другой способ — использовать для этого стек.Метод записи относительно прост.Вы можете написать его здесь. Ниже приведен полный код для изменения связанного списка.
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return;
}
//找到链表的中间节点位置
ListNode fast = head;
ListNode slow = head;
ListNode prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
//这里就改变了原链表 head，head是前半部分链表
prev.next = null;
//slow 就是后半部分的链表，这里将后半部分链表反转。这里可以利用栈。
ListNode listNode = reverseList(slow);
//这里就将两个链表合并成一个，这里你可以新建一个链表去做，也可以直接在head的上操作。但是我测试性能的效果没差，
//在head上操作可能会稍微复杂一些，需要你用好几个指针来做，不熟练的可以直接新建一个链表，因为指针指来指去的容易把自己弄迷了。
//利用栈也是可以实现的，这里自己可以试一下。
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
while(head != null && listNode != null){
curr.next = head;
head = head.next;
curr.next.next = listNode;
listNode = listNode.next;
curr = curr.next.next;
}
//这里需要注意的是判断后半部分的链表是否为空，可以知道链表是奇数节点还是偶数节点。
//如果是奇数节点的话，链表的后半部分会比前半部分多一个节点，因为我们把中间的那个节点算到的后半部分里面。
if(listNode != null){
curr.next = listNode;
}
head = dummy.next;
}
public static ListNode reverseList(ListNode head) {
ListNode curr = head, prev = null;
ListNode temp;
while (curr != null) {
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
2. Алгоритм типа палиндромного связанного списка и кольцевого связанного списка
Темы палиндромных связанных списков и круговых связанных списков относительно просты. Оценка связанного списка-палиндрома такая же, как и в первом разделе.Используйте быстрый и медленный указатель, чтобы найти положение средней точки, а затем сравните, находятся ли вторая половина и первая половина в обратном порядке. Здесь мы сосредоточимся на идеях решения проблем кругового связанного списка.
2.1 Идеи решения проблем и шаблоны кода
Оригинальное название на LeetCode:Проверить, является ли связанный список круговым связанным списком
Первая идея, мы можем использовать хеш-таблицу, мы обходим весь связанный список, если есть цикл, обязательно будет ситуация, когда узел посещается дважды.
public static boolean hasCycle2(ListNode head) {
HashSet set = new HashSet();
while (head != null) {
if (set.contains(head)) {
return true;
} else {
set.add(head);
}
head = head.next;
}
return false;
}
Используя решение хеш-таблицы, временная сложность составляет O (n), а пространственная сложность также составляет O (n). Этот метод является самым простым и легким для придумывания.
Вторая идея заключается в использовании быстрых и медленных указателей. Мы делаем быстрый указатель в два раза быстрее, чем медленный указатель, чтобы мы могли пройти весь связанный список. Если в односвязном списке есть цикл, то два указателя обязательно встретится в определенном узле. код показывает, как показано ниже:
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
if (head == null || head.next == null) {
return false;
}
return false;
}
Расширенные вопросы для круговых связанных списков:Возвращает первый узел связанного списка в кольцо или NULL, если нет кольца
Если в односвязном списке есть кольцо, то два указателя обязательно встретятся в определенном узле кольца. Когда два указателя встречаются, медленный указательlen + s1длина;len+n(s1+s2)+s1это длина , потому что быстрый указатель продолжает циклически перемещаться по кольцуn(s1+s2). Поскольку быстрый указатель в два раза быстрее медленного, расстояния, пройденные за одно и то же время, должны быть равны, поэтому можно вывести формулу:2(len+S1) = len + n(S1+S2)+S1, после упрощения получаем формулуlen = (n-1)S1 + nS2. n означает, что когда быстрый указатель и медленный указатель встречаются, быстрый указатель делает несколько оборотов по кольцу. Это уравнение устанавливается всегда, вы можете привести его в тест самостоятельно. Когда мы игнорируем переменную n и принимаем n = 1, формула принимает вид len = s2. Затем, после того, как два указателя встретятся, пусть два указателя начинаются с узлов A и C одновременно, перемещаются по одному узлу за раз, и когда они снова встретятся, это будет входной узел кольцевого связанного списка. код показывает, как показано ниже:
public ListNode hasCycle(ListNode head) {
ListNode slow = head,fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
if (fast == null || fast.next == null) return null;
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
3. Сортировка списка и список слияния
Тема алгоритма:
- Сортировка списка
- Объединить два отсортированных связанных списка
- Объединить K отсортированных связанных списков
3.1 Идеи решения проблем
Первая проблема алгоритма, сортировка связанного списка и обычная сортировка данных - это одни и те же идеи решения проблемы, потому что связанный список не может случайным образом обращаться к узлам в связанном списке, мы можем только пройти весь связанный список, здесь мы можем использовать слияние sort для сортировки связанного списка, я полагаю, что все уже знакомы с сортировкой слиянием, поэтому давайте перейдем непосредственно к коду.
Чтобы объединить и отсортировать связанный список, нам сначала нужно найти среднюю точку связанного списка, разделить связанный список на две части и отсортировать две части связанного списка. Затем повторите предыдущие действия для двух частей связанного списка до конца.
public static ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
return merge(left, right) ;
}
//合并左右两部分
private static ListNode merge(ListNode l1, ListNode l2) {
ListNode temp1 = l1, temp2 = l2;
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
while (temp1 != null && temp2 != null) {
if (temp1.val > temp2.val) {
dummy.next = temp2;
temp2 = temp2.next;
} else {
dummy.next = temp1;
temp1 = temp1.next;
}
dummy = dummy.next;
}
dummy.next = temp1 != null ? temp1 : temp2;
return prev.next;
}
Фактически, объединение двух упорядоченных связанных списков является частью нашей первой проблемы алгоритма. Код для объединения двух упорядоченных связанных списков может быть непосредственно используется в последней части первой проблемы алгоритма. Здесь следует отметить, что этот метод можно использовать только для объединения двух упорядоченных связанных списков
Как насчет слияния K упорядоченных связанных списков, как в третьей проблеме алгоритма? На самом деле способов много, например:
1. Использовать приоритетную очередь PriorityQueue в Java для реализации, потому что нижний уровень PriorityQueue реализован с использованием бинарной кучи, а наименьший элемент всегда находится вверху кучи, так что мы можем объединять несколько упорядоченных списков. Однако здесь следует отметить, что мы можем сделать это только в том случае, если несколько связанных списков упорядочены, а при объединении нескольких неупорядоченных связанных списков мы не можем этого сделать.
2. Мы все еще можем продолжать использовать идею нашего второго вопроса.Независимо от того, сколько связанных списков объединено, мы можем объединить их по два и, наконец, объединить их в один связанный список.Это решение заключается в том, является ли связанный список упорядочена или неупорядочена, мы все можем сделать это.
- приоритетная очередь
public static ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> pq = new PriorityQueue<>((v1,v2)->v1.val - v2.val);
for (ListNode node : lists) {
if (node != null) {
pq.offer(node);
}
}
ListNode dummyHead = new ListNode(-1);
ListNode tail = dummyHead;
while (!pq.isEmpty()) {
ListNode minNode = pq.poll();
tail.next = minNode;
tail = minNode;
if (minNode.next != null) {
pq.offer(minNode.next);
}
}
return dummyHead.next;
}
- Слияние два на два
public static ListNode mergeKLists2(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return helper(lists, 0, lists.length - 1);
}
private static ListNode helper(ListNode[] lists, int begin, int end) {
if(begin==end) {
return lists[begin];
}
int mid = begin+(end-begin)/2;
ListNode left = helper(lists,begin,mid);
ListNode right = helper(lists,mid+1,end);
return merge(left,right);
}
//合并两个有序链表
private static ListNode merge(ListNode l1, ListNode l2) {
ListNode temp1 = l1, temp2 = l2;
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
while (temp1 != null && temp2 != null) {
if (temp1.val > temp2.val) {
dummy.next = temp2;
temp2 = temp2.next;
} else {
dummy.next = temp1;
temp1 = temp1.next;
}
dummy = dummy.next;
}
dummy.next = temp1 != null ? temp1 : temp2;
return prev.next;
}
4. Проблема типа обмена связанными списками
- Переверните связанный список на указанном положении узла
- Попарно поменять местами узлы в связанном списке
- Набор из K перевернутых связанных списков
Не существует определенного шаблона, который можно было бы применить к этому типу задач, единственное, что вам нужно сделать, это уловить ощущение решения такого рода проблем. Хотя нет фиксированного шаблона, который можно применить, все же есть ключевые точки, которые можно нарисовать. Шаг 1: Нам нужно выяснить, когда нам нужно поменять местами два узла. Возьмем в качестве примера первую проблему алгоритма выше, узлы, которые необходимо обменять, — это узлы с третьего по пятый. Шаг 2: Затем найдите узлы-предшественники и узлы-преемники, которые необходимо поменять местами. Это позволит вам успешно переместить узел. Шаг 3: На этом шаге вам нужно определить, как перемещать указатель, что может удовлетворить ваши последующие действия цикла.
Давайте возьмем в качестве примера первую задачу алгоритма, для удобства понимания вы можете обратиться к анимации выше, и давайте посмотрим на время решения задачи в соответствии с тем, что мы сказали выше.
Шаг 1: По смыслу вопроса находим позицию узла, который нужно обменять. В этом разделе приведены узлы, которыми необходимо обменяться между k -> n, и узлы вне, которые не нужно перемещать. Итак, здесь нам нужно решить, является ли длина связного списка, который мы проходим, узлом между k - n.
Шаг 2: Найдите передний план и последующие узлы, которые необходимо обменять узлы. Здесь я проходил список 3-5. Поскольку он уже определил местонахождение узла, которое необходимо изменить, то найдите передний привод и последующий узел, который необходимо изменить узел, используя два указателяpreNodeа такжеnextNodeСохраните узлы-предшественники и узлы-преемники. Затем поменяйте связанный список там, где мы хотим.
Часть 3: После того, как мы завершили обмен узлами, нам также нужно соответствующим образом переместить указатели, которые нам нужно использовать.
Полный код выглядит следующим образом:
public static ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
int length = 0;
ListNode temp;
while (head.next != null) {
length++;
//找到需要交换节点的条件
if (length >= m && length < n) {
//保存head 的后继节点
temp = head.next;
//head.next 指向后继节的后继节点
head.next = temp.next;
temp.next = prev.next;
prev.next = temp;
} else {
if (length < m) {
prev = prev.next;
}
head = head.next;
}
}
return dummy.next;
}
Второй вопрос алгоритма — обмен связанными списками парами, вопросы на самом деле очень простые, главное здесь — контролировать позицию, на которую указывает указатель.
Третий вопрос об алгоритме — это сложный вопрос об алгоритме на LeetCode, На самом деле, мы отбросим сложность вопроса и разберем его, чтобы обнаружить, что он на самом деле очень прост. Требованием заголовка является набор из K перевернутых связанных списков, причем K меньше длины связанного списка. На самом деле, K перевернутых связанных списков на самом деле ничем не отличаются от переворачивания одного связанного списка, за исключением того, что нам нужно разделить K связанных списков на группу для переворачивания, а затем соединить каждый перевернутый связанный список вместе.
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
while (end.next != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) {
break;
}
ListNode start = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
pre = start;
end = start;
}
return dummy.next;
}
public static ListNode reverse(ListNode head) {
ListNode curr = head, prev = null;
ListNode temp;
while (curr != null) {
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
Я не буду здесь перечислять все типы по порядку.Большинство тем алгоритма похожи.Я грубо разделю их на: работа заданного узла связанного списка, сортировка связанного списка, круговой связанный список, обмен узла связанного списка, поиск и удаление связанного списка, инверсия связанного списка и другие типы, идея одна и та же, но все же нужно много практики, мышление и умение писать - совершенно разные вещи.
наконец
Я не буду здесь перечислять все типы по порядку.Большинство тем алгоритма похожи.Я грубо разделю их на: работа заданного узла связанного списка, сортировка связанного списка, круговой связанный список, обмен узла связанного списка, поиск и удаление связанного списка, инверсия связанного списка и другие типы, идея одна и та же, но все же нужно много практики, мышление и умение писать - совершенно разные вещи.