零基础python刷leetcode -- 3. Longest

作者: 三也视界 | 来源:发表于2017-11-27 01:24 被阅读176次

算法很重要，但是每天也需要学学python，于是就想用python刷leetcode 的算法题，和我一起开始零基础python刷leetcode之旅吧。如有不对的地方，希望指正，万分感谢~~

题目

3. Longest Substring Without Repeating Characters

最长的不重复子字符串的长度

题目解析

题目是大概意思就是找出最长的不重复子字符串的长度。

还是老规矩，先来过一些python基础知识，老手请自动忽略：

python的集合Set

Set 是没有重复元素的集合，python里用{}大括号表示，和字典一样，为了区分，初始化空的集合只能通过set()操作，而{}表示空的字典。

set无序排序且不重复，是可变的，有add（），remove（）等方法。既然是可变的，所以它不存在哈希值。基本功能包括关系测试和消除重复元素. 集合对象还支持union(联合), intersection(交集), difference(差集)和sysmmetric difference(对称差集)等数学运算.

sets 支持 x in set, len(set),和 for x in set。作为一个无序的集合，sets不记录元素位置或者插入点。因此，sets不支持 indexing, 或其它类序列的操作。

frozenset是冻结的集合，它是不可变的，存在哈希值，好处是它可以作为字典的key，也可以作为其它集合的元素。缺点是一旦创建便不能更改，没有add，remove方法。这里就不展开讲了。

初始化

>>> s= set("hello")
{'l', 'h', 'e', 'o'}
>>> type(s)
<type 'set'>

集合元素的增加

集合元素的增加支持两种类型，单个元素的增加用add方法，对序列的增加用update方法。相当于Java中的list的add 和addAll。简单理解就是update添加的会拆分。

>>> a={1,2}
>>> a.update([3,4],[3,1,6])
>>> a
{1, 2, 3, 4, 6}
>>> a.update("python&&java")
>>> a
{'h', 1, 2, 3, 4, 'o', 6, 'j', 'n', 'a', 'v', 'p', 't', '&', 'y'}
>>> a.add("hello")
>>> a
{'h', 1, 2, 3, 4, 'o', 6, 'j', 'n', 'a', 'hello', 'v', 'p', 't', '&', 'y'}

上面的程序多执行几次，我们发现每次打印的顺序都不一样。为什么呢？

因为Set是无序的。怎么去理解这个无序呢？

set的“无序”是相对于平衡二叉树而言的。但是，基于平衡二叉树的set(如c++中用红黑树实现的set和python中的orderedset)是有序的。由于二叉搜索树的特点，可以很轻松的找到任意节点的前驱和后继节点，所以算是“有序”的。
而set基于哈希表实现，存取时间可看做O(1)，但是没有办法高效的完成顺序相关的操作(比如找前驱后继，最大最小值等等)，所以认为是“无序”的。

集合删除单个元素

集合删除单个元素有两种方法，set.discard(x)和set.remove(x)。两者的区别是如果元素不在原集合中时是否会抛出异常。set.remove会抛出KeyError错误,而set.discard不会抛出异常。

>>> a={1,2,3,4}
>>> a.discard(1)
>>> a
{2, 3, 4}
>>> a.discard(1)
>>> a
{2, 3, 4}
>>> a.remove(1)
Traceback (most recent call last):
  File "C:/Users/Philos/PycharmProjects/leetcode/leetcode_python/__init__.py", line 6, in <module>
    a.remove(1)
KeyError: 1

集合也支持pop()方法，不过由于集合是无序的，pop返回的结果不能确定，且当集合为空时调用pop会抛出KeyError错误，可以调用clear方法来清空集合

>>>a={10,"p","y","t","h","o","n",0.8,0}
>>> a.pop()
>>> a
{0, 'h', 10, 'y', 't', 'o', 'n', 'p'}
>>> a.pop()
>>> a
{'h', 10, 'y', 't', 'o', 'n', 'p'}
>>> a.pop()
>>> a
{10, 'y', 't', 'o', 'n', 'p'}

>>>a={1,15,8,25}
>>> a.pop()
>>> a
{1, 25, 15}
>>> a.pop()
>>> a
{25, 15}
>>> a.pop()
>>> a
{15}

多次执行程序，发现上面一组打印是无序的，下面一组是有序的(多次执行结果都一样)。真的是这样吗？

