当前位置:网站首页>LeetCode力扣(剑指offer 36-39)36. 二叉搜索树与双向链表37. 序列化二叉树38. 字符串的排列39. 数组中出现次数超过一半的数字
LeetCode力扣(剑指offer 36-39)36. 二叉搜索树与双向链表37. 序列化二叉树38. 字符串的排列39. 数组中出现次数超过一半的数字
2022-07-07 17:44:00 【木白CPP】
剑指 Offer 36. 二叉搜索树与双向链表
题解:
思路很简单,就是一个中序遍历,一边遍历一边把节点连接起来。
代码:
class Solution {
public:
Node *pre,*head;
void dfs(Node* root){
if(root==nullptr) return;
dfs(root->left);
if(pre==nullptr) head=root;//这是个头节点
else
pre->right=root;
root->left=pre;
pre=root;
dfs(root->right);
}
Node* treeToDoublyList(Node* root) {
if(root == nullptr) return root;
dfs(root);
head->left=pre;
pre->right=head;
return head;
}
};
结果:
剑指 Offer 37. 序列化二叉树
题解:
序列化一般采用前序,中序,后序,这里采用前序。
序列化,用前序遍历将二叉树的节点保存到一个字符串中,每个节点之间用’,‘隔开。值得注意的是,在遍历的过程中需要将二叉树看成一颗满二叉树,空节点用’null‘表示。
反序列化,将字符串放在队列que中,用’,‘判断并推入到队列中。通过前序遍历,一边前序遍历一边建立二叉树节点。
代码:
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(root==nullptr) return "null,";
string str=to_string(root->val)+',' ;
str+=serialize(root->left);
str+=serialize(root->right);
return str;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
queue<string> que;
string str;
for(auto i:data){
if(i==','){
que.push(str);
str.clear();
}
else
str.push_back(i);
}
return rdeserialize(que);
}
TreeNode* rdeserialize(queue<string> &que){
if (que.front() == "null") {
que.pop();
return nullptr;
}
TreeNode* root = new TreeNode(stoi(que.front()));
que.pop();
root->left = rdeserialize(que);
root->right = rdeserialize(que);
return root;
}
};
结果:
剑指 Offer 38. 字符串的排列
题解:
最关键是去重复,因为有重复的字符。可以用一个标志位,判断当前的字符是否出现在前面的字符串中。
代码:
class Solution {
public:
vector<string> res;
void dfs(string &s,int sz,int pos){
if(pos==sz) res.push_back(s);
for(int i=pos;i<sz;++i){
bool flag=true;
for(int j=pos;j<i;++j){
if(s[j]==s[i]) flag=false;
}
if(flag){
swap(s[i],s[pos]);
dfs(s,sz,pos+1);
swap(s[i],s[pos]);
}
}
}
vector<string> permutation(string s) {
dfs(s,s.size(),0);
return res;
}
};
结果:
剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
题解:
方法一:排序
如果重复字符有超过一半的,排序后必然会在数组中间位置。
代码:
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(),nums.end());
return nums[nums.size()/2];
}
};
结果:
方法二:哈希
用哈希存储,一旦这个值大于数组长度的一半就返回该值。
代码:
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int>map;
for(auto i:nums){
++map[i];
if(map[i]>nums.size()/2) return i;
}
return -1;
}
};
结果:
边栏推荐
- 吞吐量Throughout
- RESTAPI 版本控制策略【eolink 翻译】
- Automatic classification of defective photovoltaic module cells in electroluminescence images-论文阅读笔记
- 【RT-Thread env 工具安装】
- PMP practice once a day | don't get lost in the exam -7.7
- 2022年投资哪个理财产品收益高?
- The project manager's "eight interview questions" is equal to a meeting
- 841. 字符串哈希
- 炒股如何开户?请问一下手机开户股票开户安全吗?
- L1-028 judging prime number (Lua)
猜你喜欢
Numpy——2. Shape of array
Redis——基本使用(key、String、List、Set 、Zset 、Hash、Geo、Bitmap、Hyperloglog、事务 )
Dynamic addition of El upload upload component; El upload dynamically uploads files; El upload distinguishes which component uploads the file.
Kirin Xin'an joins Ningxia commercial cipher Association
杰理之关于 TWS 配对方式配置【篇】
Redis master-slave and sentinel master-slave switchover are built step by step
How to share the same storage among multiple kubernetes clusters
Le PGR est - il utile au travail? Comment choisir une plate - forme fiable pour économiser le cœur et la main - d'œuvre lors de la préparation de l'examen!!!
Make this crmeb single merchant wechat mall system popular, so easy to use!
Nunjuks template engine
随机推荐
L1-025 positive integer a+b (Lua)
Dynamic addition of El upload upload component; El upload dynamically uploads files; El upload distinguishes which component uploads the file.
剑指 Offer II 013. 二维子矩阵的和
AI writes a poem
最多可以参加的会议数目[贪心 + 优先队列]
Navicat连接2002 - Can‘t connect to local MySQL server through socket ‘/var/lib/mysql/mysql.sock‘解决
超分辨率技术在实时音视频领域的研究与实践
8 CAS
PMP每日一练 | 考试不迷路-7.7
PV static creation and dynamic creation
论文解读(ValidUtil)《Rethinking the Setting of Semi-supervised Learning on Graphs》
how to prove compiler‘s correctness
What does "true" mean
杰理之关于 TWS 配对方式配置【篇】
Redis master-slave and sentinel master-slave switchover are built step by step
杰理之按键发起配对【篇】
R语言dplyr包select函数、group_by函数、filter函数和do函数获取dataframe中指定因子变量中指定水平中特定数值数据列的值第三大的值
J ü rgen schmidhub reviews the 25th anniversary of LSTM papers: long short term memory All computable metaverses. Hierarchical reinforcement learning (RL). Meta-RL. Abstractions in generative adversar
R language ggplot2 visualization: use the ggdensity function of ggpubr package to visualize the packet density graph, and use stat_ overlay_ normal_ The density function superimposes the positive dist
让这个 CRMEB 单商户微信商城系统火起来,太好用了!