xqxls

分类

二叉树技巧总结(2) 未归档(3) 题解(292)

/ 注册

TA的专栏 297篇文章 4人订阅

297篇文章 4409人学习

全部文章（共13篇）

题解 | #父子情深# 来自专栏

题意整理给定一颗有n个节点的树，每个节点权值初始为0。现在有一个查询集合，集合中每一项提供两个参数r和v，每次查询将r节点及其子节点的权值增加v。返回最终每个节点的权值。方法一（DFS） 1.解题思路首先建立邻接表，用于访问某个节点的所有子节点。初始化查询中当前根节点的权值。按照...

java 递归 DFS BFS

2021-09-05

0 551

题解 | #新集合# 来自专栏

题意整理给定一个集合包含1到n共n个数，从中选若干数出来组成新的集合。规定一个限制数组，限制数组里的每一个数对不能同时出现在新集合中。求这样的新集合有多少个。方法一（二进制枚举） 1.解题思路定义1个mask，表示1到n有没有出现过，若mask最低位为1，则表示1出现过，次低位为1，...

java 组合递归二进制

2021-09-03

1 541

题解 | #中序序列# 来自专栏

题意整理给定一颗二叉树的先序遍历序列和后序遍历序列。求中序遍历序列（如果某个节点只有一个子节点，则必是左子节点）。方法一（递归+重建二叉树） 1.解题思路在每次递归中，可以确定当前根节点在先序遍历开头处，后续遍历结尾处。在后续遍历中找到当前节点的第一个左子节点，则后续遍历中，该节点之前...

java 递归哈希表

2021-09-03

4 932

题解 | #消息压缩# 来自专栏

题意整理有一段长度为n的消息，要将消息分成若干组，每组2个消息。第一个消息长度必须是4，第二个消息长度不能为0。求有多少种分割方法。方法一（递归） 1.解题思路递归终止条件：如果剩下的长度为0，说明正好完成分割，返回一种方案。递归如何推进：首先减去4，表示第一个消息的长度，然后第二...

java 递归动态规划

2021-09-01

0 554

题解 | #魔法数字# 来自专栏

题意整理有n和m两个数字。并且约定三种操作，其一是将n加一，其二是将n减一，其三是将n变为自己的平方数。求至少需要操作n多少次，能将其变为m。方法一（BFS） 1.解题思路首先进行特殊情况的判断，如果n和m都是1，直接返回0；如果n大于m，只能执行减一操作，直接返回n-m。然后初始...

java BFS 递归

2021-08-24

3 717

题解 | #简单变向# 来自专栏

题意整理牛牛在一个3行n列的跑道上跑步。牛牛的下一步只能在原来的那一行，或者由相邻行跳转过来（不能跨行或者越界）。求牛牛从(1,1)到(3,n)有多少条不同的路径可走。方法一（记忆化递归） 1.解题思路递归终止条件：起点第1行第1列的位置肯定是可达的。递归如何推进：总共有1，2，3...

java 动态规划递归记忆化递归

2021-08-13

0 554

题解 | #又见台阶# 来自专栏

题意整理总共有n层台阶，起初牛牛在第1层。牛牛每次能跳奇数层台阶，问有多少种不同的跳法到达第n层台阶（不能踩到积水的台阶）。方法一（记忆化递归） 1.解题思路递归终止条件：只有0层或1层的时候，共1种方案，返回1。递归如何推进：当前层的方案数，需要借助之前所有相隔奇数层的方案数来计算...

java 递归记忆化递归迭代

2021-08-12

0 519

题解 | #牛牛的数列# 来自专栏

方法一（递归） 1.解题思路递归终止条件：向左寻找时，寻找到索引0终止；向右寻找时，到索引nums.length-1终止。递归如何推进：向左寻找时，如果大于左边元素，直接由左边索引子序列加一，否则重置为1；向右寻找时，如果小于右边元素，直接由右边索引子序列加一，否则重置为1。每一层递归返回什...

java 动态规划递归

2021-07-30

1 579

题解 | #数的划分# 来自专栏

题意整理给定一个整数n和一个整数k，将n分成k份。每份不能为空，问有多少种分法（组合相同，排列不同的算同一种分法）。方法一（暴力递归） 1.解题思路递归终止条件：已经分了k份。递归如何推进：份数加一，剩余的数字rest要减去已经分配的，而use是当前尝试分配的（只要小于rest，都可...

java 递归动态规划

2021-07-29

3 875

题解 | #最大公约数# 来自专栏

题意整理输入整数a和b。求a和b的最大公约数。方法一（暴力法） 1.解题思路由于是a和b的最大公约数，那么它的范围一定在1到之间，我们逆序遍历这个区间，找到能同时被a和b整除的数即可。 2.代码实现 import java.util.*; public class Solution ...

java 迭代递归辗转相除法最大公约数

2021-07-28

0 595