其实set内部保存的数据都是通过哈希值排序的。为了帮助理解，我们可以简单的认为hashCode%size=0的key排在最前，hashCode%size=1的其次，以此类推()。

image.png

Java里面计算字符串hash方法是（python的应该类似）：

公式: s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]

来看一个例子：

计算字符串”Lee”的哈希值
‘L’的ASCII码为76，’e’的ASCII码为101
多少个字符就需要for循环几次，例子是3次
h=31*0+76=76
h=31*76+101=2457
h=31*2457+101=76268
所以字符串”Lee”的哈希码就是76268

而1 ~ 4对应的ascii码对应49~52，相当于一个字符。于是有如下计算：

0*31 +49 =49
0*31 +50 =50
0*31 +51 =51
0*31 +52 =52

然后根据hashCode%size排序的到49 %4 = 1 ； 50 %4 = 2以此类推，{1,15,8,25} 对应排序{8,1,25,15},验证一致。但是看下上面的1～4那么按照理由，这个4应该排序在最前面才对？其实值>=size的都会排在最前面,如果值>=size，当元素个数size的变化会引起排序的变化。

python计算hash值是有一些算法去计算的，所以对于一些数字还是存在一些规律的，说了这么多，就是为了引出一句话，这个按照顺序只是碰巧的（不要打我。。。。。。我对自己也是很无语，啊哈哈），实在要去深究，你可以看下计算hash值的这些算法(hashlib模块)：'md5', 'sha1', 'sha224', 'sha256', 'sha384', 'sha512', 'new', 'algorithms_guaranteed', 'algorithms_available', 'pbkdf2_hmac'

引用知乎一段话：

hash（散列、杂凑）函数，是将任意长度的数据映射到有限长度的域上。直观解释起来，就是对一串数据m进行杂糅，输出另一段固定长度的数据h，作为这段数据的特征（指纹）。也就是说，无论数据块m有多大，其输出值h为固定长度。到底是什么原理？将m分成固定长度（如128位），依次进行hash运算，然后用不同的方法迭代即可（如前一块的hash值与后一块的hash值进行异或）。如果不够128位怎么办？用0补全或者用1补全随意，算法中约定好就可以了。

这个运用是很广的，比如很多网站或者银行不会保存用户密码，都是保存密码的hash值，只要按照约定好的算法就能解析出来正确的值。

集合多个元素的删除

set(['p', 'y', 't', 'h', 'o', 'n', 'j', 'a', 'v', 'a'])
>>> s -= set('java')#删除
>>> s
set(['p', 'y', 't', 'h', 'o', 'n'])
>>> del s #删除整个集合

条件判断（关系）

s = set(['p', 'y', 't', 'h', 'o', 'n'])
>>> 'j' in s
False
>>> 'p' in s
True
>>> 'a' not in s
True

集合等价/不等价

s = set('python')
t = set('java')
>>> s == t
False
>>> s != t
True

集合的运算看下图，这个是数学的东西了。。。不懂的自行百度：

image.png

集合子集/超集

>>> set('py') < set('python')
True
>>> set('python') >= set('no')
True

遍历

>>> s=set('python')
>>> s
{'t', 'h', 'p', 'y', 'n', 'o'}
>>> for i in s:
print(i) 

t
h
p
y
n
o

联合( | )

如图中的(1) + (2) + (3)部分

两个集合的联合是一个新集合，理解并集（数学的或）成员，方法为union()

>>>  s = set('python')
t = set('java')
b = s | t
>>> b
{'n', 'y', 'a', 'p', 'j', 'v', 'o', 'h', 't'}

>>>   b = s.union(t)
>>> b
{'n', 'y', 'a', 'p', 'j', 'v', 'o', 'h', 't'}

交集( & )

如图中的(2)部分

集合的 AND(或合取)操作。两个集合的交集是一个新集合，方法为intersection()

>>>  s = set('python')
t = set('pjavay')
b = s & t
print(b)
b = s.intersection(t)
print(b)
a = t.intersection(s)
print(a)

>>>  {'y', 'p'}
{'y', 'p'}
{'y', 'p'}

差补/相对补集( – )

如图中的(1) 或者 (3)部分

