ダブルポインタ1:衝突ポインタ衝突ポインタ

8615 ワード

1、配列内の要素を反転する:s=['l','e','e','t','c','o','d','e']
アルゴリズム構想:左ポインタi=0,右ポインタr=len(s)-1を定義する.ポインタに対応する要素を交換し、ポインタが衝突するまでポインタを中間に移動します.ポインタが移動しながら、ポインタが指す要素を交換します.
def reverseStr(s):
    l=0
    r=len(s)-1
    while l<r:
        s[l],s[r]=s[r],s[l]
        l+=1
        r-=1
    return s

s = ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']
print(reverseStr(s))

2、2つの数の和:昇順に配列された秩序配列を指定し、2つの数を見つけて、それらが加算された和が目標数に等しいようにします.関数は、index 1とindex 2の2つの下付き値を返す必要があります.index 1はindex 2より小さくなければなりません.
カラム:入力:numbers=[2,7,11,15]、target=9出力:[12].2と7の和は目標数9に等しい.したがってindex 1=1,index 2=2である.
アルゴリズム構想:左ポインタl=0,右ポインタr=len(nums)-1を定義する.2つのポインタが指す要素の和:sum=nums[l]+nums[r]を計算します.sumtargetの場合、
右ポインタを左に移動します.sum=targetになるまで[l+1,r+1]を返します.
def twoSum(nums,target):
    l=0
    r=len(nums)-1
    while l<r:
        sum=nums[l]+nums[r]
        if sum>target:
            r-=1
        elif sum<target:
            l+=1
        else:
            return (l+1,r+1)
            
        
nums=[2, 7, 11, 15]
target=9
print(twoSum(nums,target))

3、返信文字列を検証します.文字列を指定し、文字列が文字列であるかどうかを検証し、文字と数字のみを考慮し、文字の大文字と小文字を無視できます.
    : "A man, a plan, a canal: Panama"   : true
: l=0, r=len(s)-1. 。 , 、 。1 ;
、 。 , False。 , , 。
def isPalindrome(s):
    n=len(s)
    l=0
    r=n-1
    while l<r:
        if s[l].isalnum()==False:
            l+=1
            continue
        if s[r].isalnum()==False:
            r-=1
            continue
        if s[l].lower()!=s[r].lower():
            return False
        l+=1
        r-=1
    return True

s="A man, a plan, a canal: Panama"
print(isPalindrome(s))

4、文字列の母音文字を反転します.入力:hello出力:holle.アルゴリズムの構想は問題3に似ている.
def reverseVowels(s):
    s=list(s)
    res = ['a', 'e', 'i', 'o', 'u', 'A','E','I','O','U']
    l=0
    r=len(s)-1
    while l<r:
        if s[l] not in res:
            l+=1
            continue
        if s[r] not in res:
            r-=1
            continue
        if (l<r):
            s[l],s[r]=s[r],s[l]
        l+=1
        r-=1
    return "".join(s)


s="hello"
print(reverseVowels(s))

5、一番水を盛る容器.n個の非負の整数a 1,a 2,...,anは、各数が座標の1つの点(i,ai)を表す.座標内にn本の垂直線を描き、垂直線iの2つの端点はそれぞれ(i,ai)と(i,0)である.x軸と共に構成された容器が最も多くの水を収容できるように、その中の2本の線を探し出す.
def maxArea(height):
    l=0
    r=len(height)-1
    #     
    area=0
    while l<r:
        if height[l]<=height[r]:
            area=max(area,(r-l)*height[l])
            l+=1
        if height[l]>height[r]:
            area=max(area,(r-l)*height[r])
            r-=1
    return area


height=[1,8,6,2,5,4,8,3,7]
print(maxArea(height))