算法很重要，但是每天也需要學學python，于是就想用python刷leetcode 的算法題，和我一起開始零基礎python刷leetcode之旅吧。如有不對的地方，希望指正，萬分感謝~~

題目

最長的不重復子字符串的長度

題目解析

題目是大概意思就是找出最長的不重復子字符串的長度。

還是老規矩，先來過一些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)

集合元素的增加

集合元素的增加支持兩種類型，單個元素的增加用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

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))

>>>

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

總結

以上是生活随笔為你收集整理的python刷leetcode_零基础python刷leetcode -- 3. Longest Substring Without Repeating Characters的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。