Condivisione della tecnologia

Domande selezionate sul test della superficie Niukeliana e Likou

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

💎 欢迎各位大佬互三：la mia home page

1. Elenco collegato inverso

206. Elenco concatenato inverso

Riflessione: se non si libera spazio aggiuntivo e si modifica solo l'elenco collegato originale, quale metodo dovrebbe essere utilizzato?

Basta partire dal secondo elemento ed eseguire in sequenza l'inserimento della testa.

Quindi modifica semplicemente il riferimento e punta l'ultimo elemento su null

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         //head为null，直接返回
  4.         if(head == null){
  5.             return head;
  6.         }
  7.  
  8.         ListNode cur = head.next;
  9.         //head变为了末尾元素，指向null
  10.         head.next = null;
  11.         while(cur!=null){
  12.             //curn为cur的next节点，便于往后移动
  13.             ListNode curn = cur.next;    
  14.             cur.next = head;
  15.             head = cur;
  16.             //更新cur
  17.             cur = curn;
  18.         }
  19.         return head;
  20.     }
  21. }

2. Il nodo centrale dell'elenco collegato

876. Nodo intermedio di lista concatenata

Il primo metodo che mi viene in mente per questa domanda è sicuramente quello di definire un cnt, attraversare una volta l'elenco collegato, quindi trovare il numero centrale e quindi attraversare il valore restituito. Questo metodo è molto semplice, ma cosa succede se è necessario attraversare il elenco collegato solo una volta per trovare il nodo intermedio?

Ecco una nuova idea: usa i puntatori veloci e lenti, partendo da head. Il puntatore veloce si sposta di due nodi ogni volta e il puntatore lento si sposta di un nodo ogni volta. Questo raggiunge l'obiettivo finale?

Quindi implementiamolo:

  1. class Solution {
  2.     public ListNode middleNode(ListNode head) {
  3.         if(head == null){
  4.             return null;
  5.         }
  6.         ListNode fast = head;
  7.         ListNode slow = head;
  8.         while(fast!= null&&fast.next!= null){
  9.             fast = fast.next.next;
  10.             slow = slow.next;
  11.         }
  12.         return slow;
  13.     }
  14. }

Sarebbe più efficiente?

3. Restituisce il k-esimo nodo dall'ultimo

Domanda dell'intervista 02.02. Restituisce il k-esimo nodo dall'ultimo

La prima cosa che mi viene in mente per questa domanda è attraversarlo una volta per ottenere la lunghezza totale, quindi trovare il k-esimo nodo dall'ultimo. Tuttavia, sulla base della domanda precedente, puoi pensare a un altro metodo: Allo stesso modo,Utilizzando i puntatori veloce e lento, lascia andare prima i nodi fast k-1, quindi vai lento e veloce allo stesso tempo. Quando il successivo di fast è nullo, significa che fast ha raggiunto l'ultimo nodo e slow in questo momento è il k-esimo nodo dal basso.

Questa domanda indica che l'input k è legale, quindi non è necessario alcun giudizio aggiuntivo. Come giudicare se k è illegale ed è necessario che la lunghezza dell'elenco collegato non possa essere trovata direttamente, quindi è necessario giudicare lentamente mentre si cammina.

  1. class Solution {
  2.     public int kthToLast(ListNode head, int k) {
  3.         if (head == null) {
  4.             return -1;
  5.         }
  6.         ListNode fast = head;
  7.         ListNode slow = head;
  8.         int cnt = 0;
  9.         while (cnt != k - 1) {
  10.             //判断k的合法性，虽然本题不用判断
  11.             fast = fast.next;
  12.             if(fast == null){
  13.                 return;
  14.             }
  15.             cnt++;
  16.         }
  17.         //slow和fast同时移动
  18.  
  19.         while (fast.next != null) {
  20.             fast = fast.next;
  21.             slow = slow.next;
  22.         }
  23.         return slow.val;
  24.     }
  25. }

4. Unisci elenchi collegati

21. Unisci due elenchi collegati ordinati

Idea:Devi solo definire un nuovo nodo newH, quindi confrontare il val di headA e headB. Per trovare finalmente il nodo head dell'elenco collegato unito, devi anche definire un tmp = newH, e quindi chi ha il più piccolo. tmp.next lo indicherà.

  1. class Solution {
  2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  3.         ListNode head = new ListNode();
  4.         ListNode tmp = head;
  5.     
  6.         while(list1!=null&&list2!=null){
  7.             if(list1.val < list2.val){
  8.                 tmp.next = list1;
  9.                 list1 = list1.next;
  10.                 tmp = tmp.next;
  11.             }else{
  12.                 tmp.next = list2;
  13.                 list2 = list2.next;
  14.                 tmp = tmp.next;
  15.             }
  16.         }
  17.         //判断剩余的情况
  18.         if(list1!=null){
  19.             tmp.next = list1;
  20.         }else if(list2!=null){
  21.             tmp.next = list2;
  22.         }
  23.         return head.next;
  24.     }
  25. }

