python求解数组中两个字符串的最小距离
题目：
给定一个数组 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]
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
Python语言描述连续子数组的最大和
题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学.今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决.但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止).你会不会被他忽悠住?(子向量的长度至少是1) 思路: 最大和连续子数组一定有如下几个特点: 1.第一个不为负数 2.如果前面数的累加值
-
Python实现二维有序数组查找的方法
本文实例讲述了Python实现二维有序数组查找的方法.分享给大家供大家参考,具体如下: 题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 这题目属于比较简单但又很不容易想到的,问了两个同学,大家一时都没有想出来怎么解决比较快.第一反应都是二分查找.对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路. 比较好的另一种思路是,首先选取数组右上角
-
python中找出numpy array数组的最值及其索引方法
在list列表中,max(list)可以得到list的最大值,list.index(max(list))可以得到最大值对应的索引 但在numpy中的array没有index方法,取而代之的是where,其又是list没有的 首先我们可以得到array在全局和每行每列的最大值(最小值同理) >>> a = np.arange(9).reshape((3,3)) >>> a array([[0, 1, 2], [9, 4, 5], [6, 7, 8]]) >>&
-
Python实现查找数组中任意第k大的数字算法示例
本文实例讲述了Python实现查找数组中任意第k大的数字算法.分享给大家供大家参考,具体如下: 模仿partion方法,当high=low小于k的时候,在后半部分搜索,当high=low大于k的时候,在前半部分搜索.与快排不同的是,每次都减少了一半的排序. def partitionOfK(numbers, start, end, k): if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end
-
Python实现返回数组中第i小元素的方法示例
本文实例讲述了Python实现返回数组中第i小元素的方法.分享给大家供大家参考,具体如下: #! /usr/bin/env python #coding=utf-8 #期望为线性时间的选择算法 import random class RandomSelect(object): def Partition(self,a, p, r): x=a[r] i=p-1 for j in range(p, r): '''如果a[j]>x,则只需将j的值加1即可使循环不变量继续保持; 如果a[j]<=x,则
-
Python实现在某个数组中查找一个值的算法示例
第一种算法思路: 第一步:随机出来一个数组的下标 第二步:判断下标对应的值是否等于被查找的值,是的话终止,已找到,否的话转第三步. 第三步:判断是否随机完数组的所有下标,是的话终止,没找到,否的话转第一步. 代码如下: #本程序的功能是在字典中查找存在某个值 import random di = {'a':1,'b':2,'c':3,'d':4,'e':5,'f':6} key = 2 di1 = {} while True: tmp = random.choice(di.keys()) #随机
-
python求最大连续子数组的和
抛出问题: 求一数组如 l = [0, 1, 2, 3, -4, 5, -6],求该数组的最大连续子数组的和 如结果为[0,1,2,3,-4,5] 的和为7 问题分析: 这个问题很简单,直接暴力法,上代码. # -*- coding:utf-8 -*- # 日期:2018/6/9 7:46 # Author:小鼠标 # 最大连续子数组的和 l = [0, 1, 2, 3, -4, 5, -6] # 暴力求解 def violence(l = []): maxVal = 0 x,y=0,0 for
-
Python实现找出数组中第2大数字的方法示例
本文实例讲述了Python实现找出数组中第2大数字的方法.分享给大家供大家参考,具体如下: 题目比较简单直接看实现即可,具体的注释在代码中都有: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出数组中第2大的数字 ''' def find_Second_large_num(num_list): ''''' 找出数组中第2大的数字 ''' #直接排序,输出倒数第二个数即可 tmp_list=sorted(num_lis
-
python求解数组中两个字符串的最小距离
题目: 给定一个数组 strs,其中的数据都是字符串,给定两个字符串 str1,str2.如果这两个字符串都在 strs数组中,就返回它们之间的最小距离:如果其中任何一个不在里面,则返回 -1:如果两个字符串相等,则返回 0. 例如:给定['*','3','*','5','10','9','7','1','*'],再给定两个字符串'* '和'9',通过函数求得返回值 3. 分析:有两种方法 方法1: 遍历数组 strs,分别记录两个 str1 和 str2 的位置.求得最小的一个距离数字.这样做
-
利用python求解物理学中的双弹簧质能系统详解
前言 本文主要给大家介绍了关于利用python求解物理学中双弹簧质能系统的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定.假定没有外力时,两个弹簧的长度为L1和L2. 由于两物体有重力,那么在平面上形成摩擦力,那么摩擦系数分别为b1和b2.所以可以把微分方程写成这样: 这是一个二阶的微分方程,为了使用python来求解,需要把它转换为一阶微分方程
-
对python numpy数组中冒号的使用方法详解
python中冒号实际上有两个意思:1.默认全部选择:2. 指定范围. 下面看例子 定义数组 X=array([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16],[17,18,19,20]]) 输出为5x4二维数组 第一种意思,默认全部选择: 如,X[:,0]就是取矩阵X的所有行的第0列的元素,X[:,1] 就是取所有行的第1列的元素 第二种意思,指定范围,注意这里含左不含右 如,X[:, m:n]即取矩阵X的所有行中的的第m到n-1列数据,含左不含右
-
python 列表,数组,矩阵两两转换tolist()的实例
通过代码熟悉过程: # -*- coding: utf-8 -*- from numpy import * a1 =[[1,2,3],[4,5,6]] #列表 print('a1 :',a1) #('a1 :', [[1, 2, 3], [4, 5, 6]]) a2 = array(a1) #列表 -----> 数组 print('a2 :',a2) #('a2 :', array([[1, 2, 3],[4, 5, 6]])) a3 = mat(a1) #列表 ----> 矩阵 print(
-
Python查找数组中数值和下标相等的元素示例【二分查找】
本文实例讲述了Python查找数组中数值和下标相等的元素.分享给大家供大家参考,具体如下: 题目描述: 假设一个单调递增的数组中的每个元素都是整数并且是唯一的.请编程实现一个函数,找出数组中任意一个数值等于其下标的元素,例如在数组[-3,-1,1,3,5]中,3和他的下标相等. 采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标.如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找. 算法示例: # -*-
-
python numpy数组中的复制知识解析
这篇文章主要介绍了python numpy数组中的复制知识解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 vector = numpy.array([5, 10, 15, 20]) equal_to_ten_or_five = (vector == 10) | (vector == 5) vector[equal_to_ten_or_five] = 50 print(vector) 第一次看到这个的时候一脸懵逼,后来分析了下懂了下面记录下,
-
python不相等的两个字符串的 if 条件判断为True详解
今天遇到一个非常基础的问题,结果搞了好久好久.....赶快写一篇博客记录一下: 本来两个不一样的字符串,在if 的条件判断中被判定为True,下面是错误的代码: test_str = 'happy' if test_str == 'good' or 'happy': #这样if判断永远是True,写法错误 print('aa') else: print('bbbb') 这是正确的代码: test_str = 'happy' if test_str == 'good' or test_str ==
-
Python求解排列中的逆序数个数实例
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序. 一个排列中逆序的总数就称为这个排列的逆序数. 一个排列中所有逆序总数叫做这个排列的逆序数. 也就是说,对于n个不同的元素,先规定各元素之间有一个标准次序(例如n个 不同的自然数,可规定从小到大为标准次序),于是在这n个元素的任一排列中,当某两个元素的先后次序与标准次序不同时,就说有1个逆序. 一个排列中所有逆序总数叫做这个排列的逆序数. Python代码: def inverse_number(s
-
利用python查看数组中的所有元素是否相同
不知道大家有没有过这种经历,就是想要判断两个数组运算后得到的新数组中的各个元素值是否相同.这里给出一种使用np.unique()的方法,代码如下: import numpy as np class Debug: @staticmethod def isAllElementSame(): x1 = np.array([[1, 2, 3], [3, 4, 5], [6, 7, 8]]) x2 = np.array([[81., 162., 243., ], [243., 324., 405.], [
-
Matlab求解数组中的最大值及它所在的具体位置
在使用Matlab肯定会碰到Matlab求解数组中的最大值以及它所在的位置的问题.博主开始用循环的方法找,既浪费时间又消耗资源,后面查找后才发现有简单快速的方法.下面就简单介绍一下这种方法. 1.电脑环境 电脑环境:Windows 10 教育版 MATLAB:MATLAB R2014a 2.方法 1.1.一维数组 在Matlab随机生成一维数组或者手动输入 a = [1,9,24,8,7,16] [m,p]=max(a) 利用max函数,将一维数据放入max(一维数组)中 最终利用Max函数输出