Summary
本周解决的问题：
- Most Frequent Subtree Sum
- Max Consecutive Ones III
- Check Completeness of a Binary Tree
- Single Number II
- Map Sum Pairs
- Binary Tree Right Side View
- Flip Columns For Maximum Number of Equal Rows
- Palindromic Substrings
- Minimum Cost For Tickets
- Car Pooling
- Next Greater Element II
- Kth Smallest Element in a BST
- Stone Game II
- Implement Magic Dictionary
- Largest Values From Labels
- Regions Cut By Slashes
- Battleships in a Board
- Convert to Base -2: 参考 wikipedia 中的
negative base
其中斜体表示不是自己独立去解决，主要是动态规划问题。
Highlight
Max Consecutive Ones III
这题的解决方法真的很奇妙，维护一个窗口，窗口的大小是里面 0 的个数。一旦超出限制，我们计算当前能 得到的最大 1 的个数。之前使用的递归方式去解决，复杂度基本不能接受。尝试去用了缓存，好像也不 work。
Flip Columns For Maximum Number of Equal Rows
这道题并没有什么特殊的地方。但是它的思路值得借鉴。直接去计算答案，可能不止从哪下手。但是反过来 思考，假设某一行在最后的结果中，我们就可以推测它能达到的最大 1 或者 0 个数。
Map Sum Paris
就是 prefix tree。以前对 prefix tree 以及自己构造 dfs 的方式还是比较难受的。现在基本上没啥
问题。
Check Completeness of a Binary Tree
这道题是自己最终写出来，但是自己的思路太过复杂。就是对二叉树进行层序遍历，然后校验：
- 非最深层，其节点个数
- 最深层出现
nullptr节点时(此时位于倒数第二层):left is nullptr,right is not nullptr，结果是falseleft is nullptr,right is nullptr，不能有其他节点left is nullptr,right is not nullptr，不能有其他节点
去搜索了下答案，感觉思路非常棒。
- 使用
queue一直做层序遍历，如果出现nullptr直接break - 继续遍历
queue，如果出现非nullptr节点，return false
其实思路就是：只要不是最后一层，就一直不会出现 nullptr，如果出现了 nullptr，那么它后面应该就
都是 nullptr。
后续的博客都会采用英文去编写，锻炼自己的英文能力。
本文完