ダブルポインタ1:衝突ポインタ衝突ポインタ
8615 ワード
1、配列内の要素を反転する:s=['l','e','e','t','c','o','d','e']
アルゴリズム構想:左ポインタi=0,右ポインタr=len(s)-1を定義する.ポインタに対応する要素を交換し、ポインタが衝突するまでポインタを中間に移動します.ポインタが移動しながら、ポインタが指す要素を交換します.
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]を返します.
3、返信文字列を検証します.文字列を指定し、文字列が文字列であるかどうかを検証し、文字と数字のみを考慮し、文字の大文字と小文字を無視できます.
4、文字列の母音文字を反転します.入力:hello出力:holle.アルゴリズムの構想は問題3に似ている.
5、一番水を盛る容器.n個の非負の整数a 1,a 2,...,anは、各数が座標の1つの点(i,ai)を表す.座標内にn本の垂直線を描き、垂直線iの2つの端点はそれぞれ(i,ai)と(i,0)である.x軸と共に構成された容器が最も多くの水を収容できるように、その中の2本の線を探し出す.
アルゴリズム構想:左ポインタ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))