论坛 › Python交流 › 用 Python 实现 str.find() 方法

qiuyouzhi 发表于 2020-3-21 21:17:29

用 Python 实现 str.find() 方法

本帖最后由 qiuyouzhi 于 2020-3-21 21:31 编辑

用 Python 实现 str.find() 方法

思路：

最开始是想挨个遍历（很zz，不要学），

然后简单一些的都成功了，结果：

print(find('1'*1000010000+'2', '2'))

当场超时。。。

痛定思痛，改了一个思路：

用两个指针（双指针，会的可以略过），一个指向开头，

一个指向末尾。

如果开头没找到，开头指针就指向后一个元素，

如果结尾没找到，就指向前一个元素。

def find(x,sub,start = None, end = None):
    # 判断start和end,不多说
    if len(sub) <= 0:
      return 0
    if start != None and end != None:res = x
    elif start != None:res = x
    elif end != None:res = x[:end]
    else:res = x[:]
    # 先简单判断一下，不在里面直接返回-1
    if sub not in res:
      return -1
    i,j = 0,len(res)-1 # 一个指向开头，一个指向结尾
    while j >= i:
      if sub == res:
            return i
      elif sub == res:
            return j
      
      if sub != res:
            i += 1
      if sub != res:
            j -= 1
    return -1

print(find("123123", ""))

一个账号 发表于 2020-3-21 21:30:20

本帖最后由 一个账号 于 2020-3-22 09:40 编辑

输入：find("123123", "")

输出：IndexError

预期输出：0

qiuyouzhi 发表于 2020-3-21 21:32:16

一个账号 发表于 2020-3-21 21:30
解答错误：

输入：find("123123", "")


已修改，现在试试？

一个账号 发表于 2020-3-21 21:50:18

本帖最后由 一个账号 于 2020-3-22 09:40 编辑

qiuyouzhi 发表于 2020-3-21 21:32
已修改，现在试试？

输入：find(["a"], "a")

输出：0

预期输出：TypeError

qiuyouzhi 发表于 2020-3-21 21:56:37

一个账号 发表于 2020-3-21 21:50
解答错误：

输入：find(["a"], "a")


是类型不同就报TypeError是吗

永恒的蓝色梦想 发表于 2020-3-21 22:04:56

    # 先简单判断一下，不在里面直接返回-1
    if sub not in res:
      return -1这段去掉，降低效率

一个账号 发表于 2020-3-21 22:06:27

qiuyouzhi 发表于 2020-3-21 21:56
是类型不同就报TypeError是吗

对滴

永恒的蓝色梦想 发表于 2020-3-21 22:08:05

这个双指针毫无意义
用了双指针，print(find('1'*500005000+'2'+'1'*500005000,'2'))就会超时
反正怎么着都超时，还不如不用{:10_248:}

永恒的蓝色梦想 发表于 2020-3-21 22:12:51

一个账号 发表于 2020-3-21 22:06
你怎么知道的？

in本质上就是遍历一遍，后面再遍历一边，浪费资源

qiuyouzhi 发表于 2020-3-22 07:49:23

永恒的蓝色梦想 发表于 2020-3-21 22:08
这个双指针毫无意义
用了双指针，就会超时
反正怎么着都超时，还不如不用

。。。
早上起来，这么一看。。。
头都大了，但是这也让我有了一个新的想法！
我先去试试能不能实现

qiuyouzhi 发表于 2020-3-22 09:42:58

一个账号 发表于 2020-3-22 09:42
还是 str 的 find 快：

是啊
人家用C写的
比我们Python的快多了

一个账号 发表于 2020-3-27 11:32:54

还是超时：

def find(x,sub,start = None, end = None):
    # 判断start和end,不多说
    if len(sub) <= 0:
      return 0
    if start != None and end != None:res = x
    elif start != None:res = x
    elif end != None:res = x[:end]
    else:res = x[:]
    # 先简单判断一下，不在里面直接返回-1
    if sub not in res:
      return -1
    i,j = 0,len(res)-1 # 一个指向开头，一个指向结尾
    while j >= i:
      if sub == res:
            return i
      elif sub == res:
            return j
      
      if sub != res:
            i += 1
      if sub != res:
            j -= 1
    return -1

num = 100000000

print(find("a"*num+"b"+"a"*num, "b"))

查看完整版本: 用 Python 实现 str.find() 方法