题解:根据描述,只需要深度遍历两颗树,把叶子节点都存到两个向量中,判定两个向量是不是一模一样。
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);
}
题解:根据描述,只要用代码模拟这个过程即可,比较难受的是方向变换,方向变换也是有规律的。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;
}
题解:根据描述,本题就是一个二分查找的修改,二分查找的要求变成了题目要求条件。
从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;
}