第94场周赛
872. 叶子相似的树
题解：根据描述，只需要深度遍历两颗树，把叶子节点都存到两个向量中，判定两个向量是不是一模一样。
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int>ret1;
vector<int> ret2;
dfs(root1,ret1);
dfs(root2,ret2);
if(ret1.size()!=ret2.size()) return false;
for(int i=0;i<ret1.size();i++){
if(ret1[i]!=ret2[i])return false;
}
return true;
}
void dfs(TreeNode* root,vector<int>& ret){
if(!root) return;
if(!root->left&&!root->right) ret.push_back(root->val);
dfs(root->left,ret);
dfs(root->right,ret);
}874. 模拟行走机器人
题解：根据描述，只要用代码模拟这个过程即可，比较难受的是方向变换，方向变换也是有规律的。dirs = [0,1],[1,0],[0,-1],[-1,0]，向左转，方向的索引减；向右转，方向的索引加。障碍物判定，还是需要转换为集合，方便查找。
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
vector<vector<int>>dirs = {{0,1},{1,0},{0,-1},{-1,0}};//向北，向东，向南，向西
set<pair<int,int>>obs;//将obstacles转成set
for(auto i:obstacles){
obs.insert(make_pair(i[0],i[1]));
}
int dir = 0;
int ret = 0;
pair<int,int>start = make_pair(0,0);
for(auto command:commands){
if(command==-2){
dir = (dir+3)%4;//dir在dirs的新index,向左转
}
else if(command==-1){
dir = (dir+1)%4;//向右转
}
else{
for(int i=0;i<command;i++){
start.first+=dirs[dir][0];
start.second+=dirs[dir][1];
if(obs.find(start)!=obs.end()){
start.first-=dirs[dir][0];
start.second-=dirs[dir][1];
break;
}
ret = max(ret,start.first*start.first+start.second*start.second);
}
}
}
return ret;
}875. 爱吃香蕉的珂珂
题解：根据描述，本题就是一个二分查找的修改，二分查找的要求变成了题目要求条件。
从1开始枚举，枚举满足条件的K。如果满足，继续枚举，如果不满足，那么就在这附近了。
int minEatingSpeed(vector<int>& piles, int H) {
int lo = 1, hi = *(max_element(piles.begin(),piles.end()));
while (lo < hi) {
int mi = lo + (hi - lo);
if (!possible(piles, H, mi))//二分查找在这里是target==vec[mi]
lo = mi + 1;
else
hi = mi;
}
return lo;
}
bool possible(vector<int>& piles, int H, int K) {
int time = 0;
for (auto p: piles)
time += (p - 1) / K + 1;
return time <= H;
}873. 最长的斐波那契子序列的长度
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录