Κοινή χρήση τεχνολογίας

Επιλεγμένες ερωτήσεις τεστ Likou, Niukelian επιφάνειας

2024-07-12

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

💎 欢迎各位大佬互三：την αρχική μου σελίδα

1. Αντίστροφη συνδεδεμένη λίστα

206.Αντίστροφη συνδεδεμένη λίστα

Σκέψη: Εάν δεν ανοίξετε επιπλέον χώρο και τροποποιήσετε μόνο την αρχική συνδεδεμένη λίστα, ποια μέθοδος θα πρέπει να χρησιμοποιήσετε;

Απλώς ξεκινήστε από το δεύτερο στοιχείο και εκτελέστε την εισαγωγή της κεφαλής με τη σειρά.

Στη συνέχεια απλώς τροποποιήστε την αναφορά και τοποθετήστε το τελευταίο στοιχείο σε 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. Ο μεσαίος κόμβος της συνδεδεμένης λίστας

876. Ενδιάμεσος κόμβος συνδεδεμένης λίστας

Η πρώτη μέθοδος που έρχεται στο μυαλό για αυτήν την ερώτηση είναι οπωσδήποτε να ορίσετε ένα cnt, να διασχίσετε τη συνδεδεμένη λίστα μία φορά, μετά να βρείτε τον μεσαίο αριθμό και μετά να διασχίσετε την τιμή επιστροφής Αυτή η μέθοδος είναι πολύ απλή, αλλά τι γίνεται αν χρειαστεί να διασχίσετε την τιμή συνδεδεμένη λίστα μόνο μία φορά για να βρείτε τον ενδιάμεσο κόμβο;

Εδώ είναι μια νέα ιδέα: χρησιμοποιήστε τους γρήγορους και αργούς δείκτες, ξεκινώντας από το κεφάλι Ο γρήγορος δείκτης μετακινεί δύο κόμβους κάθε φορά και ο αργός δείκτης κινεί έναν κόμβο κάθε φορά.

Τότε ας το εφαρμόσουμε:

  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. }

Θα ήταν πιο αποτελεσματικό αυτό;

3. Επιστρέψτε τον κ-ο κόμβο από τον τελευταίο

Ερώτηση συνέντευξης 02.02 Επιστρέψτε τον κ-ο κόμβο από τον τελευταίο

Το πρώτο πράγμα που έρχεται στο μυαλό για αυτήν την ερώτηση είναι να το διασχίσετε μία φορά για να λάβετε το συνολικό μήκος και στη συνέχεια να βρείτε τον κ-ο κόμβο από τον τελευταίο, ωστόσο, με βάση την προηγούμενη ερώτηση, μπορείτε να σκεφτείτε μια άλλη μέθοδο: Ομοίως,Χρησιμοποιώντας τους γρήγορους και αργούς δείκτες, αφήστε πρώτα τους κόμβους γρήγορα να πάνε και μετά να πάνε αργοί και γρήγοροι ταυτόχρονα είναι ο κ-ος κόμβος από κάτω.

Αυτή η ερώτηση υποδεικνύει ότι η είσοδος k είναι νόμιμη, επομένως δεν χρειάζεται πρόσθετη κρίση Πώς να κρίνουμε εάν το k είναι παράνομο και απαιτείται να μην μπορεί να βρεθεί άμεσα το μήκος της συνδεδεμένης λίστας, επομένως χρειάζεται να κριθεί αργά ενώ περπατάτε.

  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. Συγχώνευση συνδεδεμένων λιστών

21. Συγχωνεύστε δύο ταξινομημένες συνδεδεμένες λίστες

Ιδέα:Χρειάζεται μόνο να ορίσετε έναν νέο κόμβο newH και, στη συνέχεια, να συγκρίνετε την val του headA και του headB Για να βρείτε τελικά τον κύριο κόμβο της συγχωνευμένης συνδεδεμένης λίστας, πρέπει επίσης να ορίσετε ένα tmp = newH και, στη συνέχεια, όποιος έχει το μικρότερο. tmp.next θα το δείχνει.

  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. Διαχωρισμός συνδεδεμένης λίστας

Διαχωρισμός συνδεδεμένης λίστας CM11

Αυτή είναι μια ερώτηση συνέντευξης στο Niuke Το νόημα της ερώτησης είναι να διαιρέσετε τη συνδεδεμένη λίστα Η αριστερή πλευρά του x είναι μεγαλύτερη από το x.

Ιδέα: Ορίστε έναν νέο κόμβο για να διασχίσετε την αρχική συνδεδεμένη λίστα (για να αποτρέψετε την αλλαγή της αρχικής συνδεδεμένης λίστας), τοποθετήστε ό,τι μεγαλύτερο από x σε μια συνδεδεμένη λίστα, βάλτε οτιδήποτε μικρότερο από x σε μια συνδεδεμένη λίστα και, τέλος, συνδέστε τα δύο συνδεδεμένες λίστες.

  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. }

Πρέπει να σημειωθεί ότι εάν είναι μεγαλύτερα από x, δηλαδή bs = null, τότε το as θα επιστραφεί απευθείας και εάν το as.next οριστεί τελικά σε null

