LeetCode日记2020.2.10

591 标签验证器(hard)

这道题难在快速实现给定的复杂逻辑判断，要考虑的情况很多也容易遗漏，更多的是考察编码能力。

class Solution {
public:
bool isValid(string code) {
stack<string> tagName;
int N = code.size();
string preCDATA("[CDATA["), posCDATA("]]>");
for(int i=0; i<N; ++i)
{
if(code[i] == '<')
{
++i;
if(i>=N)
return false;
if(code[i] == '/')
{
++i;
auto pos = code.find('>', i);
if(pos == string::npos)
return false;
string tag = code.substr(i, pos-i);
if(tagName.empty() || tag != tagName.top())
return false;
tagName.pop();
i = pos;
if(tagName.empty() && i < N - 1)
return false;
}
else if(code[i] == '!')
{
if(tagName.empty())
return false;
++i;
if(code.substr(i, preCDATA.size()) != preCDATA)
return false;
i += preCDATA.size();
auto pos = code.find(posCDATA, i);
if(pos == string::npos)
return false;
i = pos + posCDATA.size() - 1;
}
else
{
int length = 0;
while(code[i] != '>')
{
++length;
if(length > 9)
return false;
if(!isupper(code[i]))
return false;
++i;
}
if(length == 0)
return false;
tagName.push(code.substr(i - length, length));
}
}
else
{
if(tagName.empty())
return false;
}
}
return tagName.empty();
}
};

1302 层数最深的叶子节点的和(mid)

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int deepestLeavesSum(TreeNode* root) {
deque<pair<TreeNode*, int>> deq;
deq.emplace_back(root, 0);
int maxD = -1;
int res = 0;
while(!deq.empty())
{
auto f = deq.front();
deq.pop_front();
if(f.second == maxD)
res += f.first->val;
else if(f.second > maxD)
{
maxD = f.second;
res = f.first->val;
}
else;
if(f.first->left != NULL)
deq.emplace_back(f.first->left, f.second + 1);
if(f.first->right != NULL)
deq.emplace_back(f.first->right, f.second + 1);
}
return res;
}
};

1315 祖父节点值为偶数的节点和(mid)

迭代实现DFS，记录每个节点的父节点的奇偶性，在节点由父节点提取并入栈时判断该结点是否满足要求。

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int sumEvenGrandparent(TreeNode* root) {
vector<pair<TreeNode*, bool>> s;
if(root != NULL)
s.emplace_back(root, false);
int res = 0;
while(!s.empty())
{
while(s.back().first->left != NULL)
{
if(s.back().second)
res += s.back().first->left->val;
s.emplace_back(s.back().first->left, !(s.back().first->val & 1));
}
while(!s.empty() && s.back().first->right == NULL)
s.pop_back();
if(!s.empty())
{
auto t = s.back();
s.pop_back();
s.emplace_back(t.first->right, !(t.first->val & 1));
if(t.second)
res += t.first->right->val;
}
}
return res;
}
};

654 最大二叉树(mid)

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return consTree(nums.cbegin(), nums.cend());
}
TreeNode* consTree(vector<int>::const_iterator beg, vector<int>::const_iterator End)
{
if(beg == End)
return NULL;
auto maX = max_element(beg, End);
TreeNode* root = new TreeNode(*maX);
root->left = consTree(beg, maX);
root->right = consTree(++maX, End);
return root;
}
};

1305 两棵二叉搜索树中的所有元素(mid)

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
stack<TreeNode*> s1, s2;
vector<int> res;
if(root1 != NULL)
{
s1.push(root1);
while(s1.top()->left != NULL)
s1.push(s1.top()->left);
}
if(root2 != NULL)
{
s2.push(root2);
while(s2.top()->left != NULL)
s2.push(s2.top()->left);
}
while(!s1.empty() || !s2.empty())
{
if(!s1.empty() && !s2.empty())
res.push_back(min(s1.top()->val, s2.top()->val));
else if(s2.empty())
res.push_back(s1.top()->val);
else
res.push_back(s2.top()->val);
auto& s = !s1.empty() && !s2.empty() ? s1.top()->val < s2.top()->val? s1:s2 :
s1.empty()? s2 : s1;
auto t = s.top();
s.pop();
if(t->right != NULL)
{
s.push(t->right);
while(s.top()->left != NULL)
s.push(s.top()->left);
}
}
return res;
}
};

894 所有可能的满二叉树(mid)

递归实现，可用记忆化技术加速。同时注意到满二叉树的节点个数一定为奇数。

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode*> allPossibleFBT(int N) {
if(N == 1)
return vector<TreeNode*>(1, new TreeNode(0));
vector<vector<TreeNode*>> lTrees, rTrees;
for(int i=1;i<N-1; i+=2)
{
lTrees.push_back(allPossibleFBT(i));
rTrees.push_back( ((N-i-1)&1)? allPossibleFBT(N - i - 1) : vector<TreeNode*>());
}
vector<TreeNode*> trees;
for(int i=0;i<lTrees.size();++i)
{
if(!lTrees[i].empty() && !rTrees[i].empty())
{
for(const auto& l: lTrees[i])
{
for(const auto& r: rTrees[i])
{
TreeNode* t = new TreeNode(0);
t->left = l;
t->right = r;
trees.push_back(t);
}
}
}
}
return trees;
}
};

最后

以上就是单薄诺言为你收集整理的LeetCode日记20200210LeetCode日记2020.2.10的全部内容，希望文章能够帮你解决LeetCode日记20200210LeetCode日记2020.2.10所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。