- 博客(33)
- 收藏
- 关注
RSS订阅原创 从递归入手一维动态规划
因为F(i-4)之前计算过，我们直接从缓存表查F(i-4)的结果，返回给F(i-3)即可。i = 4，是右括号，dp[i-1] = dp[3] = 0，p位置 是 i位置往前跳0个，再跳1个，即 p = 3。那么dp[i] = dp[2] = dp[i-1] + 2 + dp[p-1] = 0 + 2 + 0 = 2。
2025-04-10 19:31:43
1143
原创 最小生成树（Java实现）
最初每个顶点的并查集只有自己。用并查集来判断是否存在环。边按权值大小排序。a这条边的两个端点分别是1和2。之前它们并不在一个并查集，证明没有环。所以我们选a这条边，并将{1} 和 {2} 合并为 {1，2}。接着看b这条边，两端的端点是2和5。2所在的集合与5所在的集合不是一个集合。选b这条边，{1，2} 和 {5} 合并为{1，2，5}。c这条边，两端的端点是1和5。1和5在一个集合，如果选c的话，会有环。所以不能选。接着看d。c这条边，两端的端点是5和4。
2025-04-07 15:14:27
725
原创 力扣46. 全排列（Java实现）
i 访问元素1的时候，1 已经被使用过，接着i++。2也被用过了，接着i++。i 访问元素1的时候，1 已经被使用过，接着i++。i 访问元素1的时候，1 已经被使用过，接着i++。i 访问元素1的时候，1 没有被使用过，将其加入路径。i 和 j 上的元素交换，1 在索引0位置上。现在 2 在索引0位置上，让其他位置上的元素全排列。现在3在索引0位置上，让其他位置上的元素全排列。接下来我们想要元素2在索引0位置上，只需i 和 j 上的元素交换。接下来想让元素3在索引0位置上，只需i 和 j 上的元素交换。
2025-03-24 18:59:41
294
原创 力扣90. 子集 II（Java实现)
以上面的数组为例，[1 4 4] 与 [4 1 4] 是不同的排列，但它们是同一种组合。这道题我们需要去掉这种情况，也就是去重。而我们按照组来分析，第一个组选0个、1个、2个、3个、4个，再下个组选0个、1个、2个、3个，后面的组以此类推都一样。最好的做法就是将数组排序，因为组合不要求顺序，只需要每种元素的个数不一样。相比每个数字要和不要的这种做法，因为有一大堆相同数字，剪枝会很难。只要每种元素的个数不同，就是不同的组合。可以认为从索引4出发往后的过程是递归。假设有一个数组，排完序是上面这样的。
2025-03-24 15:13:37
390
原创 力扣669. 修剪二叉搜索树（Java实现）
f(5) 递归调用 f(7) ，7 > 6，所以节点7及其右树都不返回。f(7) 调用 f(6) ，6 ∈ [4,6]。所以f(6) 返回 f(7) 节点6，f(7) 返回 f(5) 节点6。f(5) 递归调用 f （3），3 < 4，所以节点3及其左子树都不返回。f （3）调用 f (4) ，4 ∈ [4,6]。f （3）节点4， f （3）返回 f(5) 节点4。上图的二叉搜索树中，我们要求保留 [4,6] 范围上的节点。f(5) 左右都调用完毕，返回节点5。f(5) 左边调用完毕，再去调右边。
2025-03-20 19:32:12
321
原创 力扣110. 平衡二叉树（Java实现）
我们直接递归求左右子树的高度，一旦它们的高度差大于1，就返回false。是指该树所有节点的左右子树的高度相差不超过 1。
2025-03-20 16:24:50
137
原创 力扣113. 路径总和 II（Java实现）
遍历到d时，d的上层节点的路径和是2，加上d这一层的路径，一共是3。注意：在遍历到叶子节点时，我们判断一下 上一层路径和 + 叶子节点路径 是否等于 目标路径和。f 为叶子节点，其上层节点路径和 + f节点路径 = 2 + 1 = 3。b 去遍历右子树e，e的上层节点的路径和 = 2，加上e这一层路径，一共是4。函数的第一个参数是当前遍历的节点，第二个参数是当前节点的上一层节点的路径总和。**f(b)**的左右子树都调用完了，把b从全局路径中去掉，返回到。a的左子树调用完了，a再调用右子树。
2025-03-20 16:04:19
357
原创 力扣236. 二叉树的最近公共祖先（Java实现）
当左右子树一个返回null，一个返回不为null，说明搜到为p或是q的节点，直接给上层节点（1）返回那个不为null的结果，也就是p。1的左子树返回p，右子树返回null，返回不为null的结果，p。4的左子树遍历完毕返回给4 null，4再遍历右子树依然返回null。1的左子树遍历完毕返回2，1再遍历右子树返回null，那么1的返回结果就是不为null的值，也就是2。4的左子树遍历完毕返回给4 q，再遍历其右子树返回null。2的左子树遍历完毕返回q，再遍历2的右子树，遇到p直接返回p。
2025-03-20 13:52:24
241
原创 力扣222. 完全二叉树的节点个数（Java实现）
计算公式：**树的总高度h - c的层数 - 1 ** = 4 - 3 -1 = 0，即c的右子树节点数 = 2。= 4，说明c的右子树是满二叉树。b的右子树的最左节点层数 = 4，说明 b 的左子树是满二叉树。a的右子树的最左节点层数= 3 < 4，说明右子树是满二叉树。左子树节点数 + b节点数 = 3 + 1 = 4 = 2。右子树节点数 + a节点数 = 3 + 1 = 4 = 2。= 4 - 1 - 1 = 2 ，即右子树的节点数 = 2。= 4 - 2 = 2，即b的左子树节点数 = 2。
2025-03-19 22:56:47
556
原创 力扣105. 从前序与中序遍历序列构造二叉树（Java实现）
根据上面的分析，我们知道中序数组索引 [0,1] 范围上，是a的左树。是根据先序数组索引[0,4] 范围上 以及中序数组索引[0,4] 范围上 的元素建树，并将头节点返回。那h的左子树在pre数组中的索引范围为 [l1 + 1, l1 + k - l2]。h的左子树在in数组中索引范围为[l2, k-1]，总共 k - l2 个数。h的右子树在pre数组中的索引范围为[l1 + k - l2 + 1, r1]先序数组的第一个元素a就是树的根节点，而a位于中序数组索引2的位置上。的返回结果作为a的右孩子。
2025-03-19 18:26:42
183
原创 力扣297. 二叉树的序列化与反序列化（Java实现）
b的后面是#，说明b的左孩子为null，b再去看是否有右孩子，字符依然为#，说明b也没有右孩子。我们通过先序遍历的方式将其序列化成字符串，遇到null就用 “#,” 代替。字符串的第一个字符为a，a为树的根节点。a的后面是b，说明a的左孩子是b。那么上图的树序列化成字符串为 “a,b,#,#,c,d,#,#,#,”b递归调用结束后，a的左子树就遍历完毕，a再看自己是否有右孩子。c的左子树遍历完毕，再看自己是否有右孩子。当前字符遍历到c，说明a有右孩子c。c的后面是d，说明c有左孩子d。
2025-03-19 17:36:15
334
原创 力扣297. 二叉树的序列化与反序列化（Java实现）
b的后面是#，说明b的左孩子为null，b再去看是否有右孩子，字符依然为#，说明b也没有右孩子。字符串的第一个字符为a，a为树的根节点。a的后面是b，说明a的左孩子是b。那么上图的树序列化成字符串为 “a,b,#,#,c,d,#,#,#,”b递归调用结束后，a的左子树就遍历完毕，a再看自己是否有右孩子。c的左子树遍历完毕，再看自己是否有右孩子。当前字符遍历到c，说明a有右孩子c。c继续递归调用，看自己是否有左孩子。d继续递归调用，看自己是否有左孩子。c的后面是d，说明c有左孩子d。c递归结束，返回给a。
2025-03-19 13:10:33
316
原创 力扣104 & 111 二叉树的最大深度和最小深度（Java实现）
不过这里有一点需要注意，上图中的 a 如果调左孩子，左孩子为null，返回0，加上a节点这一层的高度，总共为1。我们可能误认为最小深度是1，但最小深度必须是根节点到叶子节点的最小长度。求二叉树的最大深度就是求树高。这里直接递归调用就行。代码只有一行，右边的是函数递归调用的图。所以我们设置深度的初始值为无穷大，然后在递归过程中调用Math.min求最小深度。思路与求最大深度类似，分别递归调用左右子节点，求左子树和右子树的长度，看谁小。二叉树的最小深度是指根节点到叶子节点的最小长度。
2025-03-18 21:33:22
272
原创 力扣662. 二叉树最大宽度（Java实现）
第2层，从第一个不为null的节点，到这一层最后一个不为null节点，之间的长度（算上中间为null的节点）。（设a节点编号为0也可以，那么这种情况下左右孩子的编号分别为 2 * i + 1， 2 * i + 2）若一个节点的编号为i，它左右孩子的编号分别是 2 * i，2 * i + 1。我们设a节点的编号为1。那么它左右孩子的编号分别为 2，3。第0层宽度为1，第1层宽度为2，这个可以看出。第三层的宽度 = 15 - 9 + 1 = 7。第二层的宽度 = 7 - 4 + 1 = 4。
2025-03-18 20:37:08
279
原创 力扣103. 二叉树的锯齿形层序遍历（Java实现）
循环体的操作是从队首弹出size个元素，即queue[l]。如果弹出元素的左右孩子不为空，将其加入队列中。并且将弹出元素加入到返回结果的链表中。因为 a 属于第0层，只需正着遍历，即遍历 l ~ r-1 范围。这时候我们将第1层的节点加入链表时，应该是从 r-1 ~ l 遍历加入。之后从队首弹出size个元素，将b和c弹出，将它们的的左右孩子加入。将第二层的节点加入链表，从 l ~ r-1遍历加入。（d、e、f没有孩子）此时queue的size = l - r = 1。将 a的左右孩子 b、c加入队列中。
2025-03-18 19:45:40
393
原创 力扣102. 二叉树的层序遍历（Java实现）
所以我们下一步将a弹出，弹出的时候我们查哈希表直到a的层高是0。再看链表中是否有第0层，没有的话，创建层高为0的链表，把a加入。再查哈希表得到b的层高，看链表中是否有层高为1的链表。没有的话，自己创造，再把b加入到这个层高为1的链表中。先将 a 加入队列中，加入时我们需要把节点以及层高记录到哈希表中。弹出c，查到层高，链表中有层高为1的链表，加入该链表。b，c加入队列时，也要在哈希表中记录其层高。之后弹出b，将b的左右孩子加入队列。d，e加入队列，在哈希表中记录层高。之后b，c 加入队列中。
2025-03-18 17:23:19
428
原创 基数排序（Java实现）
先根据个位将数字分别放进桶中，之后从1号桶开始倒数据再根据十位将数字分别放进桶中，之后从1号桶开始倒数据注意，2号桶里有两个数据，先进来的先倒出去，所以23比24先倒出去。至此，数组有序。
2025-03-18 14:25:02
400
原创 堆结构和堆排序（Java实现）
从顶到低建堆时间复杂度O(n * logn)，从底到顶建堆时间复杂度O(n)。但建好堆之后的调整阶段时间复杂度都是O(n * logn)，额外空间复杂度为O(1)
2025-03-17 19:46:33
678
原创 二叉树的非递归遍历(Java实现)
首先先将头节点入栈。之后不断判断栈中是否为空，不为空就将栈顶元素弹出，打印节点的值。然后将弹出节点的右节点先入栈，左节点后入栈。（注意不为空时才入栈）
2025-03-17 12:22:56
947
原创 力扣641.设计循环双端队列（Java实现）
头部添加元素时，若 l == 0，则 l = limit - 1，deque[l] = value，size++若 l!= 0，则 l = l - 1，deque[l] = value，size++头部删除元素时，通常来说，我们需要将 deque[l] 返回，但本题没有这样要求，我们在此就不考虑了。若 l = limit - 1，则 l = 0，size–若 l!= limit - 1，则 l = l + 1，size–尾部添加元素时，
2024-11-08 19:49:46
1763
原创 力扣155.最小栈（Java实现）
该题在普通栈方法上多了个获取栈中最小值的方法。我们准备两个栈，和就是普通栈。就是用来记录栈中的最小值。我们在是正常的添加弹出数据，而对的操作要遵循以下几点。这样每次 获取最小值时，只需要将min栈的的弹出即可。
2024-11-07 18:55:37
207
原创 力扣225.用队列实现栈（Java实现）
对用户而言操作的是栈，而实际程序用的是队列。如果用户向一个空栈压入元素如果队列中只有一个元素，那么此刻取走a也符合栈的特性。倘若现在用户再加入b我们的处理方式如下在 b 加入队列之前，先看一下当前队列的大小，也就是然后再将 b 加入到队列中之后我们将 b 之前的 元素从队列取出，再向队尾加上。这种操作的次数也就是之前的。没看懂的话，我们再加入 c ，重新说明上面的流程。在 c 加入 队列 之前，我们记录当前 队列的，也就是 2之后将 c 加入队尾。
2024-11-07 17:45:35
279
原创 力扣622.设计循环队列（Java实现）
该循环队列使用数组实现，其中有几个注意点。我们需要四个变量对于变量可能有人会有疑惑，接下来我们说一下与的详细实现，其他方法的实现较为简单，下方代码已给出实现。
2024-11-07 15:55:00
275
原创 力扣86.分隔链表（Java实现）
该题是要将链表分为 <x 和 >=x 两个区域我们需要五个指针，分别是记录 <x 区域的 头部尾部记录 >=x 的区域的 头部尾部记录head的下一个节点我们先将head的下一个节点保存，即这么做是因为我们需要将 head与其后面的节点断开，即为了防止找不到next，所以将其保存而为什么要将 head与其后面的节点断开呢？请看下方流程一开始 head 的值为 1， 属于 <x 区域接着我们让head走到 4 的位置，即此时head值为4，属于区域。
2024-11-06 19:56:03
330
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人