題目列表
鏈表
面試題06. 從尾到頭打印鏈表
面試題18. 刪除鏈表的節(jié)點
面試題22. 鏈表中倒數(shù)第k個節(jié)點
面試題24. 反轉鏈表(標記)
面試題25. 合并兩個排序的鏈表
面試題35. 復雜鏈表的復制（medium）
面試題36. 二叉搜索樹與雙向鏈表(medium)
面試題52. 兩個鏈表的第一個公共節(jié)點
棧
面試題09. 用兩個棧實現(xiàn)隊列
面試題30. 包含min函數(shù)的棧
面試題59 - I. 滑動窗口的最大值
鏈表：
面試題06. 從尾到頭打印鏈表
輸入一個鏈表的頭節(jié)點，從尾到頭反過來返回每個節(jié)點的值（用數(shù)組返回）。
示例 1：
輸入：head = [1,3,2]
輸出：[2,3,1]
遞歸法：
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
return self.reversePrint(head.next) +[head.val] if head else []
棧：
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
stack = []
while head:
stack.append(head.val)
head = head.next
return stack[::-1]
非常簡單
面試題18. 刪除鏈表的節(jié)點
給定單向鏈表的頭指針和一個要刪除的節(jié)點的值，定義一個函數(shù)刪除該節(jié)點。
返回刪除后的鏈表的頭節(jié)點。
注意：此題對比原題有改動
示例 1:
輸入: head = [4,5,1,9], val = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節(jié)點，那么在調用了你的函數(shù)之后，該鏈表應變?yōu)?4 -> 1 -> 9.
示例 2:
輸入: head = [4,5,1,9], val = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為 1 的第三個節(jié)點，那么在調用了你的函數(shù)之后，該鏈表應變?yōu)?4 -> 5 -> 9.
說明：
題目保證鏈表中節(jié)點的值互不相同
若使用 C 或 C++ 語言，你不需要 free 或 delete 被刪除的節(jié)點
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if head.val == val: return head.next
pre, cur = head, head.next
while cur and cur.val != val:
pre, cur = cur, cur.next
if cur:
pre.next = cur.next
return head
面試題22. 鏈表中倒數(shù)第k個節(jié)點
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個節(jié)點。為了符合大多數(shù)人的習慣，本題從1開始計數(shù)，即鏈表的尾節(jié)點是倒數(shù)第1個節(jié)點。例如，一個鏈表有6個節(jié)點，從頭節(jié)點開始，它們的值依次是1、2、3、4、5、6。這個鏈表的倒數(shù)第3個節(jié)點是值為4的節(jié)點。
示例：
給定一個鏈表: 1->2->3->4->5, 和 k = 2.
返回鏈表 4->5.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
p = q = head
count = 0
while q:
if count >= k:
p = p.next
count += 1
q = q.next
return p if count >= k else None
寫法2，同樣思路不同寫法
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
slow = head
fast = head
for _ in range(k):
if not fast: return None
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow
面試題24. 反轉鏈表
定義一個函數(shù)，輸入一個鏈表的頭節(jié)點，反轉該鏈表并輸出反轉后鏈表的頭節(jié)點。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
限制：0 <= 節(jié)點個數(shù) <= 5000
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
curr = head
while curr:
tmp = curr.next
curr.next = pre
pre = curr
curr = tmp
return pre
emmm,每次都頭大，來回來去的搞混
面試題25. 合并兩個排序的鏈表
輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的節(jié)點仍然是遞增排序的。
示例1：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
限制：0 <= 鏈表長度 <= 1000
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
node = dummy
while l1 and l2:
if l1.val > l2.val:
node.next = l2
l2 = l2.next
else:
node.next = l1
l1 = l1.next
node = node.next
node.next = l1 if l1 else l2
return dummy.next
基本操作。
面試題35. 復雜鏈表的復制
示例 1：
輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
解法1 深度優(yōu)先
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
def dfs(head):
if not head: return None
if head in visited:
return visited[head]
copy = Node(head.val, None, None)
visited[head] = copy
copy.next = dfs(head.next)
copy.random = dfs(head.random)
return copy
visited = {}
return dfs(head)
還有迭代和廣度優(yōu)先的方法，覺得復雜，不做了；
面試題36. 二叉搜索樹與雙向鏈表
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的循環(huán)雙向鏈表。
有點難？
[圖片上傳中...(image.png-f13ed5-1589009921053-0)]
要求不能創(chuàng)建任何新的節(jié)點，只能調整樹中節(jié)點指針的指向。
為了讓您更好地理解問題，以下面的二叉搜索樹為例：
我們希望將這個二叉搜索樹轉化為雙向循環(huán)鏈表。鏈表中的每個節(jié)點都有一個前驅和后繼指針。對于雙向循環(huán)鏈表，第一個節(jié)點的前驅是最后一個節(jié)點，最后一個節(jié)點的后繼是第一個節(jié)點。
下圖展示了上面的二叉搜索樹轉化成的鏈表?！癶ead” 表示指向鏈表中有最小元素的節(jié)點。
特別地，我們希望可以就地完成轉換操作。當轉化完成以后，樹中節(jié)點的左指針需要指向前驅，樹中節(jié)點的右指針需要指向后繼。還需要返回鏈表中的第一個節(jié)點的指針。
這狗題目好難
面試題52. 兩個鏈表的第一個公共節(jié)點
輸入兩個鏈表，找出它們的第一個公共節(jié)點。
如下面的兩個鏈表：
在節(jié)點 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é)點的值為 8 （注意，如果兩個列表相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。在 A 中，相交節(jié)點前有 2 個節(jié)點；在 B 中，相交節(jié)點前有 3 個節(jié)點。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
p1 = headA
p2 = headB
while p1 != p2:
p1 = headB if p1 is None else p1.next
p2 = headA if p2 is None else p2.next
return p1
======================================================
棧
面試題09. 用兩個棧實現(xiàn)隊列
用兩個棧實現(xiàn)一個隊列。隊列的聲明如下，請實現(xiàn)它的兩個函數(shù) appendTail 和 deleteHead ，分別完成在隊列尾部插入整數(shù)和在隊列頭部刪除整數(shù)的功能。(若隊列中沒有元素，deleteHead 操作返回 -1 )
示例 1：
輸入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
輸出：[null,null,3,-1]
示例 2：
輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]
class CQueue:
def __init__(self):
self.A, self.B = [], []
def appendTail(self, value: int) -> None:
self.A.append(value)
def deleteHead(self) -> int:
if self.B:
return self.B.pop()
if not self.A:
return -1
while self.A:
self.B.append(self.A.pop())
return self.B.pop()
deleteHead解析：
刪除隊首deleteHead()函數(shù)： 有以下三種情況。
當棧 B 不為空： B中仍有已完成倒序的元素，因此直接返回 B 的棧頂元素。
否則，當 A 為空： 即兩個棧都為空，無元素，因此返回 -1?1 。
否則： 將棧 A 元素全部轉移至棧 B 中，實現(xiàn)元素倒序，并返回棧 B 的棧頂元素。
面試題30. 包含min函數(shù)的棧
定義棧的數(shù)據(jù)結構，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中，調用 min、push 及 pop 的時間復雜度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
解題思路：
push(x) 函數(shù)： 重點為保持棧 B 的元素是 非嚴格降序 的。
將 x 壓入棧 A （即 A.add(x) ）；
若 ① 棧 B 為空 或 ② x 小于等于 棧 B 的棧頂元素，則將 xx 壓入棧 BB （即 B.add(x) ）。
pop() 函數(shù)： 重點為保持棧 A,B 的 元素一致性 。
執(zhí)行棧 A 出棧（即 A.pop() ），將出棧元素記為 y ；
若 y 等于棧 B 的棧頂元素，則執(zhí)行棧 B 出棧（即 B.pop() ）。
top() 函數(shù)： 直接返回棧 A 的棧頂元素即可
min() 函數(shù)： 直接返回棧 B 的棧頂元素即可
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.s1 = []
self.s2 = []
def push(self, x: int) -> None:
self.s1.append(x)
if not self.s2 or self.s2[-1] >= x:
self.s2.append(x)
def pop(self) -> None:
if self.s1.pop() == self.s2[-1]: ##這注意下
self.s2.pop()
def top(self) -> int:
return self.s1[-1]
def min(self) -> int:
return self.s2[-1]
面試題59 - I. 滑動窗口的最大值
給定一個數(shù)組 nums 和滑動窗口的大小 k，請找出所有滑動窗口里的最大值。
示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
滑動窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
暴力的遍歷法解題
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or k== 0: return []
res = []
for i in range(0, len(nums)-k+1):
res.append(max(nums[i:i+k]))
return res
暴力法的算法的時間復雜度是O(n)，當要求優(yōu)化算法，算法時間復雜讀是O(1)時，使用一個隊列來記錄最大值
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or k== 0: return []
deque = collections.deque()
res = []
for i in range(k):
while deque and deque[-1] < nums[i]: deque.pop()
deque.append(nums[i])
res.append(deque[0])
for i in range(k, len(nums)):
if deque[-1] == nums[i-k]: deque.popleft()
while deque and deque[-1] < nums[i]: deque.pop()
deque.append(nums[i])
res.append(deque[0])
return res
面試題59 - II. 隊列的最大值
請定義一個隊列并實現(xiàn)函數(shù) max_value 得到隊列里的最大值，要求函數(shù)max_value、push_back 和 pop_front 的均攤時間復雜度都是O(1)。
若隊列為空，pop_front 和 max_value 需要返回 -1
示例 1：
輸入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
輸出: [null,null,null,2,1,2]
示例 2：
輸入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
輸出: [null,-1,-1]
均攤時間復雜度為O(1)
import queue
class MaxQueue:
def __init__(self):
self.deque = queue.deque()
self.queue = queue.Queue()
def max_value(self) -> int:
return self.deque[0] if self.deque else -1
def push_back(self, value: int) -> None:
while self.deque and self.deque[-1] < value:
self.deque.pop()
self.deque.append(value)
self.queue.put(value)
def pop_front(self) -> int:
if not self.deque:
return -1
ans = self.queue.get()
if ans == self.deque[0]:
self.deque.popleft()
return ans
