双指針法の-秩序配列-脱重と合併

21.2つの秩序チェーンテーブルを結合する
2つの昇順チェーンテーブルを新しい昇順チェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます.例:入力:1->2->4、1->3->4出力:1->1->2->3->4->4
非常に正常な考え方で、2つのポインタがそれぞれ2つのチェーンテーブルを指していることを定義し、それぞれ比較します.
シーケンス番号
0
1
2
3
4
5
6
チェーンテーブルa
a0
a1
a2
a3
a4
a5
a6
チェーンテーブルb
b0
b1
b2
b3
b4
b5
b6
まずa 0とb 0を比較し、a 0がb 0より大きい場合はチェーンテーブルaのポインタを後ろにずらし、a 1を指し、次にa 1とb 0を比較し、a 1がb 0より小さい場合はチェーンテーブルaのポインタをもう一つ後ろにずらし、a 2とb 0を比較し、a 2がb 0より大きい場合はチェーンテーブルbのポインタを後ろにずらし、b 1を指し、次にa 2とb 1を比較し、最後まで比較するのは非常に素朴な考えである

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = tmp = ListNode(-1)
        while l1 and l2:
            if l1.val < l2.val:
                tmp.next = l1
                l1 = l1.next
            else:
                tmp.next = l2
                l2 = l2.next
            tmp = tmp.next
        if l1:
            tmp.next = l1
        if l2:
            tmp.next = l2
        return head.next

ここで要求されるのは、新しいチェーンテーブルが、所与の2つのチェーンテーブルのすべてのノードを接合することによって構成されることである.だから新しいチェーン時計はなくて、直接元のチェーン時計をつなぎ合わせます
88.2つの配列を結合する
2つの秩序整数配列nums 1とnums 2を与えます.nums 2をnums 1に結合し、num 1を秩序配列にします.説明:nums 1とnums 2を初期化する要素の数は、それぞれmとnです.nums 1にはnums 2の要素を保存するのに十分な空間(空間サイズがm+n以上)があると仮定できます.例:入力:nums 1=[1,2,3,0,0],m=3 nums 2=[2,5,6],n=3出力:[1,2,2,3,5,6]
2つの配列をマージする方法は、チェーンテーブルをマージするのと同じですが、配列には任意の位置を直接読み取り、格納できるというメリットがあります.逆順に比較して、2つの配列の最後の位置、つまり最大の値を比較し、2つの配列の中で最も大きな値を一番後ろに置くことで、スペースを追加しない場合、2つの配列を1つに格納します.もちろんここにも制限条件のあるnums1 （ m + n） nums2 があります.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        end = m + n - 1
        p = m - 1
        q = n - 1
        while p >= 0 and q >= 0:
            if nums1[p] > nums2[q]:
                nums1[end] = nums1[p]
                p -= 1
            else:
                nums1[end] = nums2[q]
                q -= 1
            end -= 1

        nums1[:q+1] = nums2[:q+1]

26.ソート配列の重複を削除する
これは二重ポインタの巧みな応用と言えるが,前の二つは実は正常な応用である.2つのポインタをとり、i,j,nums[j]==nums[i]の説明が重複している場合は、j j jを1つ移動し、次に比較し、等しい場合は移動を続け、nums[j]がnums[i]に等しくない場合は新しい項目であることを説明し、iの位置を1つ後ろにずらしてnums[i]に割り当てます.
本質的にnums[j]は異なる項目を発見するために用いられ,発見後は前に保存される.
nums[j] == nums[i],j = j+1
シーケンス番号
i
j
はいれつ
2
2
3
3
3
3
4
シーケンス番号
i
j
はいれつ
2
2
3
3
3
3
4
発見nums[j]!=nums[i],i=i+1,値を過去に割り当てる
シーケンス番号
i
j
はいれつ
2
3
3
3
3
3
4
次にnums[j]==nums[i],j=j+1
シーケンス番号
i
j
はいれつ
2
3
3
3
3
3
4
それとも等しいj=j+1
シーケンス番号
i
j
はいれつ
2
3
3
3
3
3
4
それとも等しいj=j+1
シーケンス番号
i
j
はいれつ
2
3
3
3
3
3
4
それとも等しいj=j+1
シーケンス番号
i
j
はいれつ
2
3
3
3
3
3
4
発見nums[j]!=nums[i],i=i+1,値を過去に割り当てる
シーケンス番号
i
j
はいれつ
2
3
4
3
3
3
4
終了後前のiビットに保存されているのは、デポジット後のデータです

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i,j,n = 0,1,len(nums)
        while j < n:
            if nums[j] == nums[i]:
                j += 1
            else:
                i += 1
                nums[i] = nums[j]
        return i+1

27.要素の除去
配列numsと値valを与えます.valに等しいすべての数値の要素をその場で除去し、除去後の配列の新しい長さを返す必要があります.余分な配列空間を使用しないでください.O(1)余分な空間だけを使用して、入力配列をその場で変更する必要があります.要素の順序は変更できます.配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.
同じ2つのポインタで、1つのポインタは頭を指して、1つのポインタは尾を指して、もし頭のポインタの値がvalに等しくないならば、後ろに行って、もしvalに等しいならば、私達は後ろから探して、1つの等しくないvalの値を見つけて、過去を置き換えます
シーケンス番号
i
j
はいれつ
0
1
2
2
3
0
4
2
val[i] != 2、後ろへ行きます.
シーケンス番号
i
j
はいれつ
0
1
2
2
3
0
4
2
ここまで来たら2に等しい、そしてjを見てnums[j]==2を発見して、まっすぐ前へ行って、この2を捨てました
シーケンス番号
i
j
はいれつ
0
1
2
2
3
0
4
2
発見nums[j]!=2,この値を前nums[i]=2の位置に置き,jをさらに前へ,iを後ろへ
シーケンス番号
i
j
はいれつ
0
1
4
2
3
0
4
2
nums[i]はまた2に等しくなったので,次に2に等しくないjを探して置き換えた.

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        p,q = 0,len(nums)-1
        while p <= q:
            if nums[q] == val:
                q -= 1
            if nums[p] != val:
                p += 1
            else:
                nums[p] = nums[q]
                q -= 1
        return p