Comment utiliser la méthode Java à double pointeur

Préface

Habituellement utilisé dans les structures de données linéaires, telles que les listes chaînées et les tableaux.

Un pointeur est en fait l'index de données ou le nœud d'une liste chaînée. Les deux pointeurs se déplacent dans les directions gauche et droite jusqu'à ce que les conditions de recherche soient remplies. Les pointeurs doubles peuvent être divisés en pointeurs doubles dans la même direction, pointeurs doubles dans des directions différentes, pointeurs rapides et lents et fenêtres coulissantes. Choisissez un modèle à double pointeur en fonction de vos besoins, comme la suppression des éléments en double dans un tableau ou une liste chaînée, des pointeurs doubles dans la même direction (les listes linéaires doivent être ordonnées, les pointeurs rapides et lents sont généralement utilisés dans les listes chaînées, comme la recherche) ; le point médian d'une liste chaînée et déterminer si une liste chaînée est S'il y a un anneau, déterminer le point de départ du remplacement de la liste chaînée, la longueur de l'anneau et le Kème dernier élément de la liste chaînée. Par exemple, en binaire ; recherche, des pointeurs doubles anisotropes sont utilisés ; La fenêtre coulissante est en fait une opération sur un certain intervalle d'un tableau ou d'une liste chaînée. Par exemple, trouver la sous-chaîne la plus longue/la plus courte ou la longueur requise d'une sous-chaîne spécifique.

1. Déterminez s'il y a un cycle dans la liste chaînée

Question Luc 141

Vous recevez un nœud principal en tête de la liste chaînée et déterminez s'il y a un cycle dans la liste chaînée.

S'il y a un nœud dans la liste chaînée qui peut être atteint à nouveau en suivant continuellement le pointeur suivant, alors il y a un cycle dans la liste chaînée. Pour représenter un cycle dans une liste chaînée donnée, le système d'évaluation utilise en interne l'entier pos pour représenter la position dans la liste chaînée où la queue de la liste chaînée est connectée (index commençant à 0). Remarque : pos n'est pas passé en paramètre. Juste pour identifier la situation réelle de la liste chaînée.

Renvoie vrai s'il y a un cycle dans la liste chaînée. Sinon, retournez false .

Implémentation du code

public class Solution {
    //快慢指针法
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode low = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
            //此时相遇了
            if(fast == low){
                return true;
            }
        }
        return false;
    }
}

2. Recherchez l'élément au milieu de la liste chaînée

Question Liqun 876

Étant donné une liste chaînée unique non vide avec le nœud principal head, renvoyez le nœud central du lié. liste.

S'il y a deux nœuds intermédiaires, renvoyez le deuxième nœud intermédiaire.

Implémentation du code

  //快慢指针法
    public ListNode middleNode(ListNode head) {
        ListNode low = head,fast = head;
        while(fast != null && fast.next != null){
            //慢指针走一步
            low = low.next;
            //快指针走两步
            fast = fast.next.next;
        }
        //奇数，fast.next = null时，low即为所求
        //偶数，fsat == null时，low即为所求
        return low;
    }

3. Tri impair et pair avant impair et après pair

Liqun 328 questions

Étant donné le nœud principal de la liste à chaînage unique, combinez tous les nœuds avec des index impairs et les nœuds avec des index pairs dans ensemble, puis renvoyez la liste réorganisée.

L'index du premier nœud est considéré comme un nombre impair, l'index du deuxième nœud est un nombre pair, et ainsi de suite.

Implémentation du code

 public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode fastHead = head.next;
        ListNode lowTail = head;//奇数链表
        ListNode fastTail = fastHead;//偶数链表
        while(fastTail != null && fastTail.next != null){
            //更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点
            lowTail.next = fastTail.next;
            lowTail = lowTail.next;
           // 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点
            fastTail.next = lowTail.next;
            fastTail = fastTail.next;
        }
        //合并两个链表
        lowTail.next = fastHead;
        return head;
    }

4. Supprimer les éléments en double de la liste chaînée triée

Liqun 82 questions

Étant donné la tête d'une liste chaînée triée, supprimez tous les nœuds avec des numéros répétés dans la liste chaînée d'origine, en ne laissant que Différents numéros. Renvoie la liste chaînée triée

