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

題目

最長的不重復(fù)子字符串的長度

題目解析

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

還是老規(guī)矩，先來過一些python基礎(chǔ)知識(shí)，老手請(qǐng)自動(dòng)忽略：

python的集合Set

Set 是沒有重復(fù)元素的集合，python里用{}大括號(hào)表示，和字典一樣，為了區(qū)分，初始化空的集合只能通過set()操作，而{}表示空的字典。

set無序排序且不重復(fù)，是可變的，有add()，remove()等方法。既然是可變的，所以它不存在哈希值。基本功能包括關(guān)系測(cè)試和消除重復(fù)元素. 集合對(duì)象還支持union(聯(lián)合), intersection(交集), difference(差集)和sysmmetric difference(對(duì)稱差集)等數(shù)學(xué)運(yùn)算.

sets 支持 x in set, len(set),和 for x in set。作為一個(gè)無序的集合，sets不記錄元素位置或者插入點(diǎn)。因此，sets不支持 indexing, 或其它類序列的操作。

frozenset是凍結(jié)的集合，它是不可變的，存在哈希值，好處是它可以作為字典的key，也可以作為其它集合的元素。缺點(diǎn)是一旦創(chuàng)建便不能更改，沒有add，remove方法。這里就不展開講了。

初始化

>>> s= set("hello")

{'l', 'h', 'e', 'o'}

>>> type(s)

集合元素的增加

集合元素的增加支持兩種類型，單個(gè)元素的增加用add方法，對(duì)序列的增加用update方法。相當(dāng)于Java中的list的add 和addAll。簡(jiǎn)單理解就是update添加的會(huì)拆分。

>>> 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'}

上面的程序多執(zhí)行幾次，我們發(fā)現(xiàn)每次打印的順序都不一樣。為什么呢？

因?yàn)镾et是無序的。怎么去理解這個(gè)無序呢？

set的“無序”是相對(duì)于平衡二叉樹而言的。但是，基于平衡二叉樹的set(如c++中用紅黑樹實(shí)現(xiàn)的set和python中的orderedset)是有序的。由于二叉搜索樹的特點(diǎn)，可以很輕松的找到任意節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)，所以算是“有序”的。

而set基于哈希表實(shí)現(xiàn)，存取時(shí)間可看做O(1)，但是沒有辦法高效的完成順序相關(guān)的操作(比如找前驅(qū)后繼，最大最小值等等)，所以認(rèn)為是“無序”的。

集合刪除單個(gè)元素

集合 刪除單個(gè)元素有兩種方法，set.discard(x)和set.remove(x)。兩者的區(qū)別是如果元素不在原集合中時(shí)是否會(huì)拋出異常。set.remove會(huì)拋出KeyError錯(cuò)誤,而set.discard不會(huì)拋出異常。

>>> 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返回的結(jié)果不能確定，且當(dāng)集合為空時(shí)調(diào)用pop會(huì)拋出KeyError錯(cuò)誤，可以調(diào)用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}

多次執(zhí)行程序，發(fā)現(xiàn)上面一組打印是無序的，下面一組是有序的(多次執(zhí)行結(jié)果都一樣)。真的是這樣嗎？

其實(shí)set內(nèi)部保存的數(shù)據(jù)都是通過哈希值排序的。為了幫助理解，我們可以簡(jiǎn)單的認(rèn)為hashCode%size=0的key排在最前，hashCode%size=1的其次，以此類推()。

image.png

Java里面計(jì)算字符串hash方法是(python的應(yīng)該類似)：

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

來看一個(gè)例子：

計(jì)算字符串”Lee”的哈希值

‘L’的ASCII碼為76，’e’的ASCII碼為101

多少個(gè)字符就需要for循環(huán)幾次，例子是3次

h=31*0+76=76

h=31*76+101=2457

h=31*2457+101=76268

所以字符串”Lee”的哈希碼就是76268

而1 ~ 4對(duì)應(yīng)的ascii碼對(duì)應(yīng)49~52，相當(dāng)于一個(gè)字符。于是有如下計(jì)算：

0*31 +49 =49

0*31 +50 =50

0*31 +51 =51

0*31 +52 =52

然后根據(jù)hashCode%size排序的到49 %4 = 1 ； 50 %4 = 2以此類推，{1,15,8,25} 對(duì)應(yīng)排序{8,1,25,15},驗(yàn)證一致。但是看下上面的1～4那么按照理由，這個(gè)4應(yīng)該排序在最前面才對(duì)？其實(shí)值>=size的都會(huì)排在最前面,如果值>=size，當(dāng)元素個(gè)數(shù)size的變化會(huì)引起排序的變化。