两个集合(s 和 t)的差补或相对补集是一个新集合，该集合中的元素，只属于集合 s，而不属于集合 t。方法difference()

>>>  s = set('python')
t = set('pjavay')
b = s - t
print(b)
b = s.difference(t)
print(b)

a = t.difference(s)
print(a)

>>>  {'n', 'o', 't', 'h'}
{'n', 'o', 't', 'h'}
{'v', 'j', 'a'}

可以看到s.difference(t) 和t.difference(s)的结果是不一样的，读者可以自行按照上面的图画出来之后，就可以知道，补集是不一样的。

对称差分( ^ )

如图中的(1) + (3)部分

和其他的布尔集合操作相似，对称差分是集合的 XOR(又称"异或 ").
两个集合(s 和 t)的对称差分是一个x新的集合 ,该集合中的元素，只能是属于集合 s 或者集合 t 的成员，不能同时属于两个集合。方法symmetric_difference().

>>>  s = set('python')
t = set('pjavay')
b = s ^ t
print(b)
b = s.symmetric_difference(t)
print(b)

a = t.symmetric_difference(s)
print(a)

>>>  {'v', 'n', 'h', 't', 'o', 'j', 'a'}
{'v', 'n', 'h', 't', 'o', 'j', 'a'}
{'o', 'v', 'n', 't', 'h', 'j', 'a'}   #其实和上面的结果是一致的，所以异或和顺序没有关系

python的字典

字典是另一种可变容器模型，且可存储任意类型对象。
字典的每个键值(key=>value)对用冒号(:)分割，每个对之间用逗号(,)分割，整个字典包括在花括号({})中。
键必须是唯一的，但值则不必。
值可以取任何数据类型，但键必须是不可变的，如字符串，数字或元组。

字典格式和初始化：

d = {key1 : value1, key2 : value2 }

>>>  dict1 = {}
print(type(dict1))
>>> <class 'dict'>

dict1 = {'python': '123', 'Java': 456, 'android': '123'}

访问字典里的值

取出字典a中键k的值，并将其从字典a中删除，如果字典a中没有键k，则返回值x

a.pop(k[, x])

取出字典a中键值对，并将其从字典a中删除

a.popitem()

>>>  dict1 = {'python': '123', 'Java': 456, 'android': '123'}
print("dict1 ['python']: ", dict1 ['python'])
print("dict1 ['Java']: ", dict1['Java'])
>>>  dict1 ['python']:  123
dict1 ['Java']:  456

＃如果ｋｅｙ不存在，是会抛出KeyError
>>>  dict1["C++"]
>>>  KeyError: 'C++'

修改字典

字典只能够修改它的值，key是无法修改的。dict.update(dict1)从dict1字典中更新dict字典，如果键相同则更新，dict中不存在则追加.

>>> dict1 = {'python': '123', 'Java': 456, 'android': '123'}
dict1 ['Java'] = "java"
print("dict1 ['python']: ", dict1 ['python'])
print("dict1 ['Java']: ", dict1['Java'])
>>>  dict1 ['python']:  123
dict1 ['Java']:  java

>>> dict = {'python': '123', 'Java': '456', 'android': '123'}
print(str(dict))
dict1 = {'python': 'python', 'C++': '456'}
dict.update(dict1)
print(str(dict))
>>> {'python': '123', 'Java': '456', 'android': '123'}
{'python': 'python', 'Java': '456', 'android': '123', 'C++': '456'}

删除字典元素

能删单一的元素也能清空字典，清空只需一项操作。
del dict1['android']; # 删除键是'android'的条目
dict1.clear(); # 清空词典所有条目
del dict1 ; # 删除词典 dict1 将不存在，如果再去引用字典将会报TypeError: 'type' object is unsubscriptable

打印字典

str(dict)
输出字典可打印的字符串表示。

判断字典key是否存在

#方法1：通过has_key
print (d.has_key('site'))
#方法2：通过in
print ('body' in d.keys())

字典的取值

# 得到字典a中的键—值对list
a.items()
# 得到字典a中键的list
a.keys()
# 得到字典a中值的list
a.values()
# 从字典a中取出键为k的值，如果没有，则返回x
a.get(k[, x])
# 返回字典a所有键-值对的迭代器

a.iteritems()
#  返回字典a所有键的迭代器
a.iterkeys()
# 返回字典a所有值的迭代器
a.itervalues()

