ダブルポインタ-スライドウィンドウ問題(Leetcode問題のjava実装)

Leetcode141. チェーンテーブルにリングがあるかどうかを判断する

構想:速遅二重ポインタを設定し、遅ポインタ+1は速ポインタ+2である.ループが含まれていない場合、高速ポインタは最終的にnullに遭遇し、チェーンテーブルにループが含まれていないことを示します.ループが含まれている場合、速いポインタは最終的に遅いポインタを1つのループを超え、遅いポインタと出会い、チェーンテーブルにループが含まれていることを示します.時間的複雑度はO(n)であった.

public class Solution {
     
    //        M，   M     ，           ，     。
    public boolean hasCycle(ListNode head) {
     
        if (head == null || head.next == null) 
           return false;
        ListNode slow = head;
        ListNode fast = head;
        while (fast == null || fast.next == null) {
     
            //     ，           。        
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
       return true; }
        }
        return false;
    }
}

Leetcode142. チェーンテーブルのループ入口を判断する

構想:ダブルポインタ;リングチェーンテーブルの簡単な問題と同様に速いポインタと遅いポインタ(1)で初めて出会ったとき、fast=slow+kリング長とfast=2 slowでslow=kリング長が得られる.注意:1つのポインタがチェーンヘッダーからaステップを歩いてループ入口ノードに着くと仮定すると、チェーンヘッダーからループ入口に行くステップ数はa+kループ長であるため、slowは1回目の交差後にaステップを歩いてループ入口(2)に着くことができ、1回目の2つのポインタが出会った後、速いノードにチェーンヘッダー部を指し返すことができる.そして、スナップポインタが同期して前進することで、2回目の出会いが保証され、スナップポインタがリング入口

を指している.

public ListNode detectCycle(ListNode head) {
     
          if(head==null) return null;
          ListNode slow = head;
          ListNode fast = head;
          while (fast != null && fast.next != null) {
     
              fast = fast.next.next;
              slow = slow.next;
              if (fast == slow) break;
          }
          fast = head;  //        
          while(slow!=fast){
       //               
              fast = fast.next;
              slow = slow.next;
          }
          return slow;
    }

Leetcode443.圧縮文字列

class Solution {
     
    public int compress(char[] chars) {
     
        public int compress(char[] chars) {
     
        if(chars.length == 0) return 0;
        int p=0; int left=0,right =1; // p            ，           
        while(left<chars.length){
     
            chars[p++] = chars[left];//p       +1
            while(right<chars.length && chars[left]==chars[right]){
     
                right++;  //     
            }
            if(right-left >1){
     
                String temp = String.valueOf(right-left);
                for(char ch:temp.toCharArray()){
     
                    chars[p++] = ch;
                }
            }
            left = right;
        }
        return p;
    }
}