學(xué)習(xí)使用工具
劍指Offer http://itmyhome.com/sword-means-offer/sword-means-offer.pdf
LeetCode的劍指Offer題庫 https://leetcode.cn/problemset/all/
劍指 Offer 49. 丑數(shù)
我們把只包含質(zhì)因子 2夸浅、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number）很澄。求按從小到大的順序的第 n 個(gè)丑數(shù)臭觉。
示例:
輸入: n = 10
輸出: 12
解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個(gè)丑數(shù)。
**說明: **
-
1是丑數(shù)廓俭。 -
n不超過1690。
解法：
1是丑數(shù)唉工，剩下的丑數(shù)都可以由已知丑數(shù)乘2研乒、3、5得到淋硝。
建立三個(gè)一模一樣的列表雹熬，記錄丑數(shù)序列。同時(shí)設(shè)置3個(gè)指針谣膳，分別遍歷三個(gè)列表中的元素竿报，被遍歷過的數(shù)已經(jīng)被用于做乘子來得到更大的丑數(shù)。而三個(gè)列表分別記錄該數(shù)是否已經(jīng)被乘過2继谚、3或5烈菌。
設(shè)置計(jì)數(shù)變量i，每次循環(huán)尋找下一個(gè)最小的丑數(shù)花履，并令對(duì)應(yīng)列表的指針后移一位芽世。同時(shí)判定該數(shù)是否已經(jīng)被加入列表，如果已經(jīng)加入诡壁，則繼續(xù)尋找济瓢；若沒有辞槐，則將該數(shù)加入列表坡贺，并使i+1。當(dāng)i已經(jīng)計(jì)數(shù)到n時(shí)岖寞，結(jié)束循環(huán)纽帖。返回列表中的第n個(gè)數(shù)即可。
def nthUglyNumber(self, n: int) -> int:
ans2 = [1]
ans3 = [1]
ans5 = [1]
poi2 = 0
poi3 = 0
poi5 = 0
i = 0
while i < n:
temp = min(ans2[poi2]*2, ans3[poi3]*3, ans5[poi5]*5)
if temp == ans2[poi2]*2:
poi2 += 1
elif temp == ans3[poi3]*3:
poi3 += 1
else:
poi5 += 1
if not temp in [ans2[-1], ans3[-1], ans5[-1]]:
ans2.append(temp)
ans3.append(temp)
ans5.append(temp)
i += 1
return ans2[n - 1]
劍指 Offer 50. 第一個(gè)只出現(xiàn)一次的字符
在字符串 s 中找出第一個(gè)只出現(xiàn)一次的字符举反。如果沒有懊直，返回一個(gè)單空格。 s 只包含小寫字母火鼻。
示例 1:
輸入：s = "abaccdeff"
輸出：'b'
示例 2:
輸入：s = ""
輸出：' '
限制：
0 <= s 的長度 <= 50000
解法：
開辟flag數(shù)組進(jìn)行記錄室囊。flag[i]記錄26個(gè)小寫字母是否出現(xiàn)過。遍歷原始字符串魁索，檢查每個(gè)字符融撞，如果該字符未出現(xiàn)過，則將對(duì)應(yīng)flag置為1粗蔚；如果已出現(xiàn)過尝偎，從字符串中刪去所有該字符。遍歷結(jié)束后，返回結(jié)果字符串中的第一個(gè)字符致扯。
def firstUniqChar(self, s: str) -> str:
flag = [0] * 26
ans = s
for c in s:
if flag[ord(c) - ord('a')] == 0:
flag[ord(c) - ord('a')] = 1
else:
ans = ans.replace(c, '')
if ans:
return ans[0]
else:
return ' '
劍指 Offer 51. 數(shù)組中的逆序?qū)?/strong>
在數(shù)組中的兩個(gè)數(shù)字肤寝，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Χ督］斎胍粋€(gè)數(shù)組鲤看，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)。
示例 1:
輸入: [7,5,6,4]
輸出: 5
限制：
0 <= 數(shù)組長度 <= 50000
解法：
進(jìn)行一次歸并排序耍群。在合并階段义桂，記錄逆序?qū)倲?shù)即可。
def reversePairs(self, nums: List[int]) -> int:
temp = [0] * len(nums) # 輔助數(shù)組蹈垢，用于歸并階段
def merge(l: int, r: int): # 歸并排序慷吊，返回值為此數(shù)組所含的逆序?qū)倲?shù)
if l >= r: # 如果l>=r，說明此時(shí)子數(shù)組的長度已經(jīng)<=1耘婚，返回0
return 0
m = (l + r) // 2 # 劃分
res = merge(l, m) + merge(m + 1, r) # res等于左右兩個(gè)數(shù)組各自劃分后得到的逆序?qū)倲?shù)
i = l # 左指針遍歷左數(shù)組
j = m + 1 # 右指針遍歷右數(shù)組
temp[l: r + 1] = nums[l: r + 1] # temp保存原始數(shù)組的值便于歸并
for k in range(l, r + 1): # 歸并階段罢浇，k表示當(dāng)前的排序位置，每次將對(duì)應(yīng)的元素置于nums[k]
if i == m + 1: # 如果左指針已經(jīng)遍歷完畢沐祷，則將右指針數(shù)字加入排序位置嚷闭，右指針后移
nums[k] = temp[j]
j += 1
elif j == r + 1: # 如果右指針已經(jīng)遍歷完畢，則將左指針數(shù)字加入排序位置赖临，左指針后移
nums[k] = temp[i]
i += 1
elif temp[i] <= temp[j]:# 如果左指針小于右指針胞锰，則將左指針數(shù)字加入排序位置，左指針后移
nums[k] = temp[i]
i += 1
else:
# 如果左指針大于右指針兢榨，則將右指針數(shù)字加入排序位置嗅榕，右指針后移。
# 此時(shí)產(chǎn)生數(shù)量為(m-i+1)的逆序?qū)Γ醋髷?shù)組剩下的元素?cái)?shù)量）吵聪，加入res
nums[k] = temp[j]
j += 1
res += m - i + 1
return res
return merge(0, len(nums) - 1)
劍指 Offer 52. 兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)
輸入兩個(gè)鏈表凌那，找出它們的第一個(gè)公共節(jié)點(diǎn)。
如下面的兩個(gè)鏈表：
在節(jié)點(diǎn) c1 開始相交吟逝。
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Reference of the node with value = 8
輸入解釋：相交節(jié)點(diǎn)的值為 8 （注意帽蝶，如果兩個(gè)列表相交則不能為 0）。從各自的表頭開始算起块攒，鏈表 A 為 [4,1,8,4,5]励稳，鏈表 B 為 [5,0,1,8,4,5]。在 A 中囱井，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)驹尼；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)庞呕。
示例 2：
輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Reference of the node with value = 2
輸入解釋：相交節(jié)點(diǎn)的值為 2 （注意新翎，如果兩個(gè)列表相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]料祠，鏈表 B 為 [3,2,4]骆捧。在 A 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)髓绽；在 B 中敛苇，相交節(jié)點(diǎn)前有 1 個(gè)節(jié)點(diǎn)。
示例 3：
輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
輸入解釋：從各自的表頭開始算起顺呕，鏈表 A 為 [2,6,4]枫攀，鏈表 B 為 [1,5]。由于這兩個(gè)鏈表不相交株茶，所以 intersectVal 必須為 0来涨，而 skipA 和 skipB 可以是任意值。
解釋：這兩個(gè)鏈表不相交启盛，因此返回 null蹦掐。
注意：
- 如果兩個(gè)鏈表沒有交點(diǎn)，返回
null. - 在返回結(jié)果后僵闯，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)卧抗。
- 可假定整個(gè)鏈表結(jié)構(gòu)中沒有循環(huán)。
- 程序盡量滿足 O(n) 時(shí)間復(fù)雜度鳖粟，且僅用 O(1) 內(nèi)存社裆。
解法：
自己寫的稍微有點(diǎn)笨蛋的解法，先獲取兩個(gè)鏈表的長度向图，然后截去長鏈表的開頭部分讓兩個(gè)鏈表一樣長泳秀，之后再遍歷就行了。
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
def getlen(head: ListNode):
count = 0
while head:
count += 1
head = head.next
return count
lenA = getlen(headA)
lenB = getlen(headB)
if lenA >= lenB:
A = headA
for i in range(lenA - lenB):
A = A.next
B = headB
else:
A = headB
for i in range(lenB - lenA):
A = A.next
B = headA
while A:
if A == B:
return A
A = A.next
B = B.next
return A
翻答案發(fā)現(xiàn)有更好的雙指針相遇解法榄攀，截取一下K神的解說：
考慮構(gòu)建兩個(gè)節(jié)點(diǎn)指針 A , B 分別指向兩鏈表頭節(jié)點(diǎn) headA , headB 嗜傅，做如下操作：
指針 A 先遍歷完鏈表 headA ，再開始遍歷鏈表 headB 檩赢，當(dāng)走到 node 時(shí)磺陡，共走步數(shù)為：a+(b?c)
指針 B 先遍歷完鏈表 headB ，再開始遍歷鏈表 headA 漠畜，當(dāng)走到 node 時(shí)，共走步數(shù)為：b+(a?c)
如下式所示坞靶，此時(shí)指針 A , B 重合憔狞，并有兩種情況：
a+(b?c)=b+(a?c)
若兩鏈表 有 公共尾部 (即c>0) ：指針 A , B 同時(shí)指向「第一個(gè)公共節(jié)點(diǎn)」node 。
若兩鏈表 無 公共尾部 (即c=0) ：指針 A , B 同時(shí)指向 null彰阴。
因此返回 A 即可瘾敢。
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
A, B = headA, headB
while A != B:
A = A.next if A else headB
B = B.next if B else headA
return A
