关注
第一题:双指针 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;
}
查看原帖
点赞 评论
相关推荐
06-12 19:52
吉首大学张家界学院 Python 点赞 评论 收藏
分享
05-30 00:12
江西服装学院 Java 头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 实习生的蛐蛐区 #
30845次浏览 224人参与
# 面试官是我前女友 #
106174次浏览 722人参与
# 计算机有哪些岗位值得去? #
10441次浏览 95人参与
# 说说你知道的学历厂 #
21983次浏览 134人参与
# 应届生,你找到工作了吗 #
16275次浏览 135人参与
# 你找工作的时候用AI吗? #
12419次浏览 135人参与
# 面试尴尬现场 #
18154次浏览 113人参与
# 电网笔面经互助 #
36079次浏览 351人参与
# 社会教会你的第一课 #
23972次浏览 300人参与
# 下班后的时间你怎么安排 #
5854次浏览 65人参与
# 哪一瞬间觉得自己长大了 #
5878次浏览 112人参与
# 你认为小厂实习有用吗? #
8693次浏览 92人参与
# 学历贬值真的很严重吗? #
21811次浏览 161人参与
# 职场中对你有帮助的书 #
17445次浏览 203人参与
# 简历当中有水分算不算造假? #
20653次浏览 245人参与
# 双非应该如何逆袭? #
188150次浏览 3408人参与
# 神州信息工作体验 #
15711次浏览 67人参与
# 哪些公司校招卡第一学历 #
61962次浏览 234人参与
# 现在前端的就业环境真的很差吗 #
294802次浏览 3571人参与
# 毕业旅行去哪玩儿 #
12336次浏览 133人参与