網(wǎng)站鏈接維護(hù)怎么做bing搜索引擎國際版
1.相交鏈表
- 解題思路
快慢指針：分別求出兩個鏈表的長度n1和n2，在長度較長的那個鏈表上，快指針先走n2 - n1，慢指針再出發(fā)，最后能相遇則鏈表相交
時間復(fù)雜度O(m+n)，空間復(fù)雜度O(1) - 代碼
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:if not headA or not headB:return Nonel_a = 0l_b = 0node = headAwhile node:l_a += 1node = node.nextnode = headBwhile node:l_b += 1node = node.nextnode1 = headA node2 = headBif l_b > l_a:l_a, l_b = l_b, l_anode1, node2, = node2, node1for _ in range(l_a - l_b):node1 = node1.nextwhile node1 and node2:if node1 == node2:return node1node1 = node1.nextnode2 = node2.nextreturn None
2.翻轉(zhuǎn)鏈表
- 解題思路
最基本的題目，一定要掌握。prev初始化成None，不需要dummy_head
時間復(fù)雜度O（N），空間復(fù)雜度O（1） - 代碼
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head:return head# prev直接初始化成None就好prev = Nonecur = headnex = Nonewhile cur:nex = cur.nextcur.next = prevprev = curcur = nexreturn prev
3.回文鏈表
- 解題思路
查找中間鏈表，然后翻轉(zhuǎn)后半段，接著使用雙指針比較判斷即可
時間復(fù)雜度O（N），空間復(fù)雜度O（1） - 代碼
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution:def isPalindrome(self, head: Optional[ListNode]) -> bool:def reverse(head):if not head:return headprev = Nonecur = headnex = Nonewhile cur:nex = cur.nextcur.next = prevprev = curcur = nexreturn previf not head:return Falseif not head.next:return Trueslow = headfast = head.nextwhile fast and fast.next:slow = slow.nextfast = fast.next.nexthead2 = reverse(slow.next)node_1 = headnode_2 = head2while node_1 and node_2:if node_1.val != node_2.val:return Falsenode_1 = node_1.nextnode_2 = node_2.nextreturn True
4. 環(huán)形鏈表
- 題目描述
判斷鏈表是否有環(huán) - 解題思路
快慢指針，快指針一次走一步，慢指針一次走兩步，如果有環(huán)的話，他們一定在環(huán)中相遇。類比于操場跑圈的套圈，對于slow來說，fast是一個節(jié)點一個節(jié)點的靠近slow的
時間復(fù)雜度：O(N)，
空間復(fù)雜度：O(1)。 - 代碼
class Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:if not head or not head.next:return Falsefast = slow = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False
5. 環(huán)形鏈表2
- 題目描述
如果鏈表有環(huán)需要返回入環(huán)的節(jié)點，無環(huán)返回None - 解題思路
圖片來自代碼隨想錄；查找是否有環(huán)和上一題目一樣，使用快慢指針，如果有環(huán)，那么他們一定在環(huán)內(nèi)相遇。如下圖所示，慢指針走過的路程是x + y，快指針走過的路程是 x + y + (y + z) * n，又因為快指針走的路程是慢指針的兩倍，因此有x + y + (y + z) * n = 2* (x + y), 也就是(y + z) * n = x + y, 也就是(y+z)*(n-1) + z = x，那么如果兩個節(jié)點分別從頭結(jié)點和相遇節(jié)點出發(fā)，一定可以在入口節(jié)點處相遇；
時間復(fù)雜度：O(N)，
空間復(fù)雜度：O(1)。
- 代碼
class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return Noneslow = fast = headhas_cycle = Falsewhile fast and fast.next:slow = slow.nextfast = fast.next.nextif fast == slow:has_cycle = Truebreakif not has_cycle:return Nonenode1 = headnode2 = slowwhile node1 != node2:node1 = node1.nextnode2 = node2.nextreturn node1
6. 合并兩個有序鏈表
- 解題思路
是鏈表排序和合并K個有序鏈表等題目要用的基本模塊
時間復(fù)雜度O(n+m)， 空間復(fù)雜度O(n+m) - 代碼
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:if not list1:return list2if not list2:return list1head = ListNode()cur = headnode1 = list1node2 = list2while node1 and node2:if node1.val < node2.val:cur.next = node1node1 = node1.nextelse:cur.next = node2node2 = node2.nextcur = cur.nextif node1:cur.next = node1if node2:cur.next = node2return head.next
7. 兩數(shù)相加
-
題目描述
-
解題思路
注意考慮進(jìn)位、兩個數(shù)字位數(shù)不同的情況
時間復(fù)雜度：O(max(m,n))，其中 m 和 n 分別為兩個鏈表的長度。我們要遍歷兩個鏈表的全部位置，而處理每個位置只需要 O(1) 的時間。
空間復(fù)雜度：O(1)。注意返回值不計入空間復(fù)雜度。 -
代碼
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:if not l1:return l2if not l2:return l1prev = 0n1 = n2 = 0new_head = ListNode()node1 = l1node2 = l2cur = new_headwhile node1 or node2:n1 = node1.val if node1 else 0n2 = node2.val if node2 else 0s = n1 + n2 + prevnode = ListNode(s % 10)prev = s // 10cur.next = nodecur = cur.nextif node1:node1 = node1.nextif node2:node2 = node2.nextif prev != 0:node = ListNode(prev)cur.next = nodereturn new_head.next
8. 刪除鏈表的倒數(shù)第N個節(jié)點
- 解題思路
快慢指針，快指針先走N，然后快慢一起走，當(dāng)快指針走到末尾時，慢指針指向的就是要刪除的節(jié)點 - 代碼
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:if not head:return Nonenew_head = ListNode(0, head)prev = new_headslow = fast = headfor i in range(n):if not fast:raise ValueError("n must greter than length of list")fast = fast.nextwhile fast:prev = slowslow = slow.nextfast = fast.nextprev.next = slow.nextreturn new_head.next
9. 兩兩交換鏈表中的節(jié)點
- 題目描述
給你一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后鏈表的頭節(jié)點。你必須在不修改節(jié)點內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點交換）。 - 解題思路
模擬兩兩交換的過程即可 - 代碼
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head:return headnew_head = ListNode(next=head)cur = headprev = new_headwhile cur and cur.next:next = cur.nextcur.next = next.nextnext.next = curprev.next = nextprev = curcur = prev.nextreturn new_head.next
10. k個一組翻轉(zhuǎn)鏈表
-
題目描述
給你鏈表的頭節(jié)點 head ，每 k 個節(jié)點一組進(jìn)行翻轉(zhuǎn)，請你返回修改后的鏈表。k 是一個正整數(shù)，它的值小于或等于鏈表的長度。如果節(jié)點總數(shù)不是 k 的整數(shù)倍，那么請將最后剩余的節(jié)點保持原有順序。
你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際進(jìn)行節(jié)點交換。
-
解題思路
將前k個節(jié)點切斷成一個鏈表，進(jìn)行翻轉(zhuǎn)，并遞歸對剩下的鏈表進(jìn)行‘k個一組翻轉(zhuǎn)鏈表’操作，再將兩個鏈表連起來，即可 -
代碼
class Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:def reverse(head):if not head:return headprev = Nonecur = headnex = Nonewhile cur:nex = cur.nextcur.next = prevprev = curcur = nexreturn previf not head:return headl = 0node = headwhile node:l += 1node = node.nextif l < k:return headnode = headfor i in range(k - 1):node = node.nextnew_head = node.nextnode.next = Nonereverse_head = reverse(head)head.next = self.reverseKGroup(new_head, k)return reverse_head
11. 隨機(jī)鏈表的復(fù)制
- 解題思路
第一遍循環(huán)，復(fù)制每個節(jié)點，并把他們通過next連接成一個普通的鏈表，同時構(gòu)建哈希表，哈希表的key是舊的節(jié)點，value是復(fù)制的節(jié)點；
第二遍循環(huán)，通過哈希表完成random的指定，注意random可能是空的
時間復(fù)雜度O(N), 空間復(fù)雜度O(N) - 代碼
class Solution:def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':if not head:return headdic = {}node = headnew_head = Node(0)prev = new_headwhile node:new_node = Node(x=node.val)prev.next = new_nodedic[node] = new_nodeprev = new_nodenode = node.nextnode = headwhile node:# 一定要注意原始節(jié)點的random是不是空的if node.random:dic[node].random = dic[node.random]node = node.nextreturn new_head.next
12. 排序鏈表
-
題目描述
-
解題思路
解題思路：歸并排序的思想，找到中間節(jié)點，然后分別對左右兩邊進(jìn)行排序，最后合并左右兩邊的有序鏈表。
這道題目的關(guān)鍵：1. 找到鏈表的中間節(jié)點：用快慢指針實現(xiàn)，慢指針一次走一步，快指針一次走兩步，當(dāng)快指針走到末尾時，慢指針指向的就是中間節(jié)點（不用求出鏈表長度再計算中間節(jié)點的位置）；2.將鏈表從中間節(jié)點切斷成兩個鏈表；3. 合并兩個有序鏈表。
時間復(fù)雜度：O(nlogn)，其中 n 是鏈表的長度。
空間復(fù)雜度：O(logn)，其中 n 是鏈表的長度?？臻g復(fù)雜度主要取決于遞歸調(diào)用的?？臻g。 -
代碼
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution:def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:def merge(l1, l2):if not l1:return l2if not l2:return l1head = ListNode()cur = headnode1 = l1node2 = l2while node1 and node2:if node1.val < node2.val:cur.next = node1node1 = node1.nextelse:cur.next = node2node2 = node2.nextcur = cur.nextif node1:cur.next = node1if node2:cur.next = node2return head.nextif not head or not head.next:return head# 找到中間節(jié)點的方法：快慢指針slow = headfast = head.nextwhile fast and fast.next:slow = slow.nextfast = fast.next.nextnode1 = headnode2 = slow.next# 從中間斷開鏈表slow.next = Nonehead1 = self.sortList(node1)head2 = self.sortList(node2)return merge(head1, head2)
13. 合并k個升序鏈表
- 題目描述
給你一個鏈表數(shù)組，每個鏈表都已經(jīng)按升序排列。
請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。 - 解題思路
分治，通過遞歸兩兩合并，其中會用到合并兩個有序鏈表這個函數(shù)，在上一個題目排序鏈表中也用到了，因此這個模塊函數(shù)要掌握好； - 代碼
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:def merge(l1, l2):if not l1:return l2if not l2:return l1head = ListNode()cur = headnode1 = l1node2 = l2while node1 and node2:if node1.val < node2.val:cur.next = node1node1 = node1.nextelse:cur.next = node2node2 = node2.nextcur = cur.nextif node1:cur.next = node1if node2:cur.next = node2return head.nextn = len(lists)if n == 0:return Noneif len(lists) == 1:return lists[0]mid = n // 2head1 = self.mergeKLists(lists[: mid])head2 = self.mergeKLists(lists[mid :])return merge(head1, head2)
13 LRU
- 題目描述
請你設(shè)計并實現(xiàn)一個滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結(jié)構(gòu)。
實現(xiàn) LRUCache 類：
LRUCache(int capacity) 以 正整數(shù) 作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關(guān)鍵字 key 已經(jīng)存在，則變更其數(shù)據(jù)值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過 capacity ，則應(yīng)該 逐出 最久未使用的關(guān)鍵字。
函數(shù) get 和 put 必須以 O(1) 的平均時間復(fù)雜度運行。 - 解題思路
哈希表 + 雙向鏈表。哈希表用于快速查找節(jié)點，雙向鏈表用于存儲使用情況，最近被使用的節(jié)點被放在雙向鏈表的后端
時間復(fù)雜度： O(1)， 空間復(fù)雜度：O(capacity)。
注意python的字典刪除元素的方法是：pop(key[,default])
刪除字典給定鍵 key 所對應(yīng)的值，返回值為被刪除的值。key值必須給出。 否則，返回default值。 - 代碼
class BiNode:def __init__(self, val=0, next=None, prev=None, key=None):self.val = valself.next = nextself.prev = prevself.key = keyclass LRUCache:def __init__(self, n):self.n = nself.dic = {}self.head = BiNode()self.tail = BiNode()self.head.next = self.tailself.tail.prev = self.headdef add_node_to_tail(self, node):self.tail.prev.next = nodenode.prev = self.tail.prevnode.next = self.tailself.tail.prev = nodedef rm_node(self, node):prev = node.prevnex = node.nextprev.next = nexnex.prev = prevdef get(self, key):if key in self.dic:self.rm_node(self.dic[key])self.add_node_to_tail(self.dic[key])return self.dic[key].valelse:return -1def put(self, key, value):if key in self.dic:self.dic[key].val = valueself.rm_node(self.dic[key])self.add_node_to_tail(self.dic[key])else:if len(self.dic) == self.n:to_delete = self.head.nextself.rm_node(to_delete)self.dic.pop(to_delete.key)new_node = BiNode()new_node.val = valuenew_node.key = keyself.dic[key] = new_nodeself.add_node_to_tail(new_node)# Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value)
總結(jié)
對于鏈表題目，主要的解題思路有：快慢指針、翻轉(zhuǎn)鏈表（局部）、合并有序鏈表、查找中間位置的鏈表節(jié)點、將長鏈表分解切斷成小的鏈表（分治）。
需要熟練掌握的模塊：翻轉(zhuǎn)鏈表、合并有序鏈表、查找中間位置的鏈表節(jié)點
查找中間位置的鏈表節(jié)點，使用快慢指針：
slow = head
fast = head.next
while fast and fast.next:slow = slow.nextfast = fast.next.next