当前位置:网站首页>《剑指offer》题解——week3(持续更新)
《剑指offer》题解——week3(持续更新)
2022-08-11 07:53:00 【Java技术一点通】
《剑指offer》题解——week3
一、剑指 Offer 25. 合并两个排序的链表
1. 题目描述
2. 思路分析
(线性合并) O(n)
1. 新建头部的保护结点dummy
,设置cur
指针指向dummy
。
2. 若当前 l 1 l_1 l1指针指向的结点的值val
比 l 2 l_2 l2指针指向的结点的值val
小 ,则令cur
的next
指针指向 l 1 l_1 l1,且 l 1 l_1 l1后移;否则指向 l 2 l_2 l2,且 l 2 l_2 l2后移。
3. 然后cur
指针按照上一部设置好的位置后移。
4. 循环以上步骤直到 l 1 l_1 l1或 l 2 l_2 l2为空。
5. 将剩余的 l 1 l_1 l1或 l 2 l_2 l2接到cur
指针后边。
3. 代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(-1), cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur = cur->next = l1;
l1 = l1->next;
} else {
cur = cur->next = l2;
l2 = l2->next;
}
}
if (l1) cur->next = l1;
if (l2) cur->next = l2;
return dummy->next;
}
};
二、剑指 Offer 26. 树的子结构
1. 题目描述
2. 思路分析
- 首先判断两个二叉树为空的情况,如果为空,直接
return false
; - 如果不为空,就可以调用
isSame(A, B)
函数来判断B是否为A的子树。如果不是,则递归,判断B是否是A的左子树的子树,或者,B是否是A的右子树的子树。注意是||
- 对于函数
isSame(A, B)
的细节。首先判断B子树的节点是否为空,如果为空,说明前面的都匹配,直接return true
; - 接下来,如果B树的节点不为空,但是A树的节点为空,那么一定不匹配,直接
return false
; - 如果A和B树的节点都不为空,但是值不一样,那也是不匹配,直接
return false
; - 最后如果 B树的节点不为空, A树的节点也不为空, A树和B树的当前节点是匹配的。那么我们就递归到A和B的左子树,同时,A和B的右子树,看看是否匹配,注意这里是
&&
。
注意:isSame()
中的顺序不能改:
- 先判断B的节点是否为空,是的话说明该节点的父节点已经匹配,
return true
; - 这时,再判断A的节点是否为空,走到这句说明B的节点不为空,如果A空B不空,一定不匹配,
return false
; - 第3句,说明A和B都不为空,就看对应的
val
是否相等,不等就return false
;相等的话就向下递归,看这个节点在2棵树中对应的左右子树是否匹配。
3. 代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (!A || !B) return false;
if (isSame(A, B)) return true;
return isSubStructure(A->left, B) || isSubStructure(A->right,B);
}
bool isSame(TreeNode* p1, TreeNode* p2) {
if (!p2) return true;
if (!p1 || p1->val != p2->val) return false;
return isSame(p1->left, p2->left) && isSame(p1->right, p2->right);
}
};
三、剑指 Offer 27. 二叉树的镜像
1. 题目描述
2. 思路分析
这是一道很经典的二叉树问题。显然,我们从根节点开始,递归地对树进行遍历,并从叶子节点先开始翻转得到镜像。如果当前遍历到的节点 root
的左右两棵子树都已经翻转得到镜像,那么我们只需要交换两棵子树的位置,即可得到以 root
为根节点的整棵子树的镜像。
3. 代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if (root == NULL) return NULL;
TreeNode *left = mirrorTree(root->left);
TreeNode *right = mirrorTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
四、剑指 Offer 28. 对称的二叉树
1. 题目描述
2. 思路分析
如果一个树的左子树与右子树镜像对称,那么这个树是对称的。
因此,该问题可以转化为:两个树在什么情况下互为镜像?
如果同时满足下面的条件,两个树互为镜像:
- 它们的两个根结点具有相同的值;
- 每个树的右子树都与另一个树的左子树镜像对称。
我们可以实现这样一个递归函数,通过同步移动
两个指针的方法来遍历这棵树,p
指针和 q
指针一开始都指向这棵树的根,随后 p
右移时,q
左移,p
左移时,q
右移。每次检查当前 p
和 q
节点的值是否相等,如果相等再判断左右子树是否对称。
3. 代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
};
五、剑指 Offer 29. 顺时针打印矩阵
1. 题目描述
2. 思路分析
我们顺时针定义四个方向:上右下左。
从左上角开始遍历,先往右走,走到不能走为止,然后更改到下个方向,再走到不能走为止,依次类推,遍历 n 2 n^2 n2个格子后停止。
3.代码实现
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int n = matrix.size();
if (!n) return res;
int m = matrix[0].size();
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
vector<vector<bool>> st(n, vector<bool>(m));
for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++ ) {
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;
}
};
六、剑指 Offer 30. 包含min函数的栈
1. 题目描述
2. 思路分析
我们除了维护基本的栈结构之外,还需要维护一个单调栈
,来实现返回最小值的操作。
下面介绍如何维护单调栈:
- 当我们向栈中压入一个数时,如果该数 ≤ 单调栈的栈顶元素,则将该数同时压入单调栈中;否则,不压入,这是由于栈具有先进后出性质,所以在该数被弹出之前,栈中一直存在一个数比该数小,所以该数一定不会被当做最小数输出。
- 当我们从栈中弹出一个数时,如果该数等于单调栈的栈顶元素,则同时将单调栈的栈顶元素弹出。
- 单调栈由于其具有单调性,所以它的栈顶元素,就是当前栈中的最小数。
3. 代码实现
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 min() {
return stackMin.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/
七、剑指 Offer 31. 栈的压入、弹出序列
1. 题目描述
2. 思路分析
借用一个辅助栈stack
,模拟 压入 / 弹出操作的排列。根据是否模拟成功,即可得到结果。
- 入栈操作: 按照压栈序列的顺序执行。
- 出栈操作: 每次入栈后,循环判断 “栈顶元素 == 弹出序列的当前元素” 是否成立,将符合弹出序列顺序的栈顶元素全部弹出。
算法流程:
- 初始化: 辅助栈
stack
,弹出序列的索引index
; - 遍历压栈序列: 各元素记为 num` ;
- 元素
num
入栈; - 循环出栈:若
stack
的栈顶元素 == 弹出序列元素popped[index]
,则执行出栈与index ++
;
- 元素
- 返回值: 若
stack
为空,则此弹出序列合法。
3. 代码实现
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
if (pushed.size() != popped.size()) return false;
stack<int> stack;
int index = 0;
for (int num : pushed) {
stack.push(num);
while (!stack.empty() && stack.top() == popped[index]) {
stack.pop();
index ++;
}
}
return stack.empty();
}
};
八、剑指 Offer 32 - I. 从上到下打印二叉树
1. 题目描述
2. 思路分析
题目要求的二叉树的 从上至下 打印(即按层打印),又称为二叉树的 广度优先搜索(BFS)。
BFS 通常借助 队列 的先入先出特性来实现。
算法流程:
- 特例处理: 当树的根节点为空,则直接返回空列表 [] ;
- 初始化: 打印结果列表
res
,包含根节点的队列queue[root]
; - BFS 循环: 当队列 queue 为空时跳出;
- 出队: 队首元素出队,记为
t
; - 打印: 将
t.val
添加至列表res
尾部; - 添加子节点: 若
t
的左(右)子节点不为空,则将左(右)子节点加入队列 queue ;
- 出队: 队首元素出队,记为
- 返回值: 返回打印结果列表
res
即可。
3. 代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
auto t = q.front();
q.pop();
res.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
return res;
}
};
九、剑指 Offer 32 - II. 从上到下打印二叉树 II
1. 题目描述
2. 思路分析
本题是要求将本层全部节点打印到一行,并将下一层全部节点加入队列,以此类推,即可分为多行打印。
算法流程:
- 特例处理: 当树的根节点为空,则直接返回空列表 [] ;
- 初始化: 打印结果列表
res
,包含根节点的队列queue[root]
; - BFS 循环: 当队列 queue 为空时跳出;
- 新建一个临时列表
tmp
,用于存储当前层打印结果
; - 当前层打印循环: 循环次数为当前层节点数(即队列
queue
长度);- 出队: 队首元素出队,记为
t
; - 打印: 将
t.val
添加至列表res
尾部; - 添加子节点: 若
t
的左(右)子节点不为空,则将左(右)子节点加入队列 queue ;
- 出队: 队首元素出队,记为
- 将当前层结果
tmp
添加入res
。
- 新建一个临时列表
- 返回值: 返回打印结果列表
res
即可。
3. 代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
vector<int> tmp;
int n = q.size();
for (int i = 0; i < n; i ++ ) {
auto p = q.front();
q.pop();
tmp.push_back(p->val);
if (p->left) q.push(p->left);
if (p->right) q.push(p->right);
}
res.push_back(tmp);
}
return res;
}
};
十、剑指 Offer 32 - III. 从上到下打印二叉树 III
1. 题目描述
2. 思路分析
层序遍历 + 倒序
此方法的优点是只用列表即可,无需其他数据结构。
偶数层倒序: 若 res
的长度为 奇数 ,说明当前是偶数层,则对 tmp
执行 倒序 操作。
3. 代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
int n = q.size();
vector<int> tmp;
for (int i = 0; i < n; i ++ ) {
auto t = q.front();
q.pop();
tmp.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
if (res.size() % 2 == 1) reverse(tmp.begin(), tmp.end());
res.push_back(tmp);
}
return res;
}
};
创作不易,如果有帮助到你,请给题解点个赞和收藏,让更多的人看到!!!
关注博主不迷路,内容持续更新中。
边栏推荐
- Machine Learning Summary (2)
- 1051 Multiplication of Complex Numbers (15 points)
- Four states of Activity
- 1101 B是A的多少倍 (15 分)
- excel 透视表 值显示内容 不显示计数
- Pico neo3 Unity Packaging Settings
- 【LeetCode】链表题解汇总
- My creative anniversary丨Thank you for being with you for these 365 days, not forgetting the original intention, and each is wonderful
- 欢迎加入sumarua网络安全交流社区
- 查找最新人员工资和上上次人员工资的变动情况
猜你喜欢
随机推荐
3.2 - classification - Logistic regression
1.1-Regression
TF generates (feature, label) set through feature and label, tf.data.Dataset.from_tensor_slices
1081 Check Password (15 points)
软件测试常用工具的用途及优缺点比较(详细)
【C语言】每日一题,求水仙花数,求变种水仙花数
oracle数据库中列转行,列会有变化
【415. 字符串相加】
记录一些遇见的bug——Lombok和Mapstruct的冲突导致,A component required a bean of type ‘com.XXX.controller.converter.
【Day_13 0509】▲跳石板
tf.cast(),reduce_min(),reduce_max()
2022-08-10:为了给刷题的同学一些奖励,力扣团队引入了一个弹簧游戏机, 游戏机由 N 个特殊弹簧排成一排,编号为 0 到 N-1, 初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹
1003 我要通过 (20 分)
Item 2 - Annual Income Judgment
Decrement operation in tf; tf.assign_sub()
【LeetCode】Summary of linked list problems
欧拉函数(用欧拉筛法求欧拉函数)
1002 Write the number (20 points)
测试用例很难?有手就行
优炫数据库支持多列分区吗?