Leetcode summary of 20190901-20190908

Posted by chunyang on September 8, 2019

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,结果是 false
    • left is nullptr, right is nullptr,不能有其他节点
    • left is nullptr, right is not nullptr,不能有其他节点

去搜索了下答案,感觉思路非常棒。

  • 使用 queue 一直做层序遍历,如果出现 nullptr 直接 break
  • 继续遍历 queue,如果出现非 nullptr 节点,return false

其实思路就是:只要不是最后一层,就一直不会出现 nullptr,如果出现了 nullptr,那么它后面应该就 都是 nullptr

后续的博客都会采用英文去编写,锻炼自己的英文能力。

本文完