关注
第一题:双指针 void core(string &str)
{
int len = str.size(), cur, right;
cur = right = len - 1;
for (; cur >= 0; cur--)
{
if (str[cur] == '#')
continue;
else
{
if (cur != right)
swap(str[cur], str[right]);
right--;
}
}
}
第二题:动态规划 略 第三题:最小公共祖先+dfs 代码未测试 struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if (!left && !right)
return root;
if (!right) return right;
else return left;
}
bool dfs(TreeNode *root, TreeNode *p, TreeNode *q, vector<TreeNode*> &path, vector<vector<TreeNode*>> &res)
{
if (!root) return false;
if (root == p || root == q)
{
path.push_back(root);
res.push_back(path);
path.pop_back();
return true;
}
path.push_back(root);
if (dfs(root->left, p, q, path, res)) return true;
if (dfs(root->right, p, q, path, res)) return true;
path.pop_back();
return false;
}
vector<TreeNode*> findPath(TreeNode* root, TreeNode* p, TreeNode* q)
{
TreeNode *ancestor = lowestCommonAncestor(root, p, q);
vector<TreeNode*> left_path, right_path;
vector<vector<TreeNode*>> res;
dfs(ancestor->left, p, q, left_path, res);
dfs(ancestor->right, p, q, right_path, res);
vector<TreeNode*> path;
for (int i = res[0].size() - 1; i >= 0; i--)
path.push_back(res[0][i]);
path.push_back(ancestor);
for (int i = 0; i < (int)res[1].size() - 1; i++)
path.push_back(res[1][i]);
return path;
}
查看原帖
点赞 评论
相关推荐
07-18 12:20
武汉大学 golang 点赞 评论 收藏
分享

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 第一份工作应该选高薪还是热爱? #
66669次浏览 592人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
92039次浏览 678人参与
# 秋招签约后的心态变化 #
82486次浏览 813人参与
# 听劝,这个公司值得去吗 #
486024次浏览 1700人参与
# 你觉得早上几点上班合适? #
72305次浏览 303人参与
# 学历贬值真的很严重吗? #
24415次浏览 173人参与
# 机械人与华为的爱恨情仇 #
120136次浏览 957人参与
# 一人推荐一个值得去的通信/硬件公司 #
186457次浏览 1859人参与
# 打工人的工作餐日常 #
53155次浏览 415人参与
# 哪些公司真双非友好? #
15813次浏览 82人参与
# 26届的你们有几段实习? #
43832次浏览 486人参与
# 月薪多少能在一线城市生存 #
27725次浏览 303人参与
# 双非能在秋招上岸吗? #
221695次浏览 1172人参与
# 你以为的实习VS真实的实习 #
29528次浏览 272人参与
# 今年秋招哪家公司给的薪资最良心? #
252829次浏览 1417人参与
# 你后悔自己读研吗? #
20463次浏览 240人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
117881次浏览 812人参与
# 追觅科技求职进展汇总 #
18221次浏览 120人参与
# 实习想申请秋招offer,能不能argue薪资 #
149865次浏览 932人参与
# 如何KTV领导 #
62765次浏览 472人参与