6. Δομή παλίνδρομου της συνδεδεμένης λίστας OR36

Δομή παλίνδρομου OR36 της συνδεδεμένης λίστας

Αυτή είναι μια ερώτηση από τη Niuke, επειδή έχει απαιτήσεις πολυπλοκότητας χρόνου και χώρου, πράγμα που σημαίνει ότι δεν μπορείτε να ανοίξετε έναν επιπλέον πίνακα, διαφορετικά η πολυπλοκότητα του χώρου δεν θα ξεπεραστεί και η κανονική διέλευση θα έχει πολυπλοκότητα O(n)

Η ιδέα είναι αυτή: πρώτα βρείτε τον μεσαίο κόμβο της συνδεδεμένης λίστας και μετά αντιστρέψτε το τμήμα από τη μέση προς το τέλος οι τιμές είναι διαφορετικές, σημαίνει ότι δεν επιστρέφουν δομή κειμένου

Η αντιστροφή της συνδεδεμένης λίστας και η εύρεση του ενδιάμεσου κόμβου έχουν εξασκηθεί στο παρελθόν

  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. }

Πρέπει να σημειωθεί ότι υπάρχει επίσης διαφορά στην κρίση της συνδεδεμένης λίστας περιττών κόμβων και της συνδεδεμένης λίστας των ζυγών κόμβων.

Εάν ο ζυγός κόμβος μετακινηθεί στην κορυφή, θα προκαλέσει έναν άπειρο βρόχο, επομένως απαιτείται πρόσθετη κρίση για τον ζυγό κόμβο.

7. Διασταυρούμενες συνδεδεμένες λίστες

160. Διασταυρούμενες συνδεδεμένες λίστες

Η τεμνόμενη συνδεδεμένη λίστα είναι ένας μετασχηματισμός παρόμοιος με το "Y", όπως φαίνεται στο σχήμα

Η εικόνα στην παρακάτω ερώτηση είναι επίσης πολύ σαφής.

Ιδέα: Επειδή το Α είναι σύντομο ή το Β, η διαφορά μεταξύ τους είναι το τμήμα πριν από τη διασταύρωση πανομοιότυποι κόμβοι πρέπει να τέμνουν τον κόμβο του

  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. }

Τέλος, πρέπει να προσθέσουμε την ασύνδετη κατάσταση Αν και μπορούμε να περάσουμε αυτήν την ερώτηση χωρίς να την προσθέσουμε, πρέπει ακόμα να την προσθέσουμε για λόγους αυστηρότητας.

8. Κυκλική συνδεδεμένη λίστα

8.1 Προσδιορίστε εάν υπάρχει βρόχος

141. Κυκλική συνδεδεμένη λίστα

Πώς να προσδιορίσετε εάν μια συνδεδεμένη λίστα έχει κύκλο:Χρησιμοποιήστε ακόμα τον δείκτη ταχύτητας, ακριβώς όπως δύο άτομα που τρέχουν στην παιδική χαρά, το ένα άτομο τρέχει γρήγορα και το άλλο άτομο τρέχει αργά , αλλά αν δεν ήταν το Tamaki, δεν θα μπορούσαν ποτέ να συναντηθούν, όπως μια θεά που δεν μπορείς να την πιάσεις όσο κι αν κυνηγήσεις.

Αλλά υπάρχει μια άλλη κατάσταση, εάν είναι ένας δακτύλιος με δύο κόμβους, και ο καθορισμένος γρήγορος δείκτης κάνει 3 βήματα τη φορά και ο αργός δείκτης κάνει 1 βήμα τη φορά, τότε δεν θα συναντηθούν ποτέ.

Επομένως, οι καθορισμένοι δείκτες πρέπει να κρίνουν πόσα βήματα κάνουν κάθε φορά, αν ο ένας κάνει 2 βήματα και ο άλλος 1 βήμα, σίγουρα θα συναντηθούν.

  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 Επιστρέψτε τον κόμβο στην είσοδο του δακτυλίου

142. Κυκλική Συνδεδεμένη Λίστα II

Αυτή τη φορά πρέπει να μάθετε το σημείο εισόδου στο δαχτυλίδι αφού κρίνετε αν είναι δαχτυλίδι στην προηγούμενη ερώτηση Μπορείτε να κάνετε τον ακόλουθο συλλογισμό

  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. }

Αυτό που πρέπει να προστεθεί είναι:

Όταν ο δακτύλιος είναι πολύ μικρός, το τελικό αποτέλεσμα απλοποίησης γίνεται το παραπάνω, αλλά ο αρχικός κωδικός είναι ακόμα εντάξει.

Προσωπικό προφίλ

Έχει αφοσιωθεί στην έρευνα της τεχνολογίας για περισσότερα από 30 χρόνια και είναι ικανός σε διάφορες γλώσσες όπως java, linux, javascript, php, css κ.λπ. Έχει κάνει πολλές συνεισφορές στον τομέα του ανοιχτού κώδικα τεκμηρίωσης προγραμματιστή για να μοιραστείτε τα ζητήματα στην ανάπτυξη τεχνολογίας για μελλοντική αναφορά

τα στοιχεία επικοινωνίας μου

Ταχυδρομείο