LeetCode 剑指Offer

剑指 Offer 05. 替换空格

题目描述

​ 请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

  • 实例：

    1
    2
    输入：s = "We are happy."
    输出："We%20are%20happy."

  • 限制

    • 0 <= s 的长度 <= 10000

解题思路

  • 解题思路:

    1. 遍历链表压入栈，最后返回依次出栈的数组。
    2. 递归遍历链表，遍历到底后压入vector。

实现代码

  1. Python解法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution:
        def reversePrint(self, head: ListNode) -> List[int]:
            res = []
            while head:
                res.append(head.val)
                head = head.next
            return res[::-1]

  2. C++解法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */

    class Solution {
    vector<int> a;
    public:
        vector<int> reversePrint(ListNode* head) {
            if(!head) 
                return a;
            reversePrint(head->next);
            arr.push_back(head->val);
            return a;
        }
    };

剑指 Offer 24. 反转链表

题目描述

​ 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

  • 实例

    1
    2
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

  • 限制

    • 0 <= 节点个数 <= 5000

解题思路

  • 解题思路:

​ 1. 申请动态扩容容器辅助；

​ 2. 双指针法:每次遍历当前指针cur与上一个指针pre的next互换位置；空间O(1)

​ 3. ==递归==：head->next->next = head

递归.gif

  • 递归的终止条件为head==None or head.next==None;
  • cur为最后的返回结果，cur的第一个值为顺序链表的最后一个Node, 即当前head或head.next;
  • head.next.next = next即cur.next = head与双指针类似。

实现代码

  1. C++解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 双指针法:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head, *pre = nullptr;
        while(cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};
  1. Python解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 双指针法

# 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:
        cur,pre = head,None
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre
        
    
# 递归法
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if(head==None or head.next==None):
            return head
        cur = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return cur

剑指 Offer 35. 复杂链表的复制

题目描述

  • 题目描述

​ 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

img

img

img

1
2
3
4
5
6
7
8
9
10
11
12
# 实例
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

输入: head = []
输出: []
  • 提示
    • -10000 <= Node.val <= 10000
    • Node.random 为空（null）或指向链表中的节点。
    • 节点数目不超过 1000 。

解题思路

  • 解题思路

    • 对链表进行深拷贝。

    ==首先看：普通链表的拷贝==

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Node:
        def __init__(self, x: int, next: 'Node' = None):
            self.val = int(x)
            self.next = next
            
    class Solution:
        def copyList(self, head: 'Node') -> 'Node':
            cur = head
            dum = pre = Node(0)
            while cur:
                node = Node(cur.val)
                pre.next = node
                cur = cur.next
                pre = node
            return dum

    ==本题的链表结构==

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    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':
                    cur = head
            dum = pre = Node(0)
            while cur:
                node = Node(cur.val)
                pre.next = node
                # pre.random = ??? # 无法获取当前链表的Random节点
                cur = cur.next
                pre = node
            return dum

因此:

  1. hashMap构造法（时间复杂度O(n), 空间复杂度O(n))

    考虑到新链表与旧链表存在一一对应的关系，所以构建原链表->新链表的映射关系，再遍历原链表来构建新链表的next与random拷贝进新链表中。

    img

  2. 拼接+拆分法（时间复杂度O(n), 空间复杂度O(1))

    (1) 复制原来的各个节点, 构建拼接链表

    (2) 构建新链表各个节点的random指向

    (3) 拆分原/新链表

    (4) 返回新链表的头节点res即可

    img

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# hashmap法
"""
# 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':
        if not head:
            return
        hashmap = {}
        cur = head
        while cur:
            hashmap[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            hashmap[cur].next = hashmap.get(cur.next)
            hashmap[cur].random = hashmap.get(cur.random)
            cur = cur.next
        return hashmap[head]
    

# 拼接/拆分法
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return
        cur = head
        # 复制节点
        while cur:
            temp = Node(cur.val)
            temp.next = cur.next
            cur.next = temp
            cur = temp.next

        # 拷贝源节点的random给新节点
        cur = head
        while cur:
            # 判断是否非None
            if cur.random:
                # 之所以后半要取random.next而不是random在于需要链接的random为拷贝的新节点，即random.next
                cur.next.random = cur.random.next
            cur = cur.next.next
        
        # 分离所需新链表, 新链表头节点为head的拷贝节点
        res = cur = head.next
        while cur.next:
            cur.next = cur.next.next
            cur = cur.next
        return res

2023.2.3 今日收获

今天的题目属于 链表 的基础数据结构。

​ 第一、二题都比较简单，根据昨天的经验，可以申请一个辅助容器(栈)来协助所需操作，当然也可以通过递归的方法，先递归到最深的节点，最后再倒序

​ 第三题的话涉及到一个深拷贝的问题，解决的办法是与简单链表进行对比，查看所需步骤的区别，最后是通过哈希表/拼接拆分法来解决问题。