> 算法训练 - Yuyy
Yuyy
Yuyy

算法训练
文章归档

LeetCode:扁平化嵌套列表迭代器_341

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

   45   2021-12-15   去看看

LeetCode:把二叉搜索树转换为累加树_538

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

   71   2021-11-01   去看看

LeetCode:二叉搜索树中第K小的元素_230

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

   72   2021-11-01   去看看

LeetCode:二叉树的序列化与反序列化_297

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

   67   2021-10-29   去看看

LeetCode:寻找重复的子树_652

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

   72   2021-10-29   去看看

LeetCode:回文链表_234

思路 简单的方法是遍历一边链表,存入数组,再从首尾往中间判断是否相等。但是题目说了,进阶的解法是空间复杂度为O(1),首先排除递归反转链表,倒是可以利用迭代来反转链表。在优化下,不用反转整条链表来比较,只需反转半条即可。 一次就AC了,爽 题目 给你一个单链…

   77   2021-10-08   去看看

LeetCode:最长回文子串_5

思路 算是入门题了,运用双指针即可。 题目 给你一个字符串 s,找到 s 中最长的回文子串。   示例 1: 输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。 示例 2: 输入:s = "cbbd" 输出:"bb" 示例 3: 输入:s = "a" 输出:"a" 示例 4: 输…

   53   2021-10-07   去看看

Leetcode:验证回文串_125

思路 判断是否为回文字符串,最开始想到的是找到中点,利用双指针往外扩。后来发现直接从头尾往中间收就行了。 有两个注意点 本题有只判断字符和数字,其他的符号不管 大小写不敏感 在leetcode评论区学到个技巧 题目 给定一个字符串,验证它是否是回文串,…

   61   2021-10-07   去看看

LeetCode:K个一组翻转链表_25

思路 反转链表II_92的进阶,主要是利用递归思想,拆解重复问题。 题目 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节…

   75   2021-09-29   去看看

LeetCode:反转链表II_92

思路 这种题就很烦,你说它难吧,它就是在反转链表_206的基础上增加了个数量限制。你说它不难吧,边界问题折磨死你。提交几次,调试半天才AC。 题目 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位…

   81   2021-09-27   去看看
加载更多
分类
归档
我的其他站点
友链
标签
近期文章