题目:
给定一个数组 strs,其中的数据都是字符串,给定两个字符串 str1,str2。如果这两个字符串都在 strs数组中,就返回它们之间的最小距离;如果其中任何一个不在里面,则返回 -1;如果两个字符串相等,则返回 0。
例如:给定[‘*','3','*','5','10','9','7','1','*'],再给定两个字符串'* ‘和'9',通过函数求得返回值 3。
分析:有两种方法
方法1:
遍历数组 strs,分别记录两个 str1 和 str2 的位置。求得最小的一个距离数字。这样做时间复杂度为 o(n^2)。
方法2:
如果查询的次数非常多,为了提高查询的效率,构造Hash表,把每次查询的时间复杂度下降到 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)
代码:
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]
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
华山资源网 Design By www.eoogi.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
华山资源网 Design By www.eoogi.com
暂无评论...
更新日志
2024年09月23日
2024年09月23日
- 华少翌.2005-华少翌【中唱艺能】【WAV+CUE】
- 群星《十二女声Ⅱ》[WAV/CUE/分轨][527MB]
- 大自然音乐系列《漫步在山裡》[WAV/CUE/分轨][502.8MB]
- 大自然音乐系列《星光夜语》[WAV/CUE/分轨][453.3MB]
- 史依弘《史依弘交响乐京剧演唱专辑HQ》头版限量编号[WAV+CUE]
- 曼丽2020《女人三十风继续吹》HQCD[WAV+CUE]
- 曼丽2021《女人三十2雾之恋》HQCD[WAV+CUE]
- 隔壁老樊.2019-我曾【好听音乐】【FLAC分轨】
- 高林生.1993-牵挂你的人是我【白天鹅】【WAV+CUE】
- 洪卓立.2012-找个懂我的女孩(国专)【英皇娱乐】【WAV+CUE】
- 曼丽2022《女人三十3晚秋》HQCD[WAV+CUE]
- 曼丽2018《女人三十4冬天》HQCD[WAV+CUE]
- 柏菲-《好歌30年壹》限量开盘母带ORMCD[低速原抓WAV+CUE]
- 大自然音乐系列《水舞》[WAV/CUE/分轨][424.3MB]
- 大自然音乐系列《星光夜语》[WAV/CUE/分轨][453.3MB]