六個(gè)算法問題万栅，使用python學(xué)習(xí)算法匪补。
1.1 旋轉(zhuǎn)字符串
給定字符串伞辛，要求把字符串前面若干個(gè)字符移動(dòng)到字符串尾部。要求時(shí)間復(fù)雜度O(n)夯缺，空間復(fù)雜度O(1)始锚。
如：'abcdefg'前面的2個(gè)字符'a'和'b'移到字符串尾部，就是'cdefgab'喳逛。
解法一：暴力移位法
def left_shift_one(s):
slist = list(s)
temp = slist[0]
for i in range(1, len(s)):
slist[i - 1] = slist[i]
slist[len(s) - 1] = temp
s = ''.join(slist)
return s
def left_rotate_str(s, n):
while n > 0:
s = left_shift_one(s)
n -= 1
return s
時(shí)間復(fù)雜度O(n*len(s))， 空間復(fù)雜度O(1)棵里。
解法二：三步反轉(zhuǎn)法
例如給定字符串'abcdefg'润文，若要讓ab翻轉(zhuǎn)到最后姐呐，只需三步操作：
step 1. 字符串分為兩部分，即：X=ab, Y=cdefg典蝌；
step 2. 將X曙砂、Y均反轉(zhuǎn)，得到：X=ba, Y=gfedc骏掀；
step 3. 將step2得到的結(jié)果反轉(zhuǎn)鸠澈，即將'bagfedc'反轉(zhuǎn)，得到：cdefgab截驮，即為想要的結(jié)果笑陈。
def reserve_str(s):
s_list = list(s)
start, end = 0, len(s)-1
while start < end:
s_list[start], s_list[end] = s_list[end], s_list[start]
start += 1
end -= 1
return ''.join(s_list)
def left_rotate_str(s, n):
x, y = list(s[:n]), list(s[n:])
x = reserve_str(x)
y = reserve_str(y)
res = reserve_str(x+y)
return ''.join(res)
時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)葵袭。
1.2 鏈表反轉(zhuǎn)
給出一個(gè)鏈表和一個(gè)數(shù)k涵妥，比如：鏈表為1->2->3->4->5->6, k=2，翻轉(zhuǎn)后為2->1->6->5->4->3坡锡；若k=3蓬网，翻轉(zhuǎn)后3->2->1->6->5->4。
鏈表反轉(zhuǎn)的方式
解法一： 循環(huán)迭代
基本思想就是將每個(gè)節(jié)點(diǎn)的向前鹉勒、向后指向變換帆锋。
def reverse_loop(head):
if not head or not head.next:
return head
pre = None
while head:
next = head.next # 緩存當(dāng)前節(jié)點(diǎn)的向后指針，下次迭代用
head.next = pre # 把當(dāng)前節(jié)點(diǎn)的向前指針作為當(dāng)前節(jié)點(diǎn)的向后指針
pre = head # 作為下次迭代(當(dāng)前節(jié)點(diǎn))的向前指針
head = next # 作為下次迭代的(當(dāng)前)節(jié)點(diǎn)
return pre
解法二：遞歸
遞歸的思想就是：
head.next = None
head.next.next = head.next
head.next.next.next = head.next.next
...
代碼實(shí)現(xiàn)：
def reverse_recursion(head):
if not head or not head.next:
return head
new_head = reverse_recursion(head.next)
head.next.next = head
head.next = None
return new_head
解法
def divide_linked_list(head, k):
if head is None or head.next is None:
return head
p1 = head
p2 = head.next
while k >0:
tmp = p2.next
p2.next = p1
p1 = p2
p2 = tmp
k -= 1
p3 = reverse_recursion(p2) # 后部分翻轉(zhuǎn)
head.data = p3.data
head.next = p3.next
return p1
2.1 字符串包含
給定一長一短的兩個(gè)字符串A禽额，B锯厢，假設(shè)A長B短，要求判斷B是否包含在字符串A中绵疲。
解法一：暴力法
def string_contain(string_a, string_b):
for b in string_b:
if b not in string_a:
return False
return True
假設(shè)A字符串長n哲鸳，B字符串長m，那么這種暴力解需要O(n*m)次操作盔憨。
解法二：線性掃描
這種方法首先需要將A, B字符串排序徙菠，隨后同時(shí)對(duì)這兩個(gè)字符串依次輪詢。
def string_contain(string_a, string_b):
list_a = sorted(string_a)
list_b = sorted(string_b)
pa, pb = 0, 0
while pb < len(list_b):
while pa < len(list_a) and (list_a[pa] < list_b[pb]):
pa += 1
if (pa >= len(list_a)) or (list_a[pa] > list_b[pb]):
return False
pb += 1
return True
排序需要O(mlogm) + O(nlogn)次操作郁岩，之后的線性掃描則只需要O(m+n)次操作婿奔。
解法三：素?cái)?shù)對(duì)應(yīng)
將每個(gè)字母與一個(gè)素?cái)?shù)相對(duì)應(yīng)。遍歷長字符串A问慎，將每個(gè)字母對(duì)應(yīng)的素?cái)?shù)相乘得到一個(gè)乘積萍摊。再遍歷短字符串B，將每個(gè)字符對(duì)應(yīng)的素?cái)?shù)除A的乘積如叼，若不能整除冰木，說明B中對(duì)應(yīng)的字符不在A字符串中。
from functools import reduce
def string_contain(string_a, string_b):
char_map = {'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11, 'f': 13, 'g': 17, 'h': 19, 'i': 23, 'j': 29, 'k': 31, 'l': 37,
'm': 41, 'n': 43, 'o': 47, 'p': 53, 'q': 59, 'r': 61, 's': 67, 't': 71, 'u': 73, 'v': 79, 'w': 83,
'x': 89, 'y': 97, 'z': 101}
pd_a = reduce(lambda x, y: x * y, [char_map[x] for x in string_a])
for b in list(string_b):
if pd_a % char_map[b] != 0:
return False
return True
需要O(m+n)次操作，但要考慮素?cái)?shù)相乘的結(jié)果有可能導(dǎo)致正數(shù)溢出踊沸。
3.1 回文字符串
判斷一個(gè)字符串正著讀和倒著讀是否一樣歇终，比如：'abcba'即為回文字符串。
解法一：頭尾指針向中間掃描
同時(shí)從字符串的頭尾向中間掃描逼龟，知道頭尾相遇评凝。如果所有字符都一樣，那么這就是一個(gè)回文字符串腺律。
def is_palindrome(s):
s = list(s)
if len(s)>0:
start, end = 0, len(s)-1
while start<end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
return True
解法二：中間向頭尾掃描
也可以從字符串的中間向頭尾掃描奕短，如果所有字符都一樣，就認(rèn)為這是個(gè)回文字符串匀钧。
def is_palindrome(s):
s = list(s)
if len(s) > 0:
front = len(s) // 2 - 1 if len(s) % 2 == 0 else len(s) // 2
back = len(s) // 2
while front >= 0 and back <= len(s)-1:
if s[front] != s[back]:
return False
front -= 1
back += 1
return True
return True
3.2 回文鏈表
如何判斷一條單向鏈表是不是'回文'呢翎碑？
對(duì)于單項(xiàng)鏈表也可以像字符串那樣，找到其中點(diǎn)榴捡，然后將后半翻轉(zhuǎn)（見 1.1.2 鏈表反轉(zhuǎn)）杈女，再同時(shí)從鏈表頭部和中間開始遍歷比較。
def is_palindrome(self, head):
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
node = None
while slow:
current = slow
slow = slow.next
current.next = node
node = current
while node:
if node.data != head.data:
return False
node = node.next
head = head.next
return True
4.1 最長回文子串
給定一個(gè)字符串吊圾，求它的最長回文子串的長度达椰。
解法一：遍歷所有元素
首先想到的是遍歷字符串中的所有元素，用兩個(gè)指針以某個(gè)元素為中心向左右擴(kuò)展项乒，記錄并更新得到的最長的回文長度啰劲。在這里需要注意，奇數(shù)長度與偶數(shù)長度的回文字符串的判斷稍有區(qū)別檀何，需要分開處理蝇裤。
def _odd(i, max, s, id):
j, temp = 0, 0
while j <= i and i + j < len(s):
if s[i - j] != s[i + j]:
break
temp = j * 2 + 1
j += 1
if temp > max:
max = temp
id = i
return max, id
def _even(i, max, s, id):
j, temp = 0, 0
while j <= i and i + j + 1 < len(s):
if s[i - j] != s[i + j + 1]:
break
temp = j * 2 + 2
j += 1
if temp > max:
max = temp
id = i
return max, id
def longest_palindrome(s):
if len(s) == 0:
return 0
max, id = -1, 0
for i in range(len(s)):
odd_res = _odd(i, max, s, id)
max, id = odd_res[0], odd_res[1]
even_res = _even(i, max, s, id)
max, id = even_res[0], even_res[1]
return s[id - max // 2:id + (max + 1) // 2] if max % 2 != 0 else s[id - max // 2+1:id + max // 2 + 1]
解法二： 統(tǒng)一處理奇偶
上述解法中，我們需要特別區(qū)分奇偶回文字符串的情況频鉴。那么有沒有方法可以將所有情況都轉(zhuǎn)換為奇數(shù)處理呢栓辜？
可以通過在每個(gè)字符的兩邊都插入一個(gè)特殊的符號(hào)，將所有可能的奇數(shù)或偶數(shù)長度的回文子串都轉(zhuǎn)換成了奇數(shù)長度垛孔。比如 abba 變成 #a#b#b#a#藕甩，aba變成 #a#b#a#。
此外周荐，還可以在首位各加上特殊符號(hào)狭莱，這樣就不用特殊處理越界問題，比如^#a#b#a#$概作。
def longest_palindrome(s):
s_j = '#'.join('^{}$'.format(s))
if len(s_j) == 3:
return 0
max, id = -1, 0
for i in range(len(s_j)):
j = 0
temp = 0
while j <= i and i + j < len(s_j):
if s_j[i - j] != s_j[i + j]:
break
temp = j * 2
j += 1
if temp > max:
max = temp
id = i // 2 - 1
return s[id - max // 4:id + (max + 1) // 4 + 1] if max % 4 != 0 else s[id - max // 4 + 1:id + max // 4 + 1]
解法三： Manacher算法
下面將用到神奇的Manacher算法腋妙，使求最長回文子串的時(shí)間復(fù)雜度為線性O(shè)(N)。
def longest_palindrome(s):
# Transform S into T.
# For example, S = "abba", T = "^#a#b#b#a#$".
# ^ and $ signs are sentinels appended to each end to avoid bounds checking
s_j = '#'.join('^{}$'.format(s))
n = len(s_j)
P = [0] * n
id = mx = 0
for i in range(1, n - 1):
P[i] = (mx > i) and min(mx - i, P[2 * id - i]) # equals to i' = id - (i-id)
# Attempt to expand palindrome centered at i
while s_j[i + 1 + P[i]] == s_j[i - 1 - P[i]]:
P[i] += 1
# If palindrome centered at i expand past mx,
# adjust center based on expanded palindrome.
if i + P[i] > mx:
id, mx = i, i + P[i]
# Find the maximum element in P.
maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
return s[(centerIndex - maxLen) // 2: (centerIndex + maxLen) // 2]
5 交替字符串
輸入三個(gè)字符串s1讯榕、s2和s3骤素，判斷第三個(gè)字符串s3是否由前兩個(gè)字符串s1和s2交錯(cuò)而成匙睹，即不改變s1和s2中各個(gè)字符原有的相對(duì)順序，例如當(dāng)s1 = “aabcc”谆甜，s2 = “dbbca”垃僚，s3 = “aadbbcbcac”時(shí)，則輸出True规辱，但如果s3=“accabdbbca”，則輸出False栽燕。
這道題我們考慮用動(dòng)態(tài)規(guī)劃的方法罕袋，定義dp[i][j]為s1的前i和字串和s2和前j個(gè)字串是否構(gòu)成交替字符串。
可以分兩種情況討論：
- 如果s1當(dāng)前字符(即s1[i-1])等于s3當(dāng)前字符(即s3[i+j-1])碍岔，且dp[i-1][j]為真浴讯，那么可以取s1當(dāng)前字符而忽略s2的情況，dp[i][j]返回真;
- 如果s2當(dāng)前字符等于s3當(dāng)前字符蔼啦，并且dp[i][j-1]為真榆纽，那么可以取s2而忽略s1的情況，dp[i][j]返回真捏肢，其它情況奈籽，dp[i][j]返回假
狀態(tài)轉(zhuǎn)移為：
dp[i][j] = (dp[i-1][j]&& s1[i-1]==s3[i+j-1]) || dp[i][j-1] && s2[j-1]==s3[i+j-1]
代碼實(shí)現(xiàn)如下：
def is_inter_leave(s1, s2, s3):
l_1, l_2, l_3 = len(s1), len(s2), len(s3)
if l_1 + l_2 != l_3:
return False
dp = [[False for _ in range(l_1 + 1)] for _ in range(l_2 + 1)]
dp[0][0] = True
for i in range(1, l_1 + 1):
dp[0][i] = dp[0][i - 1] and (s3[i - 1] == s1[i - 1])
for i in range(1, l_2 + 1):
dp[i][0] = dp[i - 1][0] and (s3[i - 1] == s2[i - 1])
for i in range(1, l_2 + 1):
for j in range(1, l_1 + 1):
if (dp[i][j - 1] and s1[j - 1] == s3[i + j - 1]) or (dp[i - 1][j] and s2[i - 1] == s3[i + j - 1]):
dp[i][j] = True
return dp[l_2][l_1]
6 字符串編輯距離
給定一個(gè)源串和目標(biāo)串，能夠?qū)υ创M(jìn)行如下操作：
- 在給定位置上插入一個(gè)字符
- 替換任意字符
- 刪除任意字符
寫一個(gè)程序鸵赫，返回最小操作數(shù)衣屏，使得對(duì)源串進(jìn)行這些操作后等于目標(biāo)串，源串和目標(biāo)串的長度都小于2000辩棒。
這題我們依舊可以采用動(dòng)態(tài)規(guī)劃的方法狼忱。例如字符串'ALGORITHM'變成'ALTRUISTIC'，那么把相關(guān)字符各自對(duì)齊后一睁，如下圖：
把源串S[0...i]='ALGORITHM'編輯成下面的目標(biāo)串T[0...j]='ALTRUISTIC'钻弄，對(duì)于字符s[i]和t[j]的對(duì)應(yīng)，有以下四種情況：
- 目標(biāo)串空白者吁，即S + 字符X窘俺，T + 空白，意味著源串要?jiǎng)h字符砚偶，則操作數(shù)為dp[i-1, j] + 1
- 源串空白批销，即S + 空白，T + 字符染坯，意味著源串需要插入字符均芽，則操作數(shù)為dp[i, j-1] + 1
- 源串的字符和目標(biāo)串的字符不一樣，即S + 字符X单鹿，T + 字符Y掀宋，S變成T，意味著源串要修改字符，操作數(shù)為dp[i - 1, j - 1]
- 源串的字符和目標(biāo)串的字符一樣劲妙，不用修改湃鹊，操作數(shù)為dp[i - 1, j - 1] + 1
代碼如下：
def edit_distance(source, target):
len_s = len(source)
len_t = len(target)
dp = [[0 for _ in range(len_t+1)] for _ in range(len_s+1)]
for i in range(len_s+1):
dp[i][0] = i
for j in range(len_t+1):
dp[0][j] = j
for i in range(1, len_s+1):
for j in range(1, len_t+1):
if source[i-1] == target[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1+ min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[len_s][len_t]
