《剑指offer》week3

问题一：反转链表

题目描述

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

样例

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

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

题目分析

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

翻转即将所有节点的$next$指针指向前驱节点。

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

时空复杂度分析

空间复杂度分析：遍历时只有3个额外变量，所以额外的空间复杂度是$O(1)$。

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

C++代码

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;
	}
}

总结

这里需要注意的是就是链表的指针要注意在指向其它节点之后，原来的next指针就会失效了，题目中要用到哪几个指针就需要定义几个指针

问题二：合并两个有序的链表

问题描述

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

样例

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

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

问题分析

(二路归并) $O(n)$

• 新建头部的保护结点dummy，设置cur指针指向dummy。

• 若当前l1指针指向的结点的值val比l2指针指向的结点的值val小，则令cur的next指针指向l1，且l1后移；否则指向l2，且l2后移。
• 然后cur指针按照上一部设置好的位置后移。

• 循环以上步骤直到l1或l2为空。

• 将剩余的l1或l2接到cur指针后边。

时间复杂度

两个链表各遍历一次，所以时间复杂度为$O(n)$

C++代码

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
    	ListNode* dummy=new ListNode();
    	auto cur=dummy;
    	while(l1&&l2){
  			if(l1->val<l2->val){
  				cur->next=l1;
  				cur=l1;
  				l1=l1->next;
			}
			if(l1->val>=l2->val){
  				cur->next=l2;
  				cur=l2;
  				l2=l2->next;
			}
		}
		if(l1){
  			cur->next=l1;
		}
		if(l2){
  			cur->next=l2;
		}
		return dummy->next;
	}
}

总结

关于头指针：

• 在线性表的链式存储结构中,头指针是指链表指向第一个结点的指针 ,若链表有头结点,则头指针就是指向链表头结点的指针。

• 头指针具有标识作用,故常用头指针冠以链表的名字。

• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

关于头结点:

• 头结点是为了操作的统一与方便而设立的,放在第一 个元素结点之前，其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等)。

• 有了头结点后，对在第一个元素结点前插入结点和删除第一个结点,其操作与对其它结点的操作统一了。

• 首元结点也就是第一 个元素的结点,它是头结点后边的第一 个结点。
• 头结点不是链表所必需的。

具体到这个题目上就是说我们设置一个头结点的作用就是不需要判断这个题目中的参数l1和l2是否为空，直接进行后面的移动指针的操作就可以。

问题三：树的子结构

问题描述

输入两棵二叉树A，B，判断B是不是A的子结构。

我们规定空树不是任何树的子结构。

样例

树A：

    8
   / \
  8   7
 / \
9   2
   / \
  4   7

树B：

  8
 / \
9   2

返回 true ,因为B是A的子结构。

问题分析

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

代码分为两个部分：

1. 遍历树A中的所有非空节点R；

2. 判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；

对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。

对于第二部分，我们同时从根节点开始遍历两棵子树：

• 如果树B中的节点为空，则表示当前分支是匹配的，返回true；

• 如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；

• 如果两个节点都不为空，但数值不同，则说明不匹配，返回false；

• 否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；

时间复杂度

最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。

所以时间复杂度是$O(nm)$，其中$n$是树A中的节点数，$m$ 是树B中的节点数。

C++代码

class Solution {
public:
    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
    	if(!pRoot1||!pRoot2) return false;   //终止错误的条件
    	if(isPart(pRoot1,pRoot2)) return true;   //终止正确的条件
    	return hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2)  //继续递归
    }
  	bool isPart(TreeNode* p1,TreeNode* p2){  //判断以p1和p2为根节点的子树是否相同
  		if(!p2) return true;   //终止正确的条件
      	if(!p1||p1->val!=p2->val) return false;    //终止错误的条件
      	return isPart(p1->left,p2->right)&&isPart(p1->right,p2->right);    //继续递归
	}
}

总结

这种题目在递归的时候需要三步：

• 终止错误的条件
• 终止正确的条件（这一步一般都是找分析什么情况下是正确的，写一个函数，如这里的isPart()函数）
• 继续递归

