アルゴリズム(5)-leetcode-explore-learn-データ構造-文字列
19990 ワード
leetcode-explore-learn-データ構造-配列3-文字列 1.概要 2.例題 2.1バイナリ合計 2.2 strStr() を実現 2.3最長共通接頭辞 このシリーズのブログはleetcode-explore-learnサブ欄の学習ノートです.不明な点があれば、leetcode公式サイトを参照してください.https://leetcode-cn.com/explore/learn/card/array-and-string/198/introduction-to-array/768/
1.簡単に述べる
文字列は文字からなる配列です.
文字列のいくつかの一般的な関数:(1)比較関数、Pythonはクラウドアルゴリズムのリロードをサポートし、"=="を使用して文字列を比較することができます.(2)修正可能で、Pythonでは文字列が書き換えられない配列である.定義されると、文字列内の要素にのみアクセスでき、要素を直接変更することはできません.C++で文字列は変更可能です.(3)文字列接続、pythonでは2つの文字列の直接加算操作をサポートして文字列接続を行う
2.例題
2.1バイナリ加算
バイナリ文字列を与えて、彼らの和を返して、バイナリで表します.基本思想:2つの文字列を加算し、1つのシンボルビットflagを設定してキャリー情報の難点境界条件の決定:char=int(a[i])+int(b[i])+flag,chatの可能な値:0,1,2,3(1)i=[-1,-2,-l_min]遍歴加算1要素から短い文字列遍歴完了(2)i=[-l_min-1,-l_min-2 m,...,-l_max]:char=flag+int(a[i]),charの可能な値:0,1,2(3)最後にキャリーがあるかどうかを確認する必要があります
2.2 strStrを実現する()
haystack文字列とneedle文字列を指定し、haystack文字列にneedle文字列が現れる最初の場所を見つけます.存在しない場合は0を返す.
考えて、haystack文字列を遍歴して、needle文字列の最初の文字を見つけて、それから順番に後ろに探して、すべてが一致してから結果を返します.
注意点:(1)needleが空の場合、-1を返します(1つの文字列に空の文字列が見つからないことを示します).0を返す(haysta[0]から始まる文字列が空の文字列に一致することを示す)–c++言語でこのように定義されている(2)両方が空の場合、0(3)len(haystack)を返す
2.3最大共通接頭辞
文字列配列の最長の共通接頭辞を検索する関数を作成します.共通接頭辞が存在しない場合は、空の文字列「」を返してwin領域に共通接頭辞を保存し、最も短い文字列を探して、その要素を順次winに追加します.残りの文字列に接頭辞文字があるかどうかを判断します.
1.簡単に述べる
文字列は文字からなる配列です.
文字列のいくつかの一般的な関数:(1)比較関数、Pythonはクラウドアルゴリズムのリロードをサポートし、"=="を使用して文字列を比較することができます.(2)修正可能で、Pythonでは文字列が書き換えられない配列である.定義されると、文字列内の要素にのみアクセスでき、要素を直接変更することはできません.C++で文字列は変更可能です.(3)文字列接続、pythonでは2つの文字列の直接加算操作をサポートして文字列接続を行う
2.例題
2.1バイナリ加算
バイナリ文字列を与えて、彼らの和を返して、バイナリで表します.基本思想:2つの文字列を加算し、1つのシンボルビットflagを設定してキャリー情報の難点境界条件の決定:char=int(a[i])+int(b[i])+flag,chatの可能な値:0,1,2,3(1)i=[-1,-2,-l_min]遍歴加算1要素から短い文字列遍歴完了(2)i=[-l_min-1,-l_min-2 m,...,-l_max]:char=flag+int(a[i]),charの可能な値:0,1,2(3)最後にキャリーがあるかどうかを確認する必要があります
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
res=[]
l_a=len(a)
l_b=len(b)
l_min=min(l_a,l_b)
l_max=max(l_a,l_b)
flag=0
for i in range(-1,-l_min-1,-1):
char=int(a[i])+int(b[i])+flag
flag=0
if char==0:
res.append(0)
elif char==1:
res.append(1)
elif char==2:
res.append(0)
flag=1
else:
res.append(1)
flag=1
print (res,flag)
if l_a>l_b:
for i in range(-l_min-1,-l_max-1,-1):
#print(i,res,flag)
char=flag+int(a[i])
flag=0
if char==0:
res.append(0)
elif char==1:
res.append(1)
elif char==2 :
res.append(0)
flag=1
if l_a<l_b:
#print(l_min,l_max)
for i in range(-l_min-1,-l_max-1,-1):
#print(i,flag,res)
char=flag+int(b[i])
flag=0
if char==0:
res.append(0)
elif char==1:
res.append(1)
elif char==2:
res.append(0)
flag=1
#print(res,flag)
if flag==1:
res.append(1)
l_res=len(res)
res_s=""
for i in range(l_res-1,-1,-1):
res_s+=str(res[i])
return res_
2.2 strStrを実現する()
haystack文字列とneedle文字列を指定し、haystack文字列にneedle文字列が現れる最初の場所を見つけます.存在しない場合は0を返す.
考えて、haystack文字列を遍歴して、needle文字列の最初の文字を見つけて、それから順番に後ろに探して、すべてが一致してから結果を返します.
注意点:(1)needleが空の場合、-1を返します(1つの文字列に空の文字列が見つからないことを示します).0を返す(haysta[0]から始まる文字列が空の文字列に一致することを示す)–c++言語でこのように定義されている(2)両方が空の場合、0(3)len(haystack)を返す
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
l_s=len(haystack)
l_n=len(needle)
if l_n==0:
return 0
if l_s==0:
return -1
if l_s<l_n:
return -1
for i in range(l_s-l_n+1): # i:[0,1,...,l_s-l-n]
for j in range(l_n): # i:[0,1,...,l_n-1]l-s-l_n
#print(i,j)
if haystack[i+j]!=needle[j]:
break
if j==l_n-1:
return i
return -1
2.3最大共通接頭辞
文字列配列の最長の共通接頭辞を検索する関数を作成します.共通接頭辞が存在しない場合は、空の文字列「」を返してwin領域に共通接頭辞を保存し、最も短い文字列を探して、その要素を順次winに追加します.残りの文字列に接頭辞文字があるかどうかを判断します.
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
n=len(strs)
if n==0:
return ""
short_index=-1
l_min=float("INF")
for i in range(n):
if len(strs[i])<l_min:
l_min=len(strs[i])
short_index=i
win=""
i=0
while(i<l_min):
win=strs[short_index][:i+1]
for j in range(n):
if strs[j][:i+1]!=win:
return win[:i]
i+=1
return win