分类: 算法训练

217 篇文章

LeetCode:一和零_474
思路 多维的动态规划,属于背包类问题,只是穷举多了个背包。 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…
LeetCode:所有可能的路径_797
思路 很基本的深搜,还没有环,省了isVisited判断 go的数组还是不太熟悉,在求得一条路线时,需要加入到路线集合中,这里需要深拷贝,没留意到,导致出现了一些意料之外的问题,看了题解才发现的 go的闭包挺香的,不用使劲传参,或者使用全局变量 题目 给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0&nbs…
LeetCode:特殊等价字符串组_893
思路 第一次用Go刷题,主要熟悉下Go的语法 这题有窍门,奇数下标的字符可以交换,如何判断交换后的字符是否相等成为了关键。如果定义一个字符串为终态,另一个去调整,趋向于终态,这很麻烦。不如主动定义一个共同的终态,两个字符串都往这个终态调整。答案是排序。特殊等价字符串奇数下标的字符串排序后是相同的。同理可以判断偶数下标的字符串,奇数偶数都符合条件了,…
LeetCode:扁平化嵌套列表迭代器_341
思路 这题我使用了两种解法 遍历N叉树 首先分析题目得知,该数据结构是N叉树,需要的是所有叶子节点 迭代器惰性求值 从时间复杂度的角度来看,遍历N叉树为O(N),遍历了所有节点,但我们是不需要非叶子节点的,不过要得到叶子结点,不得不遍历非叶子结点,所以没有提升空间了。 从空间复杂度的角度来看,提前遍历出所有叶子结点放到数组里,这里就可以优化。优化方…
LeetCode:把二叉搜索树转换为累加树_538
思路 首先二叉搜索树需要中序遍历,但如果是中序遍历,计算前面节点依赖于后面节点的结果。所以将中序遍历倒过来即可。 二叉树的遍历不止3种,可以自行调整。 题目 给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.va…
LeetCode:二叉搜索树中第K小的元素_230
思路 利用二叉搜索树的特征:中序遍历后是个递增的序列,很容易就AC了。 这样的时间复杂度是O(n),如果节点已经存储了序号,就可以像查找值一样O(logN)。 叶节点也满足二叉搜索树 题目 给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。   示例 1: 输入:root = …
LeetCode:二叉树的序列化与反序列化_297
思路 使用前序遍历序列化,遍历的元素往链表末尾添加,根节点先添加,再左子节点,右子节点。所以根节点在链表头部,有了这个信息就好做了,毕竟二叉树的遍历就是找到根节点+做点啥+递归。 使用前序遍历反序列化,需要先得出根节点,在链表的头部,将其抛出。再找出左子节点,还是链表的头部,将其抛出,继续寻找左子节点的左子节点。。。 中序遍历无法反序列化,因为根节…
LeetCode:寻找重复的子树_652
思路 问题一:如果遍历比较 遍历所有节点,然后两两比较。时间复杂度O(n)。一看性能就不行。 利用set来判断是否重复。不过有重复多次的情况,但只需返回一个重复节点,所以还需要记录count,使用map即可。 问题二:如何判断两个节点结构相同 通过递归,同时遍历两个节点。因为一个节点需要和多次比较,所以同一个节点需要遍历多次,性能差。 序列化二叉树…
LeetCode:回文链表_234
思路 简单的方法是遍历一边链表,存入数组,再从首尾往中间判断是否相等。但是题目说了,进阶的解法是空间复杂度为O(1),首先排除递归反转链表,倒是可以利用迭代来反转链表。在优化下,不用反转整条链表来比较,只需反转半条即可。 一次就AC了,爽 题目 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 …
LeetCode:最长回文子串_5
思路 算是入门题了,运用双指针即可。 题目 给你一个字符串 s,找到 s 中最长的回文子串。   示例 1: 输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。 示例 2: 输入:s = "cbbd" 输出:"bb" 示例 3: 输入:s = "a" 输出:"a" 示例 4: 输入:s = "ac" 输出:"a…