用 Python 实现 str.find() 方法

qiuyouzhi

用 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[start:end]
    elif start != None:res = x[start:]
    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[0] == res[i]:
            return i
        elif sub[0] == res[j]:
            return j
        
        if sub[0] != res[i]:
            i += 1
        if sub[0] != res[j]:
            j -= 1
    return -1

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

一个账号

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

输出：IndexError

预期输出：0

qiuyouzhi

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

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

已修改，现在试试？

一个账号

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

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

输出：0

预期输出：TypeError

qiuyouzhi

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

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

是类型不同就报TypeError是吗

永恒的蓝色梦想

    # 先简单判断一下，不在里面直接返回-1
    if sub not in res:
        return -1

这段去掉，降低效率

一个账号

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

对滴

永恒的蓝色梦想

这个双指针毫无意义
用了双指针，

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

就会超时
反正怎么着都超时，还不如不用

永恒的蓝色梦想

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

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

qiuyouzhi

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

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

qiuyouzhi

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

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

一个账号

还是超时：

def find(x,sub,start = None, end = None):
    # 判断start和end,不多说
    if len(sub) <= 0:
        return 0
    if start != None and end != None:res = x[start:end]
    elif start != None:res = x[start:]
    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[0] == res[i]:
            return i
        elif sub[0] == res[j]:
            return j
        
        if sub[0] != res[i]:
            i += 1
        if sub[0] != res[j]:
            j -= 1
    return -1

num = 100000000

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