思路 在推送给用户的推特，是该用户关注的人发的推特，并通过时间顺序合并在一起。采用多路归并的方式合并，在归并时，通过最小堆优化。 题目 设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。 实现 Twitter 类： Twitter() 初始化简易版推特对象 voi…

思路 这类题有套路，需要用到单调栈。 上图中绿色item想找到下一个比它大的值，只需要和红色item比较就行，而不需要和紫色的item比较。所以我们需要维护一个单调递增的栈，保存红色的值。 通过依次比较，得出，5对应的答案是6。 下一个数字4，来寻求下一个比它大的值。 同样的，2比5小，在这个数据结构中没有意义，他应该在5存入数据结构时抛出。也就是…

思路 多维的动态规划，属于背包类问题，只是穷举多了个背包。 strs里的每个元素就是物品，m为装1的背包数量，n为装0的背包数量，开始DP套路： 定义状态：dp[i][m][n]表示0-i个物品，m个装1的背包，n个装0的背包可以装下多少个物品 状态转移方程：dp[i][m][n]=max(dp[i-1][m][n],dp[i-1][m-i1][n…

思路 很基本的深搜，还没有环，省了isVisited判断 go的数组还是不太熟悉，在求得一条路线时，需要加入到路线集合中，这里需要深拷贝，没留意到，导致出现了一些意料之外的问题，看了题解才发现的 go的闭包挺香的，不用使劲传参，或者使用全局变量 题目 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0&nbs…

思路 第一次用Go刷题，主要熟悉下Go的语法 这题有窍门，奇数下标的字符可以交换，如何判断交换后的字符是否相等成为了关键。如果定义一个字符串为终态，另一个去调整，趋向于终态，这很麻烦。不如主动定义一个共同的终态，两个字符串都往这个终态调整。答案是排序。特殊等价字符串奇数下标的字符串排序后是相同的。同理可以判断偶数下标的字符串，奇数偶数都符合条件了，…

思路 这题我使用了两种解法 遍历N叉树 首先分析题目得知，该数据结构是N叉树，需要的是所有叶子节点 迭代器惰性求值 从时间复杂度的角度来看，遍历N叉树为O(N)，遍历了所有节点，但我们是不需要非叶子节点的，不过要得到叶子结点，不得不遍历非叶子结点，所以没有提升空间了。 从空间复杂度的角度来看，提前遍历出所有叶子结点放到数组里，这里就可以优化。优化方…

思路 首先二叉搜索树需要中序遍历，但如果是中序遍历，计算前面节点依赖于后面节点的结果。所以将中序遍历倒过来即可。 二叉树的遍历不止3种，可以自行调整。 题目 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.va…

思路 利用二叉搜索树的特征：中序遍历后是个递增的序列，很容易就AC了。 这样的时间复杂度是O(n)，如果节点已经存储了序号，就可以像查找值一样O(logN)。 叶节点也满足二叉搜索树 题目 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。   示例 1： 输入：root = …

思路 使用前序遍历序列化，遍历的元素往链表末尾添加，根节点先添加，再左子节点，右子节点。所以根节点在链表头部，有了这个信息就好做了，毕竟二叉树的遍历就是找到根节点+做点啥+递归。 使用前序遍历反序列化，需要先得出根节点，在链表的头部，将其抛出。再找出左子节点，还是链表的头部，将其抛出，继续寻找左子节点的左子节点。。。 中序遍历无法反序列化，因为根节…

思路 问题一：如果遍历比较 遍历所有节点，然后两两比较。时间复杂度O(n)。一看性能就不行。 利用set来判断是否重复。不过有重复多次的情况，但只需返回一个重复节点，所以还需要记录count，使用map即可。 问题二：如何判断两个节点结构相同 通过递归，同时遍历两个节点。因为一个节点需要和多次比较，所以同一个节点需要遍历多次，性能差。 序列化二叉树…