pythonソルバー配列中の2つの文字列の最小距離
タイトル:
配列stsが与えられています。データはすべて文字列で、二つの文字列str 1、str 2が与えられています。この2つの文字列がsts配列にある場合、それらの間の最小距離を返します。どちらかが中にいない場合、-1に戻ります。2つの文字列が等しい場合、0を返します。
例えば、「*」、「3」、「5」、「10」、「9」、「7」、「1」、「*」の2つの文字列を与え、関数によって3を返します。
二つの方法があります。
方法1:
配列stsを経て、二つのstr 1とstr 2の位置を記録します。最小の距離の数字を求める。このようにする時間の複雑さはo(n^2)です。
方法2:
検索の回数が非常に多い場合は、クエリの効率を向上させるために、Hashテーブルを作成し、クエリー毎の時間複雑度をo(1)に下げる。
Pythonの内蔵dictタイプはハッシュ・テーブルであり、実装方法もhashテーブルであり、クエリの時間複雑さはo(1)である。ハッシュ・テーブルの構造も様々です。
例えば、Hashテーブルを構成し、key値はstsの各文字列であり、value値はhashテーブルであり、その中には他の文字列までの最小距離が格納されている。
コードにすると、hash_です。テーブル={*}:{3}:1、“5”:1,“10”:2,“9”:3,“7”:2,“1”:1}
もちろんこの方法の空間複雑度はo(^2)です。
コード:
配列stsが与えられています。データはすべて文字列で、二つの文字列str 1、str 2が与えられています。この2つの文字列がsts配列にある場合、それらの間の最小距離を返します。どちらかが中にいない場合、-1に戻ります。2つの文字列が等しい場合、0を返します。
例えば、「*」、「3」、「5」、「10」、「9」、「7」、「1」、「*」の2つの文字列を与え、関数によって3を返します。
二つの方法があります。
方法1:
配列stsを経て、二つのstr 1とstr 2の位置を記録します。最小の距離の数字を求める。このようにする時間の複雑さはo(n^2)です。
方法2:
検索の回数が非常に多い場合は、クエリの効率を向上させるために、Hashテーブルを作成し、クエリー毎の時間複雑度をo(1)に下げる。
Pythonの内蔵dictタイプはハッシュ・テーブルであり、実装方法もhashテーブルであり、クエリの時間複雑さはo(1)である。ハッシュ・テーブルの構造も様々です。
例えば、Hashテーブルを構成し、key値はstsの各文字列であり、value値はhashテーブルであり、その中には他の文字列までの最小距離が格納されている。
コードにすると、hash_です。テーブル={*}:{3}:1、“5”:1,“10”:2,“9”:3,“7”:2,“1”:1}
もちろんこの方法の空間複雑度はo(^2)です。
コード:
def min_distance_1(strs, str1, str2):
'''
, 1, o(n^2)
:param strs:
:param str1:
:param str2:
:return: strs , -1,
'''
if str1 not in strs or str2 not in strs:
return -1
if str1 == str2:
return 0
dist, min = 1, len(strs)
pos1, pos2 = 0, len(strs)
for i in xrange(0, len(strs)):
if str1 == strs[i]:
pos1 = i
for j in xrange(0, len(strs)):
if str2 == strs[j]:
pos2 = j
dist = abs(pos1 - pos2)
if dist < min:
min = dist
return min
def min_distance_2(strs, str1, str2):
'''
, 2, , o(1)。
Python dict , hash , o(1)。 :
, Hash ,key strs ,value hash , 。
:hash_table = {"*":{"3":1, "5":1, "10":2, "9":3, "7":2, "1":1}}
o(n^2)
:param strs: ['*','3','*','5','10','9','7','1','*']
:param str1: , '*'
:param str2: , '9'
:return: strs , -1,
'''
if str1 not in strs or str2 not in strs:
return -1
if str1 == str2:
return 0
def create_hash(strs): # hash
strs_set = list(set(strs))
dist_hash = {}
for i in xrange(0, len(strs_set)):
temp = {}
for j in xrange(0, len(strs_set)):
if strs_set[i] != strs_set[j]:
dist = min_distance_1(strs, strs_set[i], strs_set[j])
temp[strs_set[j]] = dist
dist_hash[strs_set[i]] = temp
return dist_hash
return create_hash(strs)[str1][str2]
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。