用 Python 实现 str.find() 方法

qiuyouzhi

用 Python 实现 str.find() 方法

思路：

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

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

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

复制代码

当场超时。。。

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

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

一个指向末尾。

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

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

1. def find(x,sub,start = None, end = None):
   
2.     # 判断start和end,不多说
   
3.     if len(sub) <= 0:
   
4.         return 0
   
5.     if start != None and end != None:res = x[start:end]
   
6.     elif start != None:res = x[start:]
   
7.     elif end != None:res = x[:end]
   
8.     else:res = x[:]
   
9.     # 先简单判断一下，不在里面直接返回-1
   
10.     if sub not in res:
    
11.         return -1
    
12.     i,j = 0,len(res)-1 # 一个指向开头，一个指向结尾
    
13.     while j >= i:
    
14.         if sub[0] == res[i]:
    
15.             return i
    
16.         elif sub[0] == res[j]:
    
17.             return j
    
18.         
    
19.         if sub[0] != res[i]:
    
20.             i += 1
    
21.         if sub[0] != res[j]:
    
22.             j -= 1
    
23.     return -1
    
24. 
    
25. 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.     # 先简单判断一下，不在里面直接返回-1
   
2.     if sub not in res:
   
3.         return -1

复制代码

这段去掉，降低效率

一个账号

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

对滴

永恒的蓝色梦想

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

1. 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的快多了

一个账号

还是超时：

1. def find(x,sub,start = None, end = None):
   
2.     # 判断start和end,不多说
   
3.     if len(sub) <= 0:
   
4.         return 0
   
5.     if start != None and end != None:res = x[start:end]
   
6.     elif start != None:res = x[start:]
   
7.     elif end != None:res = x[:end]
   
8.     else:res = x[:]
   
9.     # 先简单判断一下，不在里面直接返回-1
   
10.     if sub not in res:
    
11.         return -1
    
12.     i,j = 0,len(res)-1 # 一个指向开头，一个指向结尾
    
13.     while j >= i:
    
14.         if sub[0] == res[i]:
    
15.             return i
    
16.         elif sub[0] == res[j]:
    
17.             return j
    
18.         
    
19.         if sub[0] != res[i]:
    
20.             i += 1
    
21.         if sub[0] != res[j]:
    
22.             j -= 1
    
23.     return -1
    
24. 
    
25. num = 100000000
    
26. 
    
27. print(find("a"*num+"b"+"a"*num, "b"))

复制代码