剑指Offer——Week3

发表于 | 分类于 |
字数统计: 4.1k | 阅读时长 ≈ 18

反转链表

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

思考题：

  • 请同时实现迭代版本和递归版本。

样例

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

思路

链表操作，迭代，$O(n)$

翻转即将所有节点的next指针指向前驱节点。
由于是单链表，我们在迭代时不能直接找到前驱节点，所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前，不要忘记保存它的后继节点。

算法时间复杂度

只遍历一次链表，时间复杂度是 $O(n)$

C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
		ListNode* pre = nullptr;
        auto cur = head;
        while(cur){
            auto next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

合并两个排序链表

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

样例

1
2
输入：1->3->5 , 2->4->5
输出：1->2->3->4->5->5

思路

二路归并，$O(n)$

  1. 初始化： 伪头节点$dummy$ ，节点$cur$ 指向$dummy$。
  2. 循环合并： 当$l_1$或$l_2$为空时跳出；
    1. 当$l_1->valval$时，$cur$的后继结点指向$l_1$，并且$l_1$向前走一步；
    2. 当$l_1->val>=l_2->val$时，$cur$的后继结点指向$l_2$，并且$l_2$向前走一步；
    3. 结点$cur$向前走一步，即$cur=cur->next$。
  3. 合并剩余尾部：跳出时有两种情况，即$l_1$为空或$l_2$为空；
    1. 若$l_1\neq null$：将$l_1$添加至结点$cur$之后；
    2. 否则：将$l_2$添加至阶段$cur$之后。
  4. 返回值：合并链表在伪头节点$dummy$之后，因此返回$dummy->next$。

算法时间复杂度

$O(m+n)$：分别为两个链表的长度

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while(l1 != nullptr && l2 != nullptr){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 != nullptr ? l1 : l2;
        return dummy->next;
    }
};

树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。我们规定空树不是任何树的子结构。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
树A：    
     8
    / \
   8   7
  / \
 9   2
    / \
   4   7
树B：
   8
  / \
 9   2
返回：true，因为B是A的子结构。

思路

二叉树，递归，$O(nm)$

  1. 先序遍历树$A$中的每个结点$n_A$——对应函数：isSubStructure(A, B)
  2. 判断树$A$中以$n_A$为根节点的子树是否包含树$B$——对应函数：recur(A, B)

步骤：

recur(A, B)函数：

  1. 终止条件：
    1. 当节点$B$为空：说明树$B$已经匹配完成（越过叶子节点），因此返回true;
    2. 当节点$A$为空：说明已经越过树$A$的叶子节点，即匹配失败，返回false；
    3. 当节点$A$和$B$的值不同：说明匹配失败，返回false；
  2. 返回值：
    1. 判断$A$和$B$的左子节点是否相等，即 recur(A.left, B.left) ；
    2. 判断$A$和$B$的右子节点是否相等，即 recur(A.right, B.right) ；

isSunStructure(A, B)函数：

  1. 特例处理：当树$A$为空或者树$B$为空时，返回false；
  2. 返回值：若树$B$是树$A$的子结构，必须满足以下三种情况之一，用||连接；
    1. 以节点$A$为根节点的子树包含树$B$ ，对应 recur(A, B)；
    2. 树$B$是树$A$左子树的子结构，对应 isSubStructure(A.left, B)；
    3. 树$B$是树$A$右子树的子结构，对应 isSubStructure(A.right, B)；

算法时间复杂度分析

$O(nm)$：分别为两棵树的节点数量

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
		if(!A || !B) return false;
        if(recur(A, B)) return true;
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
    bool recur(TreeNode* A, TreeNode* B){
        if(!B) return true;
        if(!A || A->val != B->val) return false;
        return recur(A->left, B->left) && recur(A->right, B->right);
    }
};

二叉树的镜像

输入一个二叉树，将它变换为它的镜像。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入树：
      8
     / \
    6  10
   / \ / \
  5  7 9 11
 [8,6,10,5,7,9,11,null,null,null,null,null,null,null,null] 