5. Divisione dell'elenco collegato

Divisione dell'elenco collegato CM11

Questa è una domanda per un'intervista su Niuke. Il significato della domanda è dividere l'elenco collegato. Il lato sinistro di x è minore di x e il lato destro è maggiore di x. L'ordine originale non può essere modificato.

Idea: definire un nuovo nodo cur per attraversare l'elenco collegato originale (per evitare che l'elenco collegato originale venga modificato), inserire tutto ciò che è più grande di x in un elenco collegato, inserire tutto ciò che è più piccolo di x in un elenco collegato e infine connettere i due elenchi collegati.

  1. public class Partition {
  2.     public ListNode partition(ListNode pHead, int x) {
  3.         ListNode bs = null;
  4.         ListNode be = null;
  5.         ListNode as = null;
  6.         ListNode ae = null;
  7.         ListNode cur = pHead;
  8.         while (cur != null) {
  9.             if (cur.val < x) {
  10.                 //处理刚开始为null的情况
  11.                 if (bs == null) {
  12.                     bs = be = cur;
  13.                 }else{
  14.                     be.next = cur;
  15.                     be = be.next;
  16.                 }
  17.             }else{
  18.                 if(as == null){
  19.                     as = ae = cur;
  20.                 }else{
  21.                     ae.next = cur;
  22.                     ae = ae.next;
  23.                 }
  24.             }
  25.             cur = cur.next;
  26.         }
  27.         //都是比x大的情况
  28.         if(bs == null){
  29.             return as;
  30.         }
  31.         be.next = as;
  32.         //最后都要置为null，不然可能会报错
  33.         if(as!=null){
  34.             ae.next = null;
  35.         }
  36.         return bs;
  37.     }
  38. }

Va notato che se sono maggiori di x, cioè bs = null, allora verrà restituito direttamente as e se as.next viene infine impostato su null

6. Struttura palindroma della lista concatenata OR36

OR36 struttura palindroma della lista concatenata

Questa è una domanda di Niuke, perché ha requisiti di complessità temporale e di complessità spaziale, il che significa che non è possibile aprire un array aggiuntivo, altrimenti la complessità spaziale non verrà superata e l'attraversamento normale avrà una complessità di O(n)

L'idea è questa: prima trova il nodo centrale lento dell'elenco collegato, quindi inverti la parte dal centro alla fine. Il nodo principale viene attraversato all'indietro e anche il nodo lento viene attraversato all'indietro i valori​​sono diversi, significa che non restituiscono la struttura del testo

L'inversione dell'elenco collegato e la ricerca del nodo intermedio sono già stati praticati in precedenza

  1. public class PalindromeList {
  2.     public boolean chkPalindrome(ListNode head) {
  3.         if (head == null) {
  4.             return true;
  5.         }
  6.         //找到中间节点
  7.         ListNode fast = head;
  8.         ListNode slow = head;
  9.         while (fast != null && fast.next != null) {
  10.             fast = fast.next.next;
  11.             slow = slow.next;
  12.         }
  13.         //从slow开始到末尾反转
  14.         ListNode cur = slow.next;
  15.         while (cur != null) {
  16.             ListNode curn = cur.next;
  17.             cur.next = slow;
  18.             slow = cur;
  19.             cur = curn;
  20.         }
  21.         //判断回文
  22.         while (head != slow) {
  23.             if (head.val != slow.val) {
  24.                 return false;
  25.             }
  26.             //判断偶数节点
  27.             if (head.next == slow) {
  28.                 return true;
  29.             }
  30.             head = head.next;
  31.             slow = slow.next;
  32.         }
  33.         return true;
  34.     }
  35. }

Va notato che esiste anche una differenza nel giudizio della lista concatenata di nodi con numeri dispari e della lista concatenata di nodi con numeri pari.

Se il nodo con numero pari viene spostato in alto, causerà un ciclo infinito, quindi è necessaria un'ulteriore valutazione per il nodo con numero pari.

7. Elenchi collegati intersecati

160. Elenchi concatenati intersecati