python計(jì)算hash值是有一些算法去計(jì)算的，所以對(duì)于一些數(shù)字還是存在一些規(guī)律的，說了這么多，就是為了引出一句話，這個(gè)按照順序只是碰巧的(不要打我。。。。。。我對(duì)自己也是很無語，啊哈哈)，實(shí)在要去深究，你可以看下計(jì)算hash值的這些算法(hashlib模塊)：'md5', 'sha1', 'sha224', 'sha256', 'sha384', 'sha512', 'new', 'algorithms_guaranteed', 'algorithms_available', 'pbkdf2_hmac'

引用知乎一段話：

hash(散列、雜湊)函數(shù)，是將任意長度的數(shù)據(jù)映射到有限長度的域上。直觀解釋起來，就是對(duì)一串?dāng)?shù)據(jù)m進(jìn)行雜糅，輸出另一段固定長度的數(shù)據(jù)h，作為這段數(shù)據(jù)的特征(指紋)。也就是說，無論數(shù)據(jù)塊m有多大，其輸出值h為固定長度。到底是什么原理？將m分成固定長度(如128位)，依次進(jìn)行hash運(yùn)算，然后用不同的方法迭代即可(如前一塊的hash值與后一塊的hash值進(jìn)行異或)。如果不夠128位怎么辦？用0補(bǔ)全或者用1補(bǔ)全隨意，算法中約定好就可以了。

這個(gè)運(yùn)用是很廣的，比如很多網(wǎng)站或者銀行不會(huì)保存用戶密碼，都是保存密碼的hash值，只要按照約定好的算法就能解析出來正確的值。

集合多個(gè)元素的刪除

set(['p', 'y', 't', 'h', 'o', 'n', 'j', 'a', 'v', 'a'])

>>> s -= set('java')#刪除

>>> s

set(['p', 'y', 't', 'h', 'o', 'n'])

>>> del s #刪除整個(gè)集合

條件判斷(關(guān)系)

s = set(['p', 'y', 't', 'h', 'o', 'n'])

>>> 'j' in s

False

>>> 'p' in s

True

>>> 'a' not in s

True

集合等價(jià)/不等價(jià)

s = set('python')

t = set('java')

>>> s == t

False

>>> s != t

True

集合的運(yùn)算看下圖，這個(gè)是數(shù)學(xué)的東西了。。。不懂的自行百度：

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

聯(lián)合( | )

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

兩個(gè)集合的聯(lián)合是一個(gè)新集合，理解并集(數(shù)學(xué)的或)成員，方法為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(或合取)操作。兩個(gè)集合的交集是一個(gè)新集合，方法為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'}

差補(bǔ)/相對(duì)補(bǔ)集( – )

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

兩個(gè)集合(s 和 t)的差補(bǔ)或相對(duì)補(bǔ)集是一個(gè)新集合，該集合中的元素，只屬于集合 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)的結(jié)果是不一樣的，讀者可以自行按照上面的圖畫出來之后，就可以知道，補(bǔ)集是不一樣的。

對(duì)稱差分( ^ )

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

和其他的布爾集合操作相似， 對(duì)稱差分是集合的 XOR(又稱"異或 ").

兩個(gè)集合(s 和 t)的對(duì)稱差分是一個(gè)x新的集合 ,該集合中的元素，只能是屬于集合 s 或者集合 t 的成員，不能同時(shí)屬于兩個(gè)集合。方法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'} #其實(shí)和上面的結(jié)果是一致的，所以異或和順序沒有關(guān)系

python的字典

字典是另一種可變?nèi)萜髂Ｐ?#xff0c;且可存儲(chǔ)任意類型對(duì)象。

字典的每個(gè)鍵值(key=>value)對(duì)用冒號(hào)(:)分割，每個(gè)對(duì)之間用逗號(hào)(,)分割，整個(gè)字典包括在花括號(hào)({})中 。

鍵必須是唯一的，但值則不必。

值可以取任何數(shù)據(jù)類型，但鍵必須是不可變的，如字符串，數(shù)字或元組。

字典格式和初始化：

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中鍵值對(duì)，并將其從字典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

＃如果ｋｅｙ不存在，是會(huì)拋出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'}

刪除字典元素

能刪單一的元素也能清空字典，清空只需一項(xiàng)操作。

del dict1['android']; # 刪除鍵是'android'的條目

dict1.clear(); # 清空詞典所有條目

del dict1 ; # 刪除詞典 dict1 將不存在，如果再去引用字典將會(huì)報(bào)TypeError: 'type' object is unsubscriptable

打印字典

str(dict)

輸出字典可打印的字符串表示。

判斷字典key是否存在

#方法1：通過has_key

print (d.has_key('site'))

#方法2：通過in

