【leetcode刷题之路】面试经典150题（4）—

文章目录

- - 7 栈
  - - 7.1 【哈希表】有效的括号
    - 7.2【栈】简化路径
    - 7.3 【栈】最小栈
    - 7.4 【栈】逆波兰表达式求值
    - 7.5 【栈】基本计算器
  - 8 链表
  - - 8.1 【双指针】环形链表
    - 8.2 【双指针】两数相加
    - 8.3 【双指针】合并两个有序链表
    - 8.4 【哈希表】随机链表的复制
    - 8.5 【链表】反转链表 II
    - 8.6 【链表】K 个一组翻转链表
    - 8.7 【双指针】删除链表的倒数第 N 个结点
    - 8.8 【双指针】删除排序链表中的重复元素 II
    - 8.9 【双指针】旋转链表
    - 8.10 【双链表】分隔链表
    - 8.11 【双向链表】【哈希表】LRU 缓存

7 栈

7.1 【哈希表】有效的括号

题目地址：https://leetcode.cn/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-interview-150

先构建一个括号的哈希表，引入 $\#$ 是防止只有右括号时无法与栈顶元素进行匹配。

class Solution:
    def isValid(self, s: str) -> bool:
        dict = {'(':')','{':'}','[':']','#':'#'}
        stack = ['#']
        for c in s:
            if c in dict:
                stack.append(c)
            else:
                if dict[stack.pop()] != c:
                    return False
        return len(stack) == 1

7.2【栈】简化路径

题目地址：https://leetcode.cn/problems/simplify-path/description/?envType=study-plan-v2&envId=top-interview-150

按照规则构建栈即可，注意遇到 $..$ 时要把栈顶元素出栈。

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        items = path.split("/")

        for item in items:
            if stack and item == "..":
                stack.pop()
            else:
                if item not in [".","..",""]:
                    stack.append(item)
        return "/" + "/".join(stack)

7.3 【栈】最小栈

题目地址：https://leetcode.cn/problems/min-stack/description/?envType=study-plan-v2&envId=top-interview-150

详见代码。

class MinStack:

    def __init__(self):
        self.num = []

    def push(self, val: int) -> None:
        self.num.append(val)

    def pop(self) -> None:
        self.num.pop()

    def top(self) -> int:
        return self.num[-1]

    def getMin(self) -> int:
        return min(self.num)

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

7.4 【栈】逆波兰表达式求值

题目地址：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/?envType=study-plan-v2&envId=top-interview-150

构建数字栈，遇到运算符将栈中最顶上的两个元素进行计算再压栈，最后输出栈顶元素。

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        num = []
        for i in range(len(tokens)):
            if tokens[i] not in ["+","-","*","/"]:
                num.append(tokens[i])
            else:
                x2 = int(float(num.pop()))
                x1 = int(float(num.pop()))
                if tokens[i] == "+":
                    x = x1 + x2
                    num.append(str(x))
                elif tokens[i] == "-":
                    x = x1 - x2
                    num.append(str(x))
                elif tokens[i] == "*":
                    x = x1 * x2
                    num.append(str(x))
                elif tokens[i] == "/":
                    x = x1 / x2
                    num.append(str(x))
        return int(float(num.pop()))

7.5 【栈】基本计算器

题目地址：https://leetcode.cn/problems/basic-calculator/description/?envType=study-plan-v2&envId=top-interview-150

设置当前数字numnumnum和符号判断signsignsign（统一为加法）：

如果当前是数字，更新当前数字 $n u m$ ；
如果当前是操作符 $+$ 或者 $-$ ，更新当前计算结果 $an s$ ，并把当前数字 $n u m$ 设为 $0$ ， $s i g n$ 根据相应的操作符设置为 $1$ 或者 $- 1$ ，继续循环；
如果当前是 $($ ，那么说明遇到了左括号，而后面括号里的内容需要先计算，这时把 $an s, s i g n$ 进栈，更新 $an s$ 和 $s i g n$ 为新的循环开始；
如果当前是 $)$ ，那么说明遇到了右括号，即当前括号里的内容已经计算完毕，所以要把之前的结果出栈，然后计算整个表达式的结果；
最后，当字符串遍历结束的时候，需要把最后的一个 $n u m$ 也更新到 $an s$ 中。