La lista concatenata che si interseca è una trasformazione simile a "Y", come mostrato in figura

Anche l’immagine nella domanda qui sotto è molto chiara.

Idea: perché se A è corto o B è corto, la differenza tra loro è la parte prima dell'intersezione. Devi solo spostare la lunga lista concatenata di una differenza, quindi i due nodi della lista concatenata si spostano indietro contemporaneamente nodi identici devono intersecare il nodo di

  1. public class Solution {
  2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3.         ListNode pl = headA;
  4.         ListNode ps = headB;
  5.         int cnta = 0,cntb = 0;
  6.         //计算两个链表的长度
  7.         while(pl!=null){
  8.             pl = pl.next;
  9.             cnta++;
  10.         }
  11.         while(ps!=null){
  12.             ps = ps.next;
  13.             cntb++;
  14.         }
  15.         //如果链表b长，就更新pl,ps
  16.         int len = cnta - cntb;
  17.         //上面求长度时pl,ps都为空了，所以这里再重新指向
  18.         pl = headA;
  19.         ps = headB;
  20.         if(len < 0){
  21.             pl = headB;
  22.             ps = headA;
  23.             len = cntb - cnta;
  24.         }
  25.         //移动差值
  26.         while(len!=0){
  27.             pl = pl.next;
  28.             len--;
  29.         }
  30.         //找到相交节点
  31.         while(pl!=ps){
  32.             pl = pl.next;
  33.             ps = ps.next;
  34.         }
  35.         //链表不相交的情况
  36.         if(pl == null) return null;
  37.         return pl;
  38.     }
  39. }

Infine, dobbiamo aggiungere la situazione disgiunta Anche se possiamo superare questa domanda senza aggiungerla, dobbiamo comunque aggiungerla per motivi di rigore.

8. Elenco collegato circolare

8.1 Determinare se esiste un loop

141. Elenco circolare collegato

Come determinare se un elenco collegato ha un ciclo:Usa ancora il puntatore di velocità, proprio come due persone che corrono nel parco giochi, una persona corre veloce e l'altra persona corre lentamente Poiché il parco giochi è un anello, quello veloce può sicuramente superare quello lento. In questo momento si sono incontrati , ma se non fosse stato per Tamaki, non sarebbero mai riusciti a incontrarsi, proprio come una dea che non puoi catturare, non importa quanto duramente la insegui.

Ma c'è un'altra situazione. Se si tratta di un anello con due nodi, e il puntatore veloce definito fa 3 passi alla volta e il puntatore lento fa 1 passo alla volta, allora non si incontreranno mai.

Pertanto, i puntatori definiti devono valutare quanti passi compiere ogni volta. Se uno fa 2 passi e l'altro ne fa 1, si incontreranno sicuramente.

  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         ListNode fast = head;
  4.         ListNode slow = head;
  5.         while(fast!=null&&fast.next!=null){
  6.             fast = fast.next.next;
  7.             slow = slow.next;
  8.             if(fast == slow) return true;
  9.         }
  10.         return false;
  11.     }
  12. }

8.2 Restituire il nodo all'ingresso dell'anello

142. Lista Circolare Collegata II

Questa volta devi scoprire il punto di ingresso nell'anello dopo aver giudicato se si tratta di un anello nella domanda precedente. Puoi fare il seguente ragionamento

  1. public class Solution {
  2.     public ListNode detectCycle(ListNode head) {
  3.         ListNode fast = head;
  4.         ListNode slow = head;
  5.         //判断环
  6.         while(fast!=null&&fast.next!=null){
  7.             fast = fast.next.next;
  8.             slow = slow.next;
  9.             if(fast == slow) break;
  10.         }
  11.         if(fast == null||fast.next == null) return null;
  12.         slow = head;
  13.         //寻找环
  14.         while(slow!=fast){
  15.             slow = slow.next;
  16.             fast = fast.next;
  17.         }
  18.         return slow;
  19.     }
  20. }

Ciò che occorre aggiungere è:

Quando l'anello è molto piccolo il risultato finale della semplificazione diventa quello sopra, ma il codice originale va comunque bene.

Profilo personale

Si dedica alla ricerca tecnologica da più di trent'anni, è esperto in vari linguaggi come java, linux, javascript, php, css, ecc., e ha apportato numerosi contributi nel campo dell'open source una stazione di documentazione per gli sviluppatori per condividere alcuni problemi nello sviluppo della tecnologia per riferimento futuro. Tutti la controllano

le mie informazioni di contatto

Posta