【每日刷题】Day129
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
2. LCR 154. 复杂链表的复制 - 力扣（LeetCode）
3. 单词识别_牛客题霸_牛客网 (nowcoder.com)
1. 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
//思路：前序遍历
//本题的核心还是前序遍历创建，但是在创建时，还是根据中序遍历的结果来创建
class Solution {
public:
//sub用来遍历 preorder(前序)，left、right 构成区间TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& sub,int left,int right)
{
if(left>right) return nullptr;//没有区间，返回nullptr
TreeNode* root = new TreeNode(preorder[sub]);//根据前序构造根
int flag = left;//去中序中寻找当前根
while(inorder[flag]!=preorder[sub]) flag++;
sub++;
root->left = _buildTree(preorder,inorder,sub,left,flag-1);//当前根链接左右构造好的子树
root->right = _buildTree(preorder,inorder,sub,flag+1,right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
int i = 0;
return _buildTree(preorder,inorder,i,0,preorder.size()-1);
}
};
2. LCR 154. 复杂链表的复制 - 力扣（LeetCode）
//思路：map 的使用
//本题在没有map之前我们采用的是在原链表相邻两节点中间插入新结点，然后修改原链表节点和新结点的指向，还是比较麻烦的。
//有了 map 后，这题就非常简单了
class Solution {
public:
Node* copyRandomList(Node* head)
{
if(!head) return nullptr;
Node* move = head;
Node* tmp = head;
map<Node*,Node*> ma;
while(move)
{
Node* newnode = new Node(move->val);
ma.insert({move,newnode});
move = move->next;
}
while(tmp->next)
{
auto it1 = ma.insert({tmp,nullptr});
auto it2 = ma.insert({tmp->next,nullptr});//根据key找到新节点的next
auto flag = ma.insert({tmp->random,nullptr});//根据key找到新节点的random
it1.first->second->next = it2.first->second;
if(flag.first->first) it1.first->second->random = flag.first->second;//链接新节点
else it1.first->second->random = nullptr;
tmp = tmp->next;
}
//处理最后一个节点
auto it = ma.insert({tmp,nullptr});
auto ran = ma.insert({tmp->random,nullptr});
it.first->second->next = nullptr;
if(ran.first->first) it.first->second->random = ran.first->second;
else it.first->second->random = nullptr;
return ma[head];
}
};
3. 单词识别_牛客题霸_牛客网 (nowcoder.com)
//思路：map的运用。
//与 Day127 中的 "前K个高频单词" 基本类似，这里我们首先将每个单词以及每个单词的出现次数放入map中。注意：这里放入时要先将单词全部转换为小写，这里可以用C++标准库中的transform函数辅助实现。
//全部放入map中后，我们再将map存入vector中，存储的类型为pari<string,int>，pari可以理解为一个节点，存储着string和int。
//随后对vector进行排序，根据单词的出现次数降序排序；对于出现次数相同的单词，根据string小写的字典序排序。因为sort排序默认为升序，因此我们需要自行实现仿函数。
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Pair
{
bool operator()(pair<string,int>& kv1,pair<string,int>& kv2)//
{
//因为我们将string存入map时就已经转换为小写，因此这里直接比较string即可。
return kv1.second>kv2.second||(kv1.second==kv2.second&&kv1.first<kv2.first);
}
};
int main()
{
string str;
getline(cin,str);
auto left = str.begin();
auto right = str.begin();
map<string,int> ma;
while(right!=str.end())
{
if(*right==' ')
{
string tmp(left,right);
transform(tmp.begin(),tmp.end(),tmp.begin(),[](unsigned char c){return tolower(c);});//将字符串转换为小写
left = right+1;
ma[tmp]++;//放入map中并记录出现次数
}
right++;
}
//跳出循环后最后一个单词还未放入，但是因为最后一个单词后跟着一个句号，因此右边开区间为right-1，忽略句号。
ma[string(left,right-1)]++;
vector<pair<string,int>> v(ma.begin(),ma.end());
sort(v.begin(),v.end(),Pair());
for(auto it:v) cout<<it.first<<":"<<it.second<<endl;//最后遍历输出即可
return 0;
}
