題目：

成都創(chuàng)新互聯(lián)公司專業(yè)成都網(wǎng)站設(shè)計、成都做網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)，集網(wǎng)站策劃、網(wǎng)站設(shè)計、網(wǎng)站制作于一體，網(wǎng)站seo、網(wǎng)站優(yōu)化、網(wǎng)站營銷、軟文營銷等專業(yè)人才根據(jù)搜索規(guī)律編程設(shè)計，讓網(wǎng)站在運(yùn)行后，在搜索中有好的表現(xiàn)，專業(yè)設(shè)計制作為您帶來效益的網(wǎng)站！讓網(wǎng)站建設(shè)為您創(chuàng)造效益。

給定一個數(shù)組 strs，其中的數(shù)據(jù)都是字符串，給定兩個字符串 str1，str2。如果這兩個字符串都在 strs數(shù)組中，就返回它們之間的最小距離；如果其中任何一個不在里面，則返回 -1；如果兩個字符串相等，則返回 0。

例如：給定[‘*','3','*','5','10','9','7','1','*']，再給定兩個字符串'* ‘和'9'，通過函數(shù)求得返回值 3。

分析：有兩種方法

方法1：

遍歷數(shù)組 strs，分別記錄兩個 str1 和 str2 的位置。求得最小的一個距離數(shù)字。這樣做時間復(fù)雜度為 o(n^2)。

方法2：

如果查詢的次數(shù)非常多，為了提高查詢的效率，構(gòu)造Hash表，把每次查詢的時間復(fù)雜度下降到 o(1)。
Python 的內(nèi)置 dict 類型就是哈希表，實(shí)現(xiàn)方法也是hash 表，其查詢的時間復(fù)雜度就是 o(1)。哈希表的構(gòu)造也分很多種：
比如，構(gòu)造 Hash 表，key值是strs中的每一個字符串，value值是一個hash表，里面存放著該字符串到其它字符串的最小距離。
寫成代碼就是：hash_table = {“*”:{“3”:1, “5”:1, “10”:2, “9”:3, “7”:2, “1”:1}}
當(dāng)然這種方法的空間復(fù)雜度是 o(n^2)

代碼： 

 def min_distance_1(strs, str1, str2):
  '''
  數(shù)組中兩個字符串的最小距離，這是方法1，時間復(fù)雜度 o(n^2)
  :param strs: 給定的數(shù)組中存放有多個字符串
  :param str1: 第一個字符串
  :param str2: 第二個字符串
  :return: 如果其中給定的一個字符串不在數(shù)組 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):
  '''
  數(shù)組中兩個字符串的最小距離，這是方法2，如果查詢的次數(shù)非常多，把每次查詢的時間復(fù)雜度下降到 o(1)。
  Python 的內(nèi)置 dict 類型就是哈希表，實(shí)現(xiàn)方法也是hash 表，其查詢的時間復(fù)雜度就是 o(1)。哈希表的構(gòu)造也分很多種：
  比如，構(gòu)造 Hash 表，key值是strs中的每一個字符串，value值是一個hash表，里面存放著該字符串到其它字符串的最小距離。
   寫成代碼就是：hash_table = {"*":{"3":1, "5":1, "10":2, "9":3, "7":2, "1":1}}
  當(dāng)然這種方法的空間復(fù)雜度是 o(n^2)
  :param strs: 給定的數(shù)組中存放有多個字符串['*','3','*','5','10','9','7','1','*']
  :param str1: 第一個字符串, '*'
  :param str2: 第二個字符串, '9'
  :return: 如果其中給定的一個字符串不在數(shù)組 strs 中，那么返回-1，否則返回兩個字符串之間的最小間距
  '''
  if str1 not in strs or str2 not in strs:
   return -1
  if str1 == str2:
   return 0

  def create_hash(strs): # 創(chuàng)建 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]

網(wǎng)頁名稱：python求解數(shù)組中兩個字符串的最小距離-創(chuàng)新互聯(lián)
本文地址：http://www.chinadenli.net/article14/djdsde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計公司、手機(jī)網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計、網(wǎng)站改版、企業(yè)網(wǎng)站制作、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)