Implémentation du code

 public ListNode deleteDuplicates(ListNode head) {
        //虚拟头节点法
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode cur = prev.next;
        while(cur != null){
            //引入next指针
            ListNode next = cur.next;
            if(next == null){
                //只有一个元素
                return dummyHead.next;
            }
            if(cur.val != next.val){
                //cur不是重复节点，三指针都移动
                cur = cur.next;
                prev = prev.next;
            }else{
                //让next指针一直向后移动，直到与cur.val不相等的节点位置
                while(next != null && cur.val == next.val){
                    next = next.next;
                }
                // 此时next指向了第一个不重复的元素
                // 此时prev - next之间所有重复元素全部删除
                prev.next = next;
                cur = next;
            }
        }
        return dummyHead.next;
    }

5. Somme de trois nombres

15 questions

Vous recevez un tableau nums contenant n entiers. Déterminez s'il y a trois éléments a dans nums b, c. , tel que a + b + c = 0 ? Veuillez trouver tous les triplets non répétitifs dont la somme est 0.

Remarque : les triples en double ne sont pas autorisés dans la réponse.

Implémentation du code

 public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

6. Diviser la liste chaînée

Question d'entretien Liqun 02.04

Vous recevez le nœud principal d'une liste chaînée et une valeur spécifique x Veuillez diviser la liste chaînée de manière à ce que tous les nœuds. inférieurs à x sont tous affichés avant les nœuds supérieurs ou égaux à x.

Vous n'avez pas besoin de conserver la position relative initiale de chaque nœud dans chaque partition.

Implémentation du code

 public ListNode partition(ListNode head, int x) {
        // 创建small和big两个小链表的头节点
        ListNode smallHead = new ListNode(-1);
        ListNode bigHead = new ListNode(-1);
        // 按照升序插入，因此需要尾插
        // 分别指向两个子链表的尾部
        ListNode smallTail = smallHead;
        ListNode bigTail = bigHead;
        //遍历原链表，根据值放入small和big链表中
        while(head != null){
            if(head.val < x){
                smallTail.next = head;
                smallTail = head;
            }else{
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        bigTail.next = null;
        //拼接小链表和大链表
        smallTail.next = bigHead.next;
        return smallHead.next;
    }

7. Fusionner deux tableaux ordonnés

Cliquez sur 88 questions

Vous recevez deux tableaux d'entiers nums1 et nums2 disposés dans un ordre non décroissant, et deux entiers m et n, indiquant le nombre. d'éléments dans nums1 et nums2 respectivement. Veuillez fusionner nums2 dans nums1 afin que le tableau fusionné soit également disposé dans un ordre non décroissant.

Remarque : En fin de compte, le tableau fusionné ne doit pas être renvoyé par la fonction, mais stocké dans le tableau nums1. Pour faire face à cette situation, nums1 a une longueur initiale de m + n, où les m premiers éléments représentent les éléments qui doivent être fusionnés et les n derniers éléments sont 0 et doivent être ignorés. La longueur de nums2 est n .

Implémentation du code

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }

8. La somme de deux nombres - saisissez un tableau ordonné

Question 167

Vous recevez un tableau de nombres entiers avec des indices commençant à 1, qui est dans un ordre non décroissant. Organiser, veuillez trouver deux nombres dans le tableau tels que la somme soit égale au nombre cible cible. Si les deux nombres sont respectivement des nombres[index1] et des nombres[index2], alors 1 <= index1 <= number.length .

Renvoie les index index1 et index2 de ces deux entiers sous forme d'un tableau d'entiers de longueur 2 [index1, index2].

Implémentation du code

 public int[] twoSum(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[]{-1, -1};
    }

9. Sous-tableau de longueur minimale

(Likou 209) Étant donné un tableau contenant n entiers positifs et une cible entière positive.

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0

代码实现

//滑动窗口法
 public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

10.排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

解题思路

通过递归实现链表归并排序，有以下两个环节：

1，分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）； 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。 找到中点 slow 后，执行 slow.next = None 将链表切断。 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。 cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。

2，合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。 双指针法合并，建立辅助ListNode h 作为头部。 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。 返回辅助ListNode h 作为头部的下个节点 h.next。

代码实现

public 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);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!