关注
第一题:双指针 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;
}
查看原帖
点赞 评论
相关推荐
世界以痛吻我我直接痛...:考研吧

点赞 评论 收藏
分享
05-21 15:47
门头沟学院 Java 浪漫主义的虹夏:项目有亮点吗,第一个不是纯玩具项目吗,项目亮点里类似ThreadLocal,Redis储存说难听点是花几十分钟绝大部分人都能学会,第二个轮子项目也没体现出设计和技术,想实习先沉淀,好高骛远的自嗨只会害了自己
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 计算机有哪些岗位值得去? #
9792次浏览 89人参与
# 电网笔面经互助 #
36037次浏览 350人参与
# 实习生的蛐蛐区 #
29525次浏览 218人参与
# 听劝,这个简历怎么改 #
177483次浏览 1150人参与
# 应届生,你找到工作了吗 #
15799次浏览 129人参与
# 你找工作的时候用AI吗? #
11675次浏览 118人参与
# 说说你知道的学历厂 #
20829次浏览 123人参与
# 总结:哪家公司面试体验感最好 #
51572次浏览 367人参与
# 学历贬值真的很严重吗? #
21751次浏览 161人参与
# 面试尴尬现场 #
16841次浏览 109人参与
# 入职第一天,你准备什么时候下班 #
62938次浏览 380人参与
# 大学生该如何认清当下的就业环境? #
88769次浏览 567人参与
# 下班后的时间你怎么安排 #
5366次浏览 61人参与
# 打工人的工作餐日常 #
48660次浏览 362人参与
# 哪些公司校招卡第一学历 #
61906次浏览 234人参与
# 哪一瞬间觉得自己长大了 #
5476次浏览 89人参与
# 社会教会你的第一课 #
22680次浏览 283人参与
# 你认为小厂实习有用吗? #
8264次浏览 80人参与
# 你觉得第一学历对求职有影响吗? #
92990次浏览 668人参与
# 研究所笔面经互助 #
75455次浏览 470人参与