class Solution:
    def calculate(self, s: str) -> int:
        ans,num,sign = 0,0,1
        stack = []

        for c in s:
            if c >= "0" and c <= "9":
                num = num*10 + int(c)
            elif c == "+" or c == "-":
                ans += num*sign
                num = 0
                sign = 1 if c == "+" else -1
            elif c == "(":
                stack.append(ans)
                stack.append(sign)
                ans = 0
                sign = 1
            elif c == ")":
                ans += num*sign
                num = 0
                ans = ans * stack.pop()
                ans = ans + stack.pop()
        ans += num*sign
        return ans

8 链表

8.1 【双指针】环形链表

题目地址：https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-interview-150

设置快慢指针，快指针一次走两步，慢指针一次走一步，如果快慢指针相遇，则说明遇到了环。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        fp,sp = head,head
        while fp and fp.next:
            fp = fp.next.next
            sp = sp.next
            if sp == fp:
                return True
        return False

8.2 【双指针】两数相加

题目地址：https://leetcode.cn/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-interview-150

方法一：将两个链表的数字分别计算出来，相加，然后按照结果构造链表。

方法二：直接计算两个链表各自位的和，设置进位标志，然后诸位构造链表。

# 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]:
        x1,x2 = 0,0
        l1p,l2p = l1,l2
        i,j = 1,1
        while l1p:
            x1 += i*l1p.val
            l1p = l1p.next
            i *= 10
        while l2p:
            x2 += j*l2p.val
            l2p = l2p.next
            j *= 10
        x = x1 + x2
        ans = l = ListNode()
        if x == 0:
            l.next = ListNode(0)
        else:
            while x:
                l.next = ListNode(x%10)
                x = x // 10
                l = l.next
        return ans.next
# 方法二
# 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]:
        ans = l = ListNode()
        sign = 0

        while l1 or l2:
            l1_num = l1.val if l1 else 0
            l2_num = l2.val if l2 else 0
            num = l1_num + l2_num + sign
            l.next = ListNode(num%10)
            sign = num//10
            l = l.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if sign:
            l.next = ListNode(sign)
        return ans.next

8.3 【双指针】合并两个有序链表

题目地址：https://leetcode.cn/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-interview-150

详见代码。

# 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]:
        l1p,l2p = list1,list2
        ans = l = ListNode()
        while l1p and l2p:
            if l1p.val <= l2p.val:
                l.next = ListNode(l1p.val)
                l1p = l1p.next
                l = l.next
            else:
                l.next = ListNode(l2p.val)
                l2p = l2p.next
                l = l.next
        while l1p:
            l.next = ListNode(l1p.val)
            l1p = l1p.next
            l = l.next
        while l2p:
            l.next = ListNode(l2p.val)
            l2p = l2p.next
            l = l.next
        return ans.next

8.4 【哈希表】随机链表的复制

题目地址：https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150

利用哈希表，首先构建链表中的每个结点，再根据哈希表中的结点分别构造 $n e x t$ 和 $r an d o m$ 引用，相当于对原始链表遍历两次。

