鱼C论坛Python精英挑战赛（第四季热身）评选结果

jerryxjr1220

本期热身赛有SixPy，wyp02033，yjsx86，開汧吣伈，JAY饭，Cathaysian，蓝色王魂，Bean_Wei，brank等多位鱼油参与答题。

根据评比规则：“答案正确”、“效率高”、“代码优雅”的原则，最终评选 蓝色王魂 为最终优胜者，可作为第四季第一期的擂主参与精英挑战赛。

@小甲鱼 @～风介～ @冬雪雪冬 @SixPy

jerryxjr1220

贴一下我的解题思路及参考解答。
常规解答：循环
自然是运用循环，遍历所有字符串，先取得局部不重复字符串，再比较全局不重复字符串，如果局部解>全局解，则替换。
这个思路也是很多参赛鱼油运用的，只是大多数鱼油都用了双层循环，其实是不需要的，单层循环就可以解决了，这样效率可以快一个数量级。

1. def longest_substring_1(string):
   
2.         longest = ''
   
3.         sub = string[0]
   
4.         for i in range(1,len(string)):
   
5.                 if string[i] in sub:
   
6.                         longest = sub if len(sub)>len(longest) else longest
   
7.                         sub=string[i]
   
8.                 else:
   
9.                         sub+=string[i]
   
10.         longest = sub if len(sub)>len(longest) else longest
    
11.         return len(longest)

复制代码

感谢@shuo指出错误，应该用列表储存sub字符串，纠正一下：

1. def longest_substring_1(string):
   
2.     longest = ''
   
3.     sub = [string[0]]
   
4.     for i in range(1,len(string)):
   
5.         for j in range(len(sub)):
   
6.             if string[i] in sub[j]:
   
7.                 longest = sub[j] if len(sub[j])>len(longest) else longest
   
8.                 sub[j]=string[i]
   
9.             else:
   
10.                 sub[j]+=string[i]
    
11.                 sub.append(string[i])
    
12.         sub=list(set(sub))
    
13.     for j in range(len(sub)):
    
14.         longest = sub[j] if len(sub[j])>len(longest) else longest
    
15.     return longest

复制代码

第二种思路：递归
递归的好处是代码可以比较简洁，但是效率方面来说，肯定是不如循环来得高效，但是对于我们这种小题目来说，递归也是不错的解决方案。不过递归对于不是新人来说，还是不容易掌握，希望多通过练习加强对递归程序的理解。

1. def longest_substring_2(string,sub='',longest = ''):
   
2.         if not string: return len(longest) if len(longest)>len(sub) else len(sub)
   
3.         if string[0] in sub: return longest_substring_2(string[1:],string[0],longest if len(longest)>=len(sub) else sub)
   
4.         return longest_substring_2(string[1:],sub+string[0],longest)

复制代码

递归法只有短短的四行，第一行是定义函数，第二行定义递归结束的条件，第三行是定义子串中有重复字符时的处理，第四行是定义一般情况下无重复字符子串的处理。是不是很简单？

再来看一个极限压缩的写法，同样是递归，但是运用python的语法糖把递归嵌套来写，一行代码输出。

1. def longest_substring_3(string,sub='',longest = ''): return (len(longest) if len(longest)>len(sub) else len(sub)) if not string else ((longest_substring_3(string[1:],string[0],longest if len(longest)>=len(sub) else sub)) if string[0] in sub else longest_substring_3(string[1:],sub+string[0],longest))

复制代码

上两种方法同样也和循环一样，应该用列表储存子字符串，所以也要相应调整，我偷懒了，后续留给有兴趣的鱼油来改吧。

解题愉快！

SixPy

@jerryxjr1220 为什么删了原贴？

蓝色王魂

感谢论坛评选我为获胜者，其实我只是个刚学小甲鱼教程不久的萌新，希望后面攻擂的各位大神手下留情

jerryxjr1220

SixPy 发表于 2017-11-24 10:45
@jerryxjr1220 为什么删了原贴？

原帖忘记设置竞猜帖了，所以重新写了。

蓝色王魂

感谢鱼c论坛！

SixPy

jerryxjr1220 发表于 2017-11-24 10:53
原帖忘记设置竞猜帖了，所以重新写了。

你选的优胜者，他的结果的是错的。

abcabcbbabcdefg ('abcdefg', 7)
正确长度是7，而优胜者的结果是6

jerryxjr1220

SixPy 发表于 2017-11-24 11:30
你选的优胜者，他的结果的是错的。

abcabcbbabcdefg ('abcdefg', 7)

好吧，我测试的几个结果到都是对的。
不过反正是热身赛就算了，也没多大影响。就当鼓励新人了。

蓝色王魂

SixPy 发表于 2017-11-24 11:30
你选的优胜者，他的结果的是错的。

abcabcbbabcdefg ('abcdefg', 7)

感谢聚聚指点，我这个函数的问题我知道了，因为我的终止值计算有问题，导致我无法经过列表最后一个元素所以说我的函数当所需字符串在最末尾的时候会报错。

1. def longest_substring(string):
   
2.     length = len(string)
   
3.     for i in range(1, length + 1):
   
4.         for n in range(length - i + 1):
   
5.             char = list(string[n:n + i])
   
6.             if len(char) == len(set(char)):
   
7.                 result = i
   
8.                 break
   
9.     return result
   

复制代码

改为这样就好了，再次感谢聚聚指点，也感谢鱼c论坛让我侥幸当上擂主。

SixPy

蓝色王魂 发表于 2017-11-24 18:51
感谢聚聚指点，我这个函数的问题我知道了，因为我的终止值计算有问题，导致我无法经过列表最后一个元素所 ...

继续努力~

shuo

jerryxjr1220 发表于 2017-11-24 09:01
贴一下我的解题思路及参考解答。
常规解答：循环
自然是运用循环，遍历所有字符串，先取得局部不重复字符 ...

第一个 循环的答案是错误的，并不能访问所有的子字符串，会出现一些遗漏。  例如字符串 abadababa

按照第一个计算，答案是2 。  其实正确答案应该是3 吧

刚学的新手， 如有疏漏 敬请谅解。

jerryxjr1220

shuo 发表于 2017-11-27 15:06
第一个 循环的答案是错误的，并不能访问所有的子字符串，会出现一些遗漏。  例如字符串 abadababa

...

感谢指出错误，是的，是我疏忽了，应该用列表来储存，而不单单是用字符串。

1. def longest_substring_1(string):
   
2.     longest = ''
   
3.     sub = [string[0]]
   
4.     for i in range(1,len(string)):
   
5.         for j in range(len(sub)):
   
6.             if string[i] in sub[j]:
   
7.                 longest = sub[j] if len(sub[j])>len(longest) else longest
   
8.                 sub[j]=string[i]
   
9.             else:
   
10.                 sub[j]+=string[i]
    
11.                 sub.append(string[i])
    
12.         sub=list(set(sub))
    
13.     for j in range(len(sub)):
    
14.         longest = sub[j] if len(sub[j])>len(longest) else longest
    
15.     return longest

复制代码

jerryxjr1220

shuo 发表于 2017-11-27 15:06
第一个 循环的答案是错误的，并不能访问所有的子字符串，会出现一些遗漏。  例如字符串 abadababa

...

同样的问题在递归程序里面也存在，应该也是用列表储存，而不能用字符串

shuo

jerryxjr1220 发表于 2017-11-27 15:38
同样的问题在递归程序里面也存在，应该也是用列表储存，而不能用字符串

嗯嗯， 递归的暂时还看不懂。 哈哈