leetcodeのポインタ方法


今日は配列編に続き、主にポインタ操作配列について説明します.
目次
  • 1.2つの数の合計は、要素
  • を返します.
  • 2.2つの数の合計-複数の要素のペア
  • を返します.
  • 3.三数の和
  • 4.順序配列の重複を削除する
  • 5.テクニック
  • 参考資料

  • 1.2つの数の合計は、要素を返します.
    配列numsとターゲットとtargetを入力すると仮定した場合、nums=[5,3,1,6],target=9などのnumsでtargetを抽出できる2つの要素の値を返します.アルゴリズムは2つの要素を返します[3,6].targetは、1対の子供要素のみがコンパクトであると仮定することができる.
    解決方法はたくさんあります.私たちは主に二重ポインタの解決方法を採用しています.
    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
          #     
          nums.sort()
          n=len(nums())
          #    
          left=0;
          right=n-1
          #    (      ,      ,     right     left)
          while left<right:
            if nums[left] +nums[right]<target:
              left+=1
            elif nums[left] +nums[right]>target:
              right+=1
            else:
              return [nums[left],num[right]]
           
    

    2.2つの数の合計-複数の要素を返します.
    numsに複数のペアの要素の和がtargetに等しい可能性があります.アルゴリズムは、nums=[1,3,1,2,2,3]と入力され、target=4と入力されたすべての要素ペアを返します.アルゴリズムが返す結果は、[[1,3],[2,2]]です.
    この問題の結題構想は同じように二重ポインタ戦略を採用している.
    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
        #     
          num.sort()
          res=[]#    
          n=len(nums)
          left=0
          right=n-1
          while left<right;
            if nums[left]+nums[right]<target:
              left+=1
            elif  nums[left]+nums[right]>target:
              right+=1
            else:
               res.append([arr[left],arr[right]])
               #    ,          ,          
               while left<right and nums[left]==num[left+1]
                  left+=1
               left+=1
               right-=1
          return res
    

    3.三数の和
    n個の整数を含む配列numsを与えて、numsの中に3つの要素a,b,cが存在するかどうかを判断して、a+b+c=0にしますか?0で重複しないすべての3元グループを見つけてください.
    この問題はやはりポインタで解きます.3つの数がありますが、私たちは1つの数を固定して、この数の右側でポインタを探して問題を解決することができます.
    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
          #     
          nums.sort()
          res=[]#    
          for i in range(len(nums)):
         #   i  0,         , i  1 ,                     ,         
            if i>0 and nums[i]=num[i-1]:
              continue
           #     
            left=i+1#                 i+1
            light=len(nums)-1
            while left<right:
              if nums[i]+nums[left]+nums[right]<target:
                left+=1
              elif nums[i]+nums[left]+nums[right]>target:
                right-=1
              else:
             #                 ,                  ,                    ,         left right
                res.append([nums[i],nums[left],nums[right]])
                while left<right and nums[left]==nums[lefts+1]
                  left+=1
                left+=1
                right-=1
            return res       
    

    4.配列内の重複を削除
    秩序配列numsを与えて、繰り返し現れる要素を元の場所で削除して、各要素が一度だけ現れるようにして、削除後の配列の新しい長さを返します.余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.入力:nums=[1,1,2]出力:2,nums=[1,2]解釈:関数は新しい長さ2を返すべきであり、元の配列numsの最初の2つの要素は1,2に変更される.配列内の新しい長さの後ろを超える要素を考慮する必要はありません.
    まずテーマを説明して、何が余分な配列空間を使わないでくださいと言って、意味は新しい配列を構築することができなくて、それから配列に物を加えて、テーマの与えたnumsで重複項を削除するしかありません.
    ここではダブルポインタの書き方も採用していますが、速い、遅い、繰り返しているかどうかを判断する、繰り返している要素に値を再付与する
    class Solution:
        def removeDuplicates(self, nums: List[int]) -> int:
           n=len(nums)
           #    ,   ,   ,           
           slow=fast=1
           while fast<n:
             if nums[fast]==num[fast-1]:
                fast+=1
             else:
                nums[slow]=nums[fast]
                fast+=1
                slow+=1
           return slow     
    

    5.テクニック
    いくつかの関数を紹介して、アルゴリズムに役立つかもしれません
    s="ssdaA*asdf:afa5ADF"
    a=[i for i in s]#              
    s.lower()#     
    nums.sort()#  (  )
    .isalpha()#         
    .isnumeric()#         
    

    参考資料
  • リンク:Leetcode-5.n sum問題python解答.
  • Leetcode:Leetcode公式サイト.