print ('body' in d.keys())

字典的取值

# 得到字典a中的鍵—值對(duì)list

a.items()

# 得到字典a中鍵的list

a.keys()

# 得到字典a中值的list

a.values()

# 從字典a中取出鍵為k的值，如果沒有，則返回x

a.get(k[, x])

# 返回字典a所有鍵-值對(duì)的迭代器

a.iteritems()

# 返回字典a所有鍵的迭代器

a.iterkeys()

# 返回字典a所有值的迭代器

a.itervalues()

python 字符串查找

python 字符串查找有4個(gè)方法: find, index , rfind , rindex 。

find()方法：查找子字符串，若找到返回從0開始的下標(biāo)值，若找不到返回-1(找到第一個(gè)符合的值)

index方法是在字符串里查找子串第一次出現(xiàn)的位置，類似字符串的find方法，不過比find方法更好的是，如果查找不到子串，會(huì)拋出異常，而不是返回-1(找到第一個(gè)符合的值)

rfind , rindex 與對(duì)應(yīng)的查找不一樣的是找到最后一個(gè)符合的值。

info = 'abca'

print info.find('a')##從下標(biāo)0開始，查找在字符串里第一個(gè)出現(xiàn)的子串，返回結(jié)果：0

info = 'abca'

print info.find('a',1)##從下標(biāo)1開始，查找在字符串里第一個(gè)出現(xiàn)的子串：返回結(jié)果3

info = 'abca'

print info.find('333')##返回-1,查找不到返回-1

其他就不舉例了，字符串這塊是很重要的，這里不展開講，有興趣的可以看下這一篇文章

好了回到正題，怎么找出最長的不重復(fù)子字符串的長度。這里的難點(diǎn)主要是不重復(fù)。

暴力解法

思路很簡(jiǎn)單，兩個(gè)for循環(huán)嵌套，如果一遇到集合里面已經(jīng)存在的元素，那么就是遇到了重復(fù)元素，此時(shí)記錄下最長的不重復(fù)字符串長度的值即可.

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

這里插入一項(xiàng)，我們不可能把所有代碼寫在一個(gè)py文件里面，那么問題來了，我怎么去引用其他文件的函數(shù)呢？具體參考底下代碼。

引用其他文件的函數(shù)

我們上面的算法是寫在同文件夾里面的LongestSubstringWithoutRepeatingCharacters.py里面的，而我的測(cè)試引用代碼是在test.py。所以需要引入外部文件，需要用到import 如下：

import LongestSubstringWithoutRepeatingCharacters;

a = "dvdf"

b = LongestSubstringWithoutRepeatingCharacters.Solution().lengthOfLongestSubstring(a)

print(b)

這個(gè)時(shí)候提交代碼，很不幸超時(shí)了， 這個(gè)算法不符合要求啊。從題中可以看出至少需要O(n^2)的時(shí)間復(fù)雜度，那有什么其他方法嗎？

利用字典

我們可以把當(dāng)前的字符串字符 當(dāng)成字典的key(利用key的唯一性，不可重復(fù)來)，把不重復(fù)的字符串長度存為字典的值。如果字典contains包含這個(gè)key，即遇到了重復(fù)的字符串，這個(gè)時(shí)候取出值即可。

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 上次不重復(fù)的最長個(gè)數(shù)，即也可以代表已經(jīng)遍歷過的個(gè)數(shù)，而 j - i + 1表示 這次遍歷的不重復(fù)個(gè)數(shù)

ans = max(ans, j - i + 1);

mset.update({s[j]: j + 1});

j = j + 1

print(str(mset))

return ans

字符串查找的優(yōu)化

第一個(gè)肯定是不重復(fù)的，我們從第二個(gè)字符a = s[1]開始找的時(shí)候，找到了倒數(shù)第二個(gè)b = s[n-1]，發(fā)現(xiàn)b =s[n-1]已經(jīng)出現(xiàn)過了，這時(shí)候，我們?cè)購牡诙€(gè)s[x]開始找，那么得到的無重復(fù)子字符串必定比從a開始找要短，那么我們就不需要再從b開始找，而是從c開始找。

也就是說，當(dāng)我們發(fā)現(xiàn)這個(gè)字符在前面的無重復(fù)子字符串出現(xiàn)的位置后一位開始找。如此我們可以節(jié)省很多時(shí)間，并且我們只需要從頭找一次就可以得到答案。時(shí)間復(fù)雜度為(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

# 這里很容易忘記處理當(dāng)最后一個(gè)字符再前面無重復(fù)子字符串里面的情況。

if s.find(s[len(s) - 1], curbegin, len(s) - 1) == -1:

return max(ans, len(s) - curbegin)

return ans

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。