输出树：
      8
     / \
    10  6
   / \ / \
  11 9 7  5
 [8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]

思路

递归，$O(n)$

  • 根据二叉树镜像的定义，递归二叉树交换每个节点的左/右子节点。
  1. 终止条件：当节点$root$为空时（即越过叶子节点），返回nullptr；
  2. 递归条件：
    1. 初始化节点$tmp$，用于暂存$root$的左子节点；
    2. 开启递归右子节点mirrorTree(root->right)，并返回值作为$root$的左子节点；
    3. 开启递归左子节点mirrorTree(tmp)，并返回值作为$root$的右子节点；
  3. 返回值：返回房前节点$root$。

Q： 为何需要暂存$root$的左子节点？
A： 在递归右子节点root->left = mirrorTree(root->right); 执行完毕后，root->left的值已经发生改变，此时递归左子节点mirrorTree(root->left)则会出问题。

辅助栈：

  • 利用栈（或队列）遍历树的所有节点$node$，并交换每个$node$的左/右子节点
  1. 特例处理：当节点$root$为空时，返回nullptr；
  2. 初始化：栈（或队列），并加入根节点$root$；
  3. 循环交换：当栈$stack$为空时跳出；
    1. 出栈：记为$node$；
    2. 添加子节点：将$node$左和右子节点入栈；
    3. 交换：交换$node$的左/右子节点。
  4. 返回值：返回根节点$root$

算法时间复杂度

时间复杂度$O(N)$ ： 其中$N$为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用$O(N)$时间。

