当前位置:网站首页>【剑指Offer】6-10题
【剑指Offer】6-10题
2022-07-04 22:30:00 【你算哪一个bug?】
从尾到头打印链表
剑指 Offer 06. 从尾到头打印链表 - 力扣(LeetCode)
从尾到头,可以更改指向,但是比较麻烦,而且也改变了链表的结构。
观察打印的结构,是先打印尾再打印头的,和栈的结构很像,所以采用栈来写。
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
stack<int> st;
vector<int>ret;
ListNode* cur=head;
while(cur!=NULL)
{
st.push(cur->val);
cur=cur->next;
}
int sz=st.size();
ret.resize(sz);
for(int i=0;i<sz;i++)
{
ret[i]=st.top();
st.pop();
}
return ret;
}
};
重建二叉树
剑指 Offer 07. 重建二叉树 - 力扣(LeetCode)
构建树的思想:前序序列的第一个节点肯定是根节点,中序序列中根节点左边所有的节点都是左子树的,右边的都是右子树的,具体做法不再赘述。下面从代码实现的角度进行分析
这题的难点在于确定基准和确定递归函数的参数,区间其实都好算。
确定基准的意思是我用的元素的下标位置是以中序序列为基准还是以前序序列为基准。
下面我采用的是根节点的位置以前序序列为基准,所以递归函数参数中的pre_root就代表当前这棵树的根节点在前序序列中的位置,in_root和in_right表示的是这棵树在中序序列里的左右边界。
class Solution {
public:
//TreeNode* _bulidTree(TreeNode* root,int left,int right)//root如果不是int就不能确定根节点在前序遍历序列中的位置
TreeNode* _bulidTree(int pre_root,int in_left,int in_right)
{
if(in_left>in_right)//说明该结点对应的左右子树已经不合理
{
return NULL;
}
TreeNode* root=new TreeNode(preorder[pre_root]);//创建根节点
int x=find(inorder.begin(),inorder.end(),preorder[pre_root])-inorder.begin();//找到根节点在中序序列中的位置
int l_length=x-in_left;//左边区间的长度
int r_length=in_right-x;//右边区间的长度
root->left=_bulidTree(pre_root+1,in_left,in_left+l_length-1);//构建左子树
root->right=_bulidTree(pre_root+l_length+1,in_right-r_length+1,in_right);//构建右子树
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder=preorder;//让子函数_buildTree里可以拿到preorder
this->inorder=inorder;//同理
TreeNode* root=_bulidTree(0,0,preorder.size()-1);//我的区间两边都是闭的
return root;
}
private:
vector<int> preorder;
vector<int> inorder;
};
这个代码还有一个可优化的点,仔细观察可以发现每次递归我都要计算根节点在中序序列中的位置,而find的底层是一个一个找过去的,效率不高,所以这里我们可以用哈希的思想把根节点在中序序列中的位置映射出来。
class Solution {
public:
//TreeNode* _bulidTree(TreeNode* root,int left,int right)//root如果不是整形就不能确定根节点在前序遍历序列中的位置
TreeNode* _bulidTree(int pre_root,int in_left,int in_right)
{
if(in_left>in_right)
{
return NULL;
}
TreeNode* root=new TreeNode(preorder[pre_root]);
// int x=find(inorder.begin(),inorder.end(),preorder[pre_root])-inorder.begin();
int l_length=dic[preorder[pre_root]]-in_left;//左边区间的长度
int r_length=in_right-dic[preorder[pre_root]];//右边区间的长度
root->left=_bulidTree(pre_root+1,in_left,in_left+l_length-1);
root->right=_bulidTree(pre_root+l_length+1,in_right-r_length+1,in_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder=preorder;
for(int i=0;i<inorder.size();i++)
{
dic[inorder[i]]=i;//映射中序序列元素的下标
}
TreeNode* root=_bulidTree(0,0,preorder.size()-1);
return root;
}
private:
vector<int> preorder;
vector<int> inorder;
unordered_map<int,int>dic;//字典,表示映射关系
};
二叉树的下一个结点
这题力扣没找到链接
找出中序遍历的下一个结点
以前写红黑树的++时写过类似的,这里把当时的代码粘过来,详细的如下图(
这个图是我红黑树那篇博客里的内容)
self& operator++()//前置++
{
Node* cur = _node;
if (cur->_right)
{
//右子树不为空,不能直接把右子树的根给_node
//因为右子树最左边的叶子才是下一个应该访问的结点
Node* right = cur->_right;
while (right&&right->_left)
{
right = right->_left;
}
_node = right;
return *this;
}
else//右子树为空
//看父亲
{
Node* parent = cur->_parent;
while (parent&&parent->_right == cur)
{
cur = parent;
parent = cur->_parent;
}
if (parent == nullptr)
{
_node = nullptr;
}
else
{
_node = parent;
}
return *this;
}
}
用两个栈实现队列
剑指 Offer 09. 用两个栈实现队列 - 力扣(LeetCode)
用两个栈模拟队列的实现。
特别注意空栈情况,不处理空栈力扣编译都无法通过(VS跑的过)
class CQueue {
public:
CQueue() {}
void appendTail(int value) {
st1.push(value);
}
int deleteHead() {
if(st1.empty()&&st2.empty())//考虑两个都是空栈的情况,因为_ move并没有处理空栈
//如果两个传入的都是空栈,会导致stack为空时访问栈顶数据报错
{
return -1;
}
_move(st1,st2);
int x=st2.top();
st2.pop();
_move(st2,st1);
return x;
}
void _move(stack<int>&s1,stack<int>&s2)//把s1的数据移到s2里面
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
private:
stack<int>st1;
stack<int>st2;
};
斐波那契数列
剑指 Offer 10- I. 斐波那契数列 - 力扣(LeetCode)
根据题目给的公式递推即可。
class Solution {
public:
int fib(int n) {
if(n==0)
{
return 0;
}
else if(n==1)
{
return 1;
}
else
{
int pprev=0;//当前数字前一个的前一个
int prev=1;//当前数字的前一个
for(int i=2;i<=n;i++)
{
int tmp=(prev+pprev)%1000000007;
pprev=prev%1000000007;
prev=tmp;
}
return prev;//最后一次计算的结果由tmp给了prev
}
}
};
书上还给了一种logn的解法,但是写起来比较复杂,不够实用。
【扩展】青蛙跳台阶
剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣(LeetCode)
斐波那契的变形,也可以用dp去做。
记青蛙跳上第n级阶梯的方案数为dp[n];则dp[n]=dp[n-1]+dp[n-2];比如青蛙在第N级阶梯,那它只能是从第N-1或者第N-2级上来的
class Solution {
public:
int numWays(int n) {
int a[]={
1,1};
if(n<2)
{
return a[n];
}
int ans=0;
int pprev=1;
int prev=1;
for(int i=2;i<=n;i++)
{
ans=(pprev+prev)%1000000007;
pprev=prev%1000000007;
prev=ans;
}
return ans;
}
};
【扩展】矩形覆盖
这题没找到链接…但也是斐波那契的变形。
边栏推荐
- Lost in the lock world of MySQL
- Breakpoint debugging under vs2019 c release
- Erik baleog and Olaf, advanced area of misc in the attack and defense world
- 页面关闭前,如何发送一个可靠请求
- SPSS安装激活教程(包含网盘链接)
- Google Earth engine (GEE) -- take modis/006/mcd19a2 as an example to batch download the daily mean, maximum, minimum, standard deviation, statistical analysis of variance and CSV download of daily AOD
- Locust performance test - environment construction and use
- Redis入门完整教程:GEO
- High school physics: linear motion
- Redis入门完整教程:HyperLogLog
猜你喜欢
NFT insider 64: e-commerce giant eBay submitted an NFT related trademark application, and KPMG will invest $30million in Web3 and metauniverse
Install the gold warehouse database of NPC
Why is Dameng data called the "first share" of domestic databases?
集群的概述与定义,一看就会
The overview and definition of clusters can be seen at a glance
It is said that software testing is very simple, but why are there so many dissuasions?
Attack and defense world misc advanced area ditf
常用技术指标之一文读懂BOLL布林线指标
Co create a collaborative ecosystem of software and hardware: the "Joint submission" of graphcore IPU and Baidu PaddlePaddle appeared in mlperf
Tla+ introductory tutorial (1): introduction to formal methods
随机推荐
环境加密技术解析
Attack and defense world misc master advanced zone 001 normal_ png
繁華落盡、物是人非:個人站長該何去何從
2022-07-04: what is the output of the following go language code? A:true; B:false; C: Compilation error. package main import “fmt“ func main() { fmt.Pri
模拟摇杆控制舵机
Talk about Middleware
Naacl-22 | introduce the setting of migration learning on the prompt based text generation task
PMO: compare the sample efficiency of 25 molecular optimization methods
[Lua] Int64 support
[the 2023 autumn recruitment of MIHA tour] open [the only exclusive internal push code of school recruitment eytuc]
Redis入门完整教程:列表讲解
SQL中MAX与GREATEST的区别
MD5 tool class
[machine learning] handwritten digit recognition
Unity修仙手游 | lua动态滑动功能(3种源码具体实现)
Redis的持久化机制
Unity vscode emmylua configuration error resolution
Detailed explanation of flask context
Breakpoint debugging under vs2019 c release
Redis: redis configuration file related configuration and redis persistence