目錄
前言
1.判斷鍊錶是否有環
2.找出鍊錶中間的元素
3.奇偶排序前奇後偶
4.刪除排序鍊錶的重複元素
5.三數總和
6.分割鍊錶
7.合併兩個有順序的陣列
8.兩數總和—輸入有序數組
9.長度最小的子數組
10.排序链表
首頁 Java java教程 Java雙指標法怎麼使用

Java雙指標法怎麼使用

Apr 18, 2023 pm 08:34 PM
java

前言

通常用在線性的資料結構中,例如鍊錶和陣列。

指標其實就是資料的索引或是鍊錶的結點。兩個指針朝著左右兩個方向移動,直到滿足搜尋條件。雙指針可分為同向雙指針、異向雙指針、快慢指針、滑動視窗。根據需求選擇雙指標的模型,例如刪除陣列或鍊錶中重複的元素,同向雙指標(線性表前提是有序的); 快慢指標一般用在鍊錶中,例如求鍊錶的中點、判斷鍊錶是否有環、判斷鍊錶換的起點、環的長度、以及鍊錶的倒數第K個元素; 例如在二分查找中用的就是異向雙指針; 滑動窗口其實就是在數組或者鍊錶某個區間上的操作,例如求最長/最短子字串或是特定子字串的長度要求。

1.判斷鍊錶是否有環

力扣141題

#給你一個鍊錶的頭節點 head ,判斷鍊錶中是否有環。

如果鍊錶中有某個節點,可以透過連續追蹤 next 指標再次到達,則鍊錶中存在環。為了表示給定鍊錶中的環,評測系統內部使用整數 pos 來表示鍊錶尾連接到鍊錶中的位置(索引從 0 開始)。注意:pos 不作為參數進行傳遞 。只是為了標識鍊錶的實際情況。

如果鍊錶中存在環 ,則傳回 true 。否則,傳回 false 。

Java雙指標法怎麼使用

程式碼實作

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.找出鍊錶中間的元素

力扣876題

給定一個頭結點為head 的非空單鍊錶,傳回鍊錶的中間結點。

如果有兩個中間結點,則傳回第二個中間結點。

Java雙指標法怎麼使用

程式實作

  //快慢指针法
    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.奇偶排序前奇後偶

力扣328題

給定單鍊錶的頭節點head ,將所有索引為奇數的節點和索引為偶數的節點分別組合在一起,然後傳回重新排序的清單。

第一個節點的索引被認為是 奇數 , 第二個節點的索引為 偶數 ,以此類推。

Java雙指標法怎麼使用

程式碼實作

 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.刪除排序鍊錶的重複元素

力扣82題

給定一個已排序的鍊錶的頭head , 刪除原始鍊錶中所有重複數字的節點,只留下不同的數字。傳回已排序的鍊錶

Java雙指標法怎麼使用

程式碼實作

 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.三數總和

力扣15題

給你一個包含n 個整數的陣列nums,判斷nums 中是否存在三個元素a,b,c ,使得a b c = 0 ?請你找出所有和為 0 且不重複的三元組。

注意:答案中不可以包含重複的三元組。

Java雙指標法怎麼使用

程式碼實作

 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.分割鍊錶

力扣面試題02.04

給你一個鍊錶的頭節點head 和一個特定值x ,請你將鍊錶分隔,使得所有小於x 的節點都出現在大於或等於x 的節點之前。

你不需要 保留 每個分區中各節點的初始相對位置。

Java雙指標法怎麼使用

程式碼實作

 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.合併兩個有順序的陣列

力扣88題

給你兩個按非遞減順序排列的整數數組nums1 和nums2,另有兩個整數m 和n ,分別表示nums1 和nums2 中的元素數目。請你 合併 nums2 到 nums1 中,使合併後的陣列同樣按 非遞減順序 排列。

注意:最終,合併後陣列不應由函數傳回,而是儲存在陣列 nums1 中。為了因應這種情況,nums1 的初始長度為 m n,其中前 m 個元素表示應合併的元素,後 n 個元素為 0 ,應忽略。 nums2 的長度為 n 。