C++代码

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
/* 递归 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
		if(root == nullptr) return nullptr;
        TreeNode* tmp = root->left;
        root->left = mirrorTree(root->right);
        root->right = mirrorTree(tmp);
        return root;
    }
};
/* 辅助栈 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            TreeNode* node = s.top();
            s.pop();
            if(node->left != nullptr) s.push(node->left);
            if(node->right != nullptr) s.push(node->right);
            TreeNode* tmp = node->left;
            node->left = node->right;
            node->right = tmp;
        }
        return root;
    }
};

对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树：
    1
   / \
  2   2
 / \ / \
3  4 4  3

如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树：
    1
   / \
  2   2
   \ / \
   4 4  3

思路

自上而下递归，二叉树，$O(n)$

isSynmetric(root)：

  1. 特例处理：若根节点$root$为空，直接返回true；
  2. 返回值：即recur(root->left, root->right);

recur(L, R)：

  1. 终止条件：
    1. 当$L$和$R$同时越过叶子节点：此树自上而下的节点都对称，返回true；
    2. 当$L$或$R$中只有一个越过叶节点：此树步对称，因此返回false；
    3. 当节点$L->val \neq R->val$：此树不对称，因此返回false；
  2. 递推工作：
    1. 判断两个节点$L->left$和$R->right$是否对称：recur(L->left, R->right)；
    2. 判断两个节点$L->right$和$R->left$是否对称：recur(L->right, R->left)；
  3. 返回值：两对节点对称时，才是对称树，逻辑与&&。

算法时间复杂度

$O(n)$：其中$n$为二叉树的节点数量

C++代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return root == nullptr ? true : recur(root->left, root->right);
    }
    bool recur(TreeNode* L, TreeNode* R){
        if(L == nullptr && R == nullptr) return true;
        if(L == nullptr || R == nullptr || L->val != R->val) return false;
        return recur(L->left, R->right) && recur(L->right, R->left);
    }
};

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

样例

1
2
3
4
5
6
7
输入：
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

思路

模拟，$O(n^2)$

  1. 顺时针定义四个方向：上、右、下、左。
  2. 从左上角开始遍历，先往右走，走到不能走为止；
  3. 然后更改到下个方向，再走到不能走为止；
  4. 依次类推，遍历$n^2$ 个格子后停止。

算法时间复杂度

矩阵中每个格子遍历一次，所以总时间复杂度是$O(n^2)$。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
		vector<int> res;
        if (matrix.empty()) return res;
        int n = matrix.size(), m = matrix[0].size();
        
        vector<vector<bool>> st(n, vector<bool>(m, false));		// 记录访问状态
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};		// 定义运动方向
        int x = 0, y = 0, d = 1;					// 初始状态为[0, 0]，初始方向为右：1
        for (int k = 0; k < n * m; k ++ ){
            res.push_back(matrix[x][y]);			// 初始点加入结果数组
            st[x][y] = true;						// 改变当前点的状态为已访问
            int a = x + dx[d], b = y + dy[d];		// 计算下一次的步数
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]){		// 不可达状态
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};

包含min函数的栈

设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

  • push(x)–将元素x插入栈中
  • pop()–移除栈顶元素
  • top()–得到栈顶元素
  • min()–得到栈中最小元素

样例

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin();   --> Returns -4.
minStack.pop();
minStack.top();      --> Returns 3.
minStack.getMin();   --> Returns -1.

思路

辅助栈（单调栈）

函数设计：

  • push(x)函数：保持栈$B$的元素是严格降序的；
    • 将$x$压入栈$A$（即push(x)）；
    • 若栈$B$为空|| x <= B.top()，则将$x$压入栈$B$（即B.push(x)）。
  • pop()函数：保持栈$A$、$B$的元素一致性；
    • 执行A.pop()，将出战元素记为y；
    • 若y == B.top()，则执行$B$出栈（即B.pop()）。
  • top()函数：直接返回栈$A$的栈顶元素即可（A.top()）;
  • min()函数：直接返回栈$B$的栈顶元素即可（B.top()）;

算法时间复杂度

push(), pop(), top(), min() 四个函数的时间复杂度均为常数级别$O(1)$。

C++代码

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
class MinStack {
public:
    stack<int> stackValue;
    stack<int> stackMin;
    MinStack() {

    }
    
    void push(int x) {
		stackValue.push(x);
        if(stackMin.empty() || stackMin.top() >= x)
            stackMin.push(x);
    }
    
    void pop() {
		if(stackMin.top() == stackValue.top()) stackMin.pop();
        stackValue.pop();
    }
    
    int top() {
		return stackValue.top();
    }
    
    int min() {
		return stackMin.top();
    }
};

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。

注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

样例

1
2
3
输入：[1,2,3,4,5]
      [4,5,3,2,1]
输出：true

思路

模拟，辅助栈，$O(n)$

  • 入栈： 按照压栈序列的顺序执行。
  • 出栈： 每次入栈后，循环判断“栈顶元素 == 弹出序列的当前元素”是否成立，将符合弹出序列顺序的栈顶元素全部弹出。

流程：

  1. 初始化：辅助栈stack，弹出序列的索引i；
  2. 遍历压栈序列：各元素记为num；
    1. 元素num入栈；
    2. 循环出栈：若stack.top() == popped[i]; ++i;；
  3. 返回值：若stack为空，则此弹出序列合法

算法时间复杂度

时间复杂度$O(N)$： 其中$N$为列表$pushed$的长度；每个元素最多入栈与出栈一次，即最多共$2N$次出入栈操作。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
		if(pushed.size() != popped.size()) return false;
        stack<int> s;				// 申请辅助栈
        int index = 0; 				// 记录弹出索引
        for(int i = 0; i < pushed.size(); ++i){		// 模拟入栈操作
            s.push(pushed[i]);
            while(!s.empty() && s.top() == popped[index]){
                s.pop();
                ++index;
            }
        }
        if(s.empty()) return true;
        return false;
    }
};

不分行从上往下打印二叉树（层次）

从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

样例

1
2
3
4
5
6
7
8
9
输入：[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4
输出：[8, 12, 2, 6, 4]

思路

BFS，层次遍历，$O(n)$

BFS 通常借助队列的先入先出特性来实现。

  1. 特例处理：当树的结点为空，直接返回[]
  2. 初始化：打印结果列表res = []，包含根节点的队列queue = [root]
  3. BFS循环：当队列queue为空时跳出
    1. 出队：队首元素出队，记为node
    2. 打印：将node->val添加到列表res尾部
    3. 添加子节点：若node的左（右）子树节点不空，则将左（右）子节点加入队列queue
  4. 返回值：返回打印结果列表res即可

算法时间复杂度

时间复杂度$O(N)$：$N$为二叉树的节点数量，即BFS需循环$ N$次。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        if(root == nullptr) return res;
        queue<TreeNode*> q;				// 辅助队列
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            res.push_back(node->val);
            if(node->left != nullptr) q.push(node->left);
            if(node->right != nullptr) q.push(node->right);
        }
        return res; 
    }
};

分行从上往下打印二叉树

从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。

样例

1
2
3
4
5
6
7
8
9
输入：[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4
输出：[[8], [12, 2], [6], [4]]

思路

BFS，$O(n)$

  1. 特例处理：当树的结点为空，直接返回[]（同上）
  2. 初始化：打印结果列表res = []，包含根节点的队列queue = [root]（同上）
  3. BFS循环：当队列queue为空时跳出
    1. 新建一个临时列表tmp，用于存储当前层的打印结果\
    2. 当前层打印循环：循环次数为当前层节点数（队列queue长度）
      1. 出队：队首元素出队，记为node
      2. 打印：将node->val添加到列表tmp尾部
      3. 添加子节点：若node的左（右）子树节点不空，则将左（右）子节点加入队列queue
    3. 当前层结果tmp添加到res
  4. 返回值：返回打印结果列表res即可

算法时间复杂度

时间复杂度$O(N)$：$N$为二叉树的节点数量，即BFS需循环$ N$次。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> res;
        if(root == nullptr) return res;
        queue<TreeNode*> q;				// 辅助队列
        q.push(root);
        while(!q.empty()){
            vector<int> tmp;			// 临时列表
            for(int i = q.size(); i > 0; --i){	// 多一层循环 计算每一层的输出
                TreeNode* node = q.front();
                q.pop();
                tmp.push_back(node->val);
                if(node->left != nullptr) q.push(node->left);
            	if(node->right != nullptr) q.push(node->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

Z字形打印二叉树

请实现一个函数按照之字形顺序从上向下打印二叉树。即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

样例

1
2
3
4
5
6
7
输入：[8, 12, 2, null, null, 6, 4, null, null, null, null]
    8
   / \
  12  2
     / \
    6   4
输出：[[8], [2, 12], [6, 4]]

思路

BFS，$O(n)$

同上一题，偶数层倒叙（res.size() % 2 == 1），奇数层顺序(res.size() % 2 == 0)。

算法时间复杂度

时间复杂度$O(N)$：$N$为二叉树的节点数量，即BFS需循环$ N$次。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> res;
        if(root == nullptr) return res;
        queue<TreeNode*> q;							// 辅助队列
        q.push(root);
        while(!q.empty()){
            vector<int> tmp;						// 临时列表
            for(int i = q.size(); i > 0; --i){		// 多一层循环 计算每一层的输出
                TreeNode* node = q.front();
                q.pop();
                tmp.push_back(node->val);
                if(node->left != nullptr) q.push(node->left);
            	if(node->right != nullptr) q.push(node->right);
            }
            if(res.size() % 2 == 1) reverse(tmp.begin(),tmp.end());
            res.push_back(tmp);
        }
        return res;
    }
};
-------------本文结束 感谢您的阅读-------------

本文标题:剑指Offer——Week3

文章作者:善雯

发布时间:2020年07月14日 - 12:07

最后更新:2020年07月15日 - 20:07

原始链接:http://shanwenyang.github.io/2020/07/14/Offer-Week3/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

原创技术分享，您的支持将鼓励我继续创作
0%