问题四：二叉树的镜像

问题描述

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

样例

输入树：
      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)$

仔细观察原树和镜像之后的树：

我们可以发现镜像后的树就是将原树的所有节点的左右儿子互换！

所以我们递归遍历原树的所有节点，将每个节点的左右儿子互换即可。

时间复杂度

原树仅被遍历一次，所以时间复杂度是$O(n)$。

C++代码

class Solution {
public:
    void mirror(TreeNode* root) {
        if (!root) return;
        swap(root->left, root->right);
        mirror(root->left);
        mirror(root->right);
    }
};

总结

这个题目采用先序遍历或者是后续遍历都可以

问题五：对称的二叉树

问题描述

请实现一个函数，用来判断一棵二叉树是不是对称的。

如果一棵二叉树和它的镜像一样，那么它是对称的。

样例

如下图所示二叉树[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
 / \ / \
3  4 4  3

问题分析

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

递归判断两个子树是否互为镜像。

两个子树互为镜像当且仅当：

• 两个子树的根节点值相等；

• 第一棵子树的左子树和第二棵子树的右子树互为镜像，且第一棵子树的右子树和第二棵子树的左子树互为镜像；

时间复杂度

从上到下每个节点仅被遍历一遍，所以时间复杂度是$O(n)$。

C++代码

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
    	if(!root) return false;
    	return dfs(root->left,root->right);
    bool dfs(TreeNode* p1,TreeNode* p2){  //判断以p1和p2为根节点的子树是否是镜像树
  		if(!p1||!p2) return !p1&&!p2;   //终止正确的条件：只有在两棵子树为空的时候才返回true，这时候就是两棵子树全部遍历完
  		if(p1->val!=p2->val) return false;   //终止错误的条件，
        return dfs(p1->left,p2->right)&&dfs(p1->right,p2->left);
	}
};

总结

首先要想清楚这个解决方法的流程是什么，然后用计算机的语言给表达出来。这个题目在写递归函数的时候还是要注意从上一题讲的三点出发。

问题七：顺时针打印矩阵

问题描述

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

样例