Java雙指標法怎麼使用

程式碼實作

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.兩數總和—輸入有序數組

力扣167題

#給你一個下標從1 開始的整數數組numbers ,該數組已按非遞減順序排列,請你從數組中找出滿足相加之和等於目標數target 的兩個數。如果設這兩個數分別是 numbers[index1] 和 numbers[index2] ,則 1 <= index1 < index2 <= numbers.length 。

以長度為 2 的整數陣列 [index1, index2] 的形式傳回這兩個整數的下標 index1 和 index2。

Java雙指標法怎麼使用

程式碼實作

 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.長度最小的子數組

(力扣209)給定一個含有n 個正整數的數組和一個正整數target 。

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

Java雙指標法怎麼使用

代码实现

//滑动窗口法
 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 ,请将其按 升序 排列并返回 排序后的链表 。

Java雙指標法怎麼使用

解题思路

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

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;
    }
登入後複製

以上是Java雙指標法怎麼使用的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

突破或從Java 8流返回? 突破或從Java 8流返回? Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API,提供了一種強大且表達力豐富的處理數據集合的方式。然而,使用Stream時,一個常見問題是:如何從forEach操作中中斷或返回? 傳統循環允許提前中斷或返回,但Stream的forEach方法並不直接支持這種方式。本文將解釋原因,並探討在Stream處理系統中實現提前終止的替代方法。 延伸閱讀: Java Stream API改進 理解Stream forEach forEach方法是一個終端操作,它對Stream中的每個元素執行一個操作。它的設計意圖是處

PHP:網絡開發的關鍵語言 PHP:網絡開發的關鍵語言 Apr 13, 2025 am 12:08 AM

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

PHP與Python:了解差異 PHP與Python:了解差異 Apr 11, 2025 am 12:15 AM

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

PHP與其他語言:比較 PHP與其他語言:比較 Apr 13, 2025 am 12:19 AM

PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

Java程序查找膠囊的體積 Java程序查找膠囊的體積 Feb 07, 2025 am 11:37 AM

膠囊是一種三維幾何圖形,由一個圓柱體和兩端各一個半球體組成。膠囊的體積可以通過將圓柱體的體積和兩端半球體的體積相加來計算。本教程將討論如何使用不同的方法在Java中計算給定膠囊的體積。 膠囊體積公式 膠囊體積的公式如下: 膠囊體積 = 圓柱體體積 兩個半球體體積 其中, r: 半球體的半徑。 h: 圓柱體的高度(不包括半球體)。 例子 1 輸入 半徑 = 5 單位 高度 = 10 單位 輸出 體積 = 1570.8 立方單位 解釋 使用公式計算體積: 體積 = π × r2 × h (4

PHP與Python:核心功能 PHP與Python:核心功能 Apr 13, 2025 am 12:16 AM

PHP和Python各有優勢,適合不同場景。 1.PHP適用於web開發,提供內置web服務器和豐富函數庫。 2.Python適合數據科學和機器學習,語法簡潔且有強大標準庫。選擇時應根據項目需求決定。

創造未來:零基礎的 Java 編程 創造未來:零基礎的 Java 編程 Oct 13, 2024 pm 01:32 PM

Java是熱門程式語言,適合初學者和經驗豐富的開發者學習。本教學從基礎概念出發,逐步深入解說進階主題。安裝Java開發工具包後,可透過建立簡單的「Hello,World!」程式來實踐程式設計。理解程式碼後,使用命令提示字元編譯並執行程序,控制台上將輸出「Hello,World!」。學習Java開啟了程式設計之旅,隨著掌握程度加深,可創建更複雜的應用程式。

PHP:許多網站的基礎 PHP:許多網站的基礎 Apr 13, 2025 am 12:07 AM

PHP成為許多網站首選技術棧的原因包括其易用性、強大社區支持和廣泛應用。 1)易於學習和使用,適合初學者。 2)擁有龐大的開發者社區,資源豐富。 3)廣泛應用於WordPress、Drupal等平台。 4)與Web服務器緊密集成,簡化開發部署。

See all articles