題目列表
鏈表
面試題06. 從尾到頭打印鏈表
面試題18. 刪除鏈表的節(jié)點(diǎn)
面試題22. 鏈表中倒數(shù)第k個節(jié)點(diǎn)
面試題24. 反轉(zhuǎn)鏈表(標(biāo)記)
面試題25. 合并兩個排序的鏈表
面試題35. 復(fù)雜鏈表的復(fù)制（medium）
面試題36. 二叉搜索樹與雙向鏈表(medium)
面試題52. 兩個鏈表的第一個公共節(jié)點(diǎn)
棧
面試題09. 用兩個棧實(shí)現(xiàn)隊(duì)列
面試題30. 包含min函數(shù)的棧
面試題59 - I. 滑動窗口的最大值
鏈表：
面試題06. 從尾到頭打印鏈表
輸入一個鏈表的頭節(jié)點(diǎn)崭孤，從尾到頭反過來返回每個節(jié)點(diǎn)的值（用數(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é)點(diǎn)
給定單向鏈表的頭指針和一個要刪除的節(jié)點(diǎn)的值绍些，定義一個函數(shù)刪除該節(jié)點(diǎn)。
返回刪除后的鏈表的頭節(jié)點(diǎn)昌妹。
注意：此題對比原題有改動
示例 1:
輸入: head = [4,5,1,9], val = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后握截，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.
示例 2:
輸入: head = [4,5,1,9], val = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為 1 的第三個節(jié)點(diǎn)飞崖，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 5 -> 9.
說明：
題目保證鏈表中節(jié)點(diǎn)的值互不相同
若使用 C 或 C++ 語言谨胞，你不需要 free 或 delete 被刪除的節(jié)點(diǎn)
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é)點(diǎn)
輸入一個鏈表固歪，輸出該鏈表中倒數(shù)第k個節(jié)點(diǎn)。為了符合大多數(shù)人的習(xí)慣胯努，本題從1開始計數(shù)牢裳，即鏈表的尾節(jié)點(diǎn)是倒數(shù)第1個節(jié)點(diǎn)术瓮。例如，一個鏈表有6個節(jié)點(diǎn)贰健，從頭節(jié)點(diǎn)開始胞四，它們的值依次是1、2伶椿、3辜伟、4、5脊另、6导狡。這個鏈表的倒數(shù)第3個節(jié)點(diǎn)是值為4的節(jié)點(diǎn)。
示例：
給定一個鏈表: 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. 反轉(zhuǎn)鏈表
定義一個函數(shù)旱捧，輸入一個鏈表的頭節(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)踩麦。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
限制：0 <= 節(jié)點(diǎn)個數(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é)點(diǎn)仍然是遞增排序的谓谦。
示例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. 復(fù)雜鏈表的復(fù)制
示例 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)先的方法，覺得復(fù)雜反粥，不做了卢肃；
面試題36. 二叉搜索樹與雙向鏈表
輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的循環(huán)雙向鏈表才顿。
有點(diǎn)難莫湘？
[圖片上傳中...(image.png-f13ed5-1589009921053-0)]
要求不能創(chuàng)建任何新的節(jié)點(diǎn)，只能調(diào)整樹中節(jié)點(diǎn)指針的指向郑气。
為了讓您更好地理解問題幅垮，以下面的二叉搜索樹為例：
我們希望將這個二叉搜索樹轉(zhuǎn)化為雙向循環(huán)鏈表。鏈表中的每個節(jié)點(diǎn)都有一個前驅(qū)和后繼指針竣贪。對于雙向循環(huán)鏈表军洼，第一個節(jié)點(diǎn)的前驅(qū)是最后一個節(jié)點(diǎn)，最后一個節(jié)點(diǎn)的后繼是第一個節(jié)點(diǎn)演怎。
下圖展示了上面的二叉搜索樹轉(zhuǎn)化成的鏈表匕争。“head” 表示指向鏈表中有最小元素的節(jié)點(diǎn)爷耀。
特別地甘桑，我們希望可以就地完成轉(zhuǎn)換操作。當(dāng)轉(zhuǎn)化完成以后，樹中節(jié)點(diǎn)的左指針需要指向前驅(qū)跑杭，樹中節(jié)點(diǎn)的右指針需要指向后繼铆帽。還需要返回鏈表中的第一個節(jié)點(diǎn)的指針。
這狗題目好難
面試題52. 兩個鏈表的第一個公共節(jié)點(diǎn)
輸入兩個鏈表德谅，找出它們的第一個公共節(jié)點(diǎn)爹橱。
如下面的兩個鏈表：
在節(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 （注意窄做，如果兩個列表相交則不能為 0）愧驱。從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]椭盏，鏈表 B 為 [5,0,1,8,4,5]组砚。在 A 中，相交節(jié)點(diǎn)前有 2 個節(jié)點(diǎn)掏颊；在 B 中糟红，相交節(jié)點(diǎn)前有 3 個節(jié)點(diǎn)。
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. 用兩個棧實(shí)現(xiàn)隊(duì)列
用兩個棧實(shí)現(xiàn)一個隊(duì)列乌叶。隊(duì)列的聲明如下盆偿，請實(shí)現(xiàn)它的兩個函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能枉昏。(若隊(duì)列中沒有元素陈肛，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解析：
刪除隊(duì)首deleteHead()函數(shù)： 有以下三種情況。
當(dāng)棧 B 不為空： B中仍有已完成倒序的元素兄裂，因此直接返回 B 的棧頂元素。
否則阳藻，當(dāng) A 為空： 即兩個棧都為空晰奖，無元素，因此返回 -1?1 腥泥。
否則： 將棧 A 元素全部轉(zhuǎn)移至棧 B 中匾南，實(shí)現(xiàn)元素倒序，并返回棧 B 的棧頂元素蛔外。
面試題30. 包含min函數(shù)的棧
定義棧的數(shù)據(jù)結(jié)構(gòu)蛆楞，請在該類型中實(shí)現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min夹厌、push 及 pop 的時間復(fù)雜度都是 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ù)： 重點(diǎn)為保持棧 B 的元素是 非嚴(yán)格降序 的。
將 x 壓入棧 A （即 A.add(x) ）矛纹；
若 ① 棧 B 為空 或 ② x 小于等于 棧 B 的棧頂元素臂聋，則將 xx 壓入棧 BB （即 B.add(x) ）。
pop() 函數(shù)： 重點(diǎn)為保持棧 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
暴力法的算法的時間復(fù)雜度是O(n)权她，當(dāng)要求優(yōu)化算法虹茶，算法時間復(fù)雜讀是O(1)時，使用一個隊(duì)列來記錄最大值
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. 隊(duì)列的最大值
請定義一個隊(duì)列并實(shí)現(xiàn)函數(shù) max_value 得到隊(duì)列里的最大值伴奥，要求函數(shù)max_value写烤、push_back 和 pop_front 的均攤時間復(fù)雜度都是O(1)。
若隊(duì)列為空拾徙，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]
均攤時間復(fù)雜度為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