"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
        dict = {}
        cur = head
        while cur:
            dict[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            dict[cur].next = dict.get(cur.next)
            dict[cur].random = dict.get(cur.random)
            cur = cur.next
        if not head:
            return head
        else:
            return dict[head]

8.5 【链表】反转链表 II

题目地址：https://leetcode.cn/problems/reverse-linked-list-ii/description/?envType=study-plan-v2&envId=top-interview-150

超赞题解+配图：点击查看

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        ans = pre = ListNode()
        ans.next = head
        cnt = 1

        while pre.next and cnt < left:
            pre = pre.next
            cnt += 1
        
        cur = pre.next
        tail = cur
        while cur and cnt <= right:
            nxt = cur.next
            cur.next = pre.next
            pre.next = cur
            tail.next = nxt
            cur = nxt
            cnt += 1
        return ans.next

8.6 【链表】K 个一组翻转链表

题目地址：https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-interview-150

在上一题的基础上，先计算链表长度，然后按照 $k$ 进行分组，每一组进行翻转。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # singly-linked length
        length = 0
        tmp = head
        while tmp:
            length += 1
            tmp = tmp.next
        # reverse
        ans = pre = ListNode()
        ans.next = head
        left,right = 1,k

        while right <= length:
            pre = ans
            cnt = 1
            while pre.next and cnt < left:
                pre = pre.next
                cnt += 1
            cur = pre.next
            tail = cur
            while cur and cnt <= right:
                nxt = cur.next
                cur.next = pre.next
                pre.next = cur
                tail.next = nxt
                cur = nxt
                cnt += 1
            left += k
            right += k
        return ans.next

8.7 【双指针】删除链表的倒数第 N 个结点

题目地址：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-interview-150

设置双指针，先让一个指针往前走 $n$ 步，再让两个指针一起走， $r i g h t$ 指针走到头就是要删除的结点。

# 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]:
        left = right = head
        cnt = 0
        while cnt < n:
            right = right.next
            cnt += 1
        
        if not right:
            return head.next
        
        while right.next:
            left = left.next
            right = right.next
        left.next = left.next.next
        return head

8.8 【双指针】删除排序链表中的重复元素 II

题目地址：https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/?envType=study-plan-v2&envId=top-interview-150

设置快慢指针，记录重复的数字，然后删除相应结点，但是要注意链表要多设置一个头结点，防止出现链表中元素都一样的情况。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ans = ListNode()
        ans.next = head

        slow,fast = ans,ans.next
        while fast:
            while fast and fast.next and fast.val == fast.next.val:
                repute_num = fast.val
                while fast and fast.val == repute_num:
                    fast = fast.next
                slow.next = fast
            if fast:
                slow = fast
                fast = fast.next
        return ans.next

8.9 【双指针】旋转链表

题目地址：https://leetcode.cn/problems/rotate-list/description/?envType=study-plan-v2&envId=top-interview-150

先计算链表长度，找出右移的相对最小数，然后根据这个最小数设置双指针，找到倒数第 $k$ 个元素，将链表一分两半重新拼接。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # length
        length = 0
        tmp = head
        while tmp:
            length += 1
            tmp = tmp.next
        if length != 0:
            k %= length
        # particular situation
        if not head or not head.next or k == 0:
            return head
        # rotate list
        slow,fast = head,head
        while k:
            fast = fast.next
            k -= 1
        while fast.next:
            slow = slow.next
            fast = fast.next
        ans = slow.next
        slow.next = None
        fast.next = head
        return ans

8.10 【双链表】分隔链表

题目地址：https://leetcode.cn/problems/partition-list/description/?envType=study-plan-v2&envId=top-interview-150

设置两个链表，一个链表存放比 $x$ 小的元素，另一个链表存放大于等于 $x$ 的元素，然后将两个链表合并即可，最后注意要让 $bi g$ 的下一个结点为空，否则容易成环。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        sml = sml_list = ListNode()
        big = big_list = ListNode()
        while head:
            if head.val < x:
                sml.next = head
                sml = sml.next
            else:
                big.next = head
                big = big.next
            head = head.next
        sml.next = big_list.next
        big.next = None
        return sml_list.next

8.11 【双向链表】【哈希表】LRU 缓存

题目地址：https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-interview-150

详见代码，通过构造双向链表和哈希表来模拟LRU缓存，要注意及时将最久未使用的结点移动到链表末尾，便于删除，这里采取的措施是定义一个函数，将链表中的某个结点移动到链表末尾，在 $g e t$ 和 $p u t$ 方法中都会遇到这种情况。

class ListNode:
    # 双向链表构建
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        # 头结点head和尾结点tail
        self.head = ListNode()
        self.tail = ListNode()
        # 初始化双向链表
        self.head.next = self.tail
        self.tail.prev = self.head

    # 将链表中的某个结点移到链表末尾tail
    def move_to_tail(self, key):
        node = self.hashmap[key]
        # 取出node结点
        node.next.prev = node.prev
        node.prev.next = node.next
        # 移到末尾
        node.next = self.tail
        node.prev = self.tail.prev
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key in self.hashmap:
            self.move_to_tail(key)
        res = self.hashmap.get(key)
        if res == None:
            return -1
        else:
            return res.value

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            self.hashmap[key].value = value
            self.move_to_tail(key)
        else:
            if len(self.hashmap) == self.capacity:
                # 删除最久未访问结点
                self.hashmap.pop(self.head.next.key)
                self.head.next = self.head.next.next
                self.head.next.prev = self.head
            newNode = ListNode(key, value)
            self.hashmap[key] = newNode
            newNode.prev = self.tail.prev
            newNode.next = self.tail
            self.tail.prev.next = newNode
            self.tail.prev = newNode

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)