输入：
[
  [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)$

我们顺时针定义四个方向：上右下左。

从左上角开始遍历，先往右走，走到不能走为止，然后更改到下个方向，再走到不能走为止，依次类推，遍历 $n^2$个格子后停止。

时间复杂度

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

C++代码

class Solution {
public:
    vector<int> printMatrix(vector<vector<int>>& matrix) {
    	vector<int> res;   //定义一个数组来接受我们的最终结果
    	int m=matrix.size();
    	int n=matrix.size();
    	if(!m) return res;
    	vector<vextor<bool>> st=vector(m,vector(n,false));
    	int x=0,y=0,d=1;
    	int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
    	for(int i=0;i<m*n;i++){
  			res.push_back(matrix[x][y]);
  			st[x][y]=true;
  			int a=x+dx[d],b=y+dy[d];
  			if(a<0||a>=m||b<0||b>=n||st[a][b]){
  				d=(d+1)%4;
  				a=x+dx[d],b=y+dy[d];
			}
			x=a,y=b;
		}
		return res;
	}
}

总结

注意顺时针的方向，然后按照顺序访问矩阵中的元素。

一般标准的《剑指offer》的题目就是按照题目给的参数进行边界条件的判断，也就是第4行和第7行。

问题八：包含min函数的栈

问题描述

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

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

问题分析

(单调栈) $O(1)$

我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。

下面介绍如何维护单调栈：

• 当我们向栈中压入一个数时，如果该数$≤$单调栈的栈顶元素，则将该数同时压入单调栈中；否则，不压入，这是由于栈具有先进后出性质，所以在该数被弹出之前，栈中一直存在一个数比该数小，所以该数一定不会被当做最小数输出。

• 当我们从栈中弹出一个数时，如果该数等于单调栈的栈顶元素，则同时将单调栈的栈顶元素弹出。

• 单调栈由于其具有单调性，所以它的栈顶元素，就是当前栈中的最小数。

时间复杂度

四种操作都只有常数次入栈出栈操作，所以时间复杂度都是$O(1)$

C++代码

class MinStack {
public:
    /** initialize your data structure here. */
    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 getMin() {
        return stackMin.top();
    }
};

总结

一般标准的《剑指offer》的题目就是按照题目给的参数进行边界条件的判断，也就是

问题九：不分行从上往下打印二叉树

问题描述

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

样例

输入如下图所示二叉树[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的顺序就是这道题目要求的顺序。

时间复杂度

BFS时每个节点仅被遍历一次，所以时间复杂度是$O(n)$。

C++代码

class Solution {
public:
    vector<int> printFromTopToBottom(TreeNode* root) {
 		vector<int> res;  //定义一个接受最终返回值的数组
 		if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()){
  			auto t=q.front();
  			res.push_back(t->val);
  			q.pop();
  			if(t->left) q.push(t->left);
  			if(t->right) q.push(t->right);
		}
      return res;
    }
}

总结

宽度优先遍历的标准化步骤一定要掌握，第6~13行。

问题十：分行从上往下打印二叉树

问题描述

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

样例

输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4

输出：[[8], [12, 2], [6], [4]]

问题分析

(BFS) $O(n)$

宽度优先遍历，一层一层来做。即：

• 将根节点插入队列中；

• 创建一个新队列，用来按顺序保存下一层的所有子节点；

• 对于当前队列中的所有节点，按顺序依次将儿子加入新队列，并将当前节点的值记录在答案中；

• 重复步骤2-3，直到队列为空为止。

时间复杂度

树中每个节点仅会进队出队一次，所以时间复杂度是$O(n)$。

C++代码

class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);   //标记第一行已经访问完
        vector<int> level;   //leval中存放的是当前非空的一行
        while(q.size()){
            auto t=q.front();
            q.pop();
            if(!t){    //说明已经遍历完了一整行
                if(level.empty()) break;   //如果为空的话，那说明已经访问完所有的元素
                res.push_back(level);
                level.clear();
                q.push(nullptr);  //表示当前已经访问到该行的最后一个节点了，并且下一层的节点也是已经压入到q中，这里就在下一层的最后也加一个空指针
                continue;
            }
            level.push_back(t->val);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        return res;
    }
};

总结

这个题目的关键就是建立一个用于存储当前层的数组，并在每一行访问后在队列中插入一个空指针nullptr用来标记当前行已经访问完。

问题十一：之字形打印二叉树

问题描述

请实现一个函数按照之字形顺序从上向下打印二叉树。

即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

样例

输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]
    8
   / \
  12  2
     / \
    6   4
输出：[[8], [2, 12], [6, 4]]

问题分析

(BFS) $O(n)$

宽度优先遍历，一层一层来做。即：

• 将根节点插入队列中；

• 创建一个新队列，用来按顺序保存下一层的所有子节点；

• 对于当前队列中的所有节点，按顺序依次将儿子插入新队列；

• 按从左到右、从右到左的顺序交替保存队列中节点的值；

• 重复步骤2-4，直到队列为空为止。

时间复杂度

树中每个节点仅会进队出队一次，所以时间复杂度是$O(n)$。

C++代码

class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);   //标记第一行已经访问完
        vector<int> level;   //leval中存放的是当前非空的一行
        bool flag=fasle;
        while(q.size()){
            auto t=q.front();
            q.pop();
            if(!t){    //说明已经遍历完了一整行
                if(level.empty()) break;   //如果为空的话，那说明已经访问完所有的元素
                if(flag) reverse(level.begin(),level.end());
                flag=!flag;
                res.push_back(level);
                level.clear();
                q.push(nullptr);  //表示当前已经访问到该行的最后一个节点了，并且下一层的节点也是已经压入到q中，这里就在下一层的最后也加一个空指针
                continue;
            }
            level.push_back(t->val);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        return res;
    }
};

总结

这一题和上一题是一样的，只是多了一个判断是否倒置的布尔型变量。