python 字符串查找

python 字符串查找有4个方法: find, index , rfind , rindex 。
find()方法：查找子字符串，若找到返回从0开始的下标值，若找不到返回-1(找到第一个符合的值)
index方法是在字符串里查找子串第一次出现的位置，类似字符串的find方法，不过比find方法更好的是，如果查找不到子串，会抛出异常，而不是返回-1(找到第一个符合的值)
rfind , rindex 与对应的查找不一样的是找到最后一个符合的值。

info = 'abca'
print info.find('a')##从下标0开始，查找在字符串里第一个出现的子串，返回结果：0
info = 'abca'
print info.find('a',1)##从下标1开始，查找在字符串里第一个出现的子串：返回结果3
info = 'abca'
print info.find('333')##返回-1,查找不到返回-1

其他就不举例了，字符串这块是很重要的，这里不展开讲，有兴趣的可以看下这一篇文章
好了回到正题，怎么找出最长的不重复子字符串的长度。这里的难点主要是不重复。

暴力解法

思路很简单，两个for循环嵌套，如果一遇到集合里面已经存在的元素，那么就是遇到了重复元素，此时记录下最长的不重复字符串长度的值即可.

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        n = len(s)
        if n == 0:
            return 0
        if n == 1:
            return 1
        ans = 0
        mset = set()

        # 暴力解法
        for i in range(n):
            if s[i] not in mset:
                mset.add(s[i])
                ans = max(ans, mset.__len__())
                for j in range(i + 1, n):
                    if s[j] not in mset:
                        mset.add(s[j])
                        ans = max(ans, mset.__len__())
                    else:
                        mset.clear()
                        break
            else:
                mset.clear()
        return ans

这里插入一项，我们不可能把所有代码写在一个py文件里面，那么问题来了，我怎么去引用其他文件的函数呢？具体参考底下代码。

引用其他文件的函数

我们上面的算法是写在同文件夹里面的LongestSubstringWithoutRepeatingCharacters.py里面的，而我的测试引用代码是在test.py。所以需要引入外部文件，需要用到import 如下：

import  LongestSubstringWithoutRepeatingCharacters;

a = "dvdf"
b = LongestSubstringWithoutRepeatingCharacters.Solution().lengthOfLongestSubstring(a)
print(b)

这个时候提交代码，很不幸超时了，这个算法不符合要求啊。从题中可以看出至少需要O(n^2)的时间复杂度，那有什么其他方法吗？

利用字典

我们可以把当前的字符串字符当成字典的key（利用key的唯一性，不可重复来），把不重复的字符串长度存为字典的值。如果字典contains包含这个key，即遇到了重复的字符串，这个时候取出值即可。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        n = len(s)
        if n == 0:
            return 0
        if n == 1:
            return 1
        ans = 0
        mset = {}
        j = 0
        i = 0
        while  j < n:
            if mset.__contains__(s[j]):
                i = max(mset.get(s[j]), i)
            # i 上次不重复的最长个数，即也可以代表已经遍历过的个数，而 j - i + 1表示 这次遍历的不重复个数
            ans = max(ans, j - i + 1);
            mset.update({s[j]: j + 1});
            j = j + 1
            print(str(mset))
        return ans

字符串查找的优化

第一个肯定是不重复的，我们从第二个字符a = s[1]开始找的时候，找到了倒数第二个b = s[n-1]，发现b =s[n-1]已经出现过了，这时候，我们再从第二个s[x]开始找，那么得到的无重复子字符串必定比从a开始找要短，那么我们就不需要再从b开始找，而是从c开始找。
也就是说，当我们发现这个字符在前面的无重复子字符串出现的位置后一位开始找。如此我们可以节省很多时间，并且我们只需要从头找一次就可以得到答案。时间复杂度为（O（nlogn）。

ans = 1
        i = 1
        curbegin = 0
        while i < len(s):
            cur = s.find(s[i], curbegin, i)
            if cur != -1:
                lls = max(ans, i - curbegin)
                curbegin = cur + 1
            i += 1
        # 这里很容易忘记处理当最后一个字符再前面无重复子字符串里面的情况。
        if s.find(s[len(s) - 1], curbegin, len(s) - 1) == -1:
            return max(ans, len(s) - curbegin)
        return ans