208.实现 Trie (前缀树) 字典树 树的节点存储两个数据: Count作为结束节点的次数(用来标识单词结束以及统计单词出现次数) Edges存储从该节点还可以延伸下去的边(指针指向下一个节点),可以是数组也可以是map,map适用性更强。 2021-09-20 算法 > leetcode
210.课程表2 leetcode 建立前序后序邻接表,找到入度为零的节点,然后维护邻接表。 最后路径长度等于课程总数则表示可以学完所有课程。 时间复杂度:O(n + m)空间复杂度:O(n + m) 2021-09-20 算法 > leetcode
22.括号生成 leetcode 先选定一对括号,生成的序列可以写为(left)right,其中 left 和 right 分别为 i 对括号和 n-i-1 对括号的序列。 再利用递归计算 left 和 right 。 时间复杂度:O(4n/√n)空间复杂度:O(4n/√n) 2021-09-20 算法 > leetcode
279.完全平方数 动态规划 dp[i] 表示和为i的完全平方数的最少数量。则可以得到状态转移方程: dp[i] = min(dp[i-j^2]) + 1 。 时间复杂度: O(N√N)。状态转移的时间复杂度为O(√N),攻击N个状态。空间复杂度:O(N) 2021-09-20 算法 > leetcode
322.零钱兑换 动态规划 自底向上,计算1~amount每个数作为结果所需要的最小硬币数量。 时间复杂度:O(Sn),其中 SS 是金额,nn 是面额数空间复杂度:O(S) 2021-09-20 算法 > leetcode