Bad man

分类

/ 注册

全部文章（共125篇）

题解 | #牛群的最长距离#

知识点：二叉树，递归要找到最长的距离，在树中，若两个节点的距离最长，则两个节点必然都是叶子节点，也就是我们可以从每一个节点出发，向下寻找左右子树中最深的叶子节点，将节点数相加即可。同时，我们也要遍历所有的节点，对于每一个节点都去统计最深叶子节点的路径长度，即可得到答案。 Java题解如下 imp...

2023-08-20

0 379

题解 | #牛的生长情况#

知识点：单调栈我们要找到每个元素后面的更大元素，我们可以通过使用单调栈的思想来解决，对于这类下一个更大元素的题目，都可以使用单调栈来解决，我们维护一个栈，若栈顶元素小于当前元素，则将其出栈，直至栈顶元素大于等于当前元素，或者栈为空。这样可以保证在栈内的元素弹出时，就找到了比其更大的元素，对于这道题...

2023-08-19

1 501

题解 | #农场牛群族谱#

知识点：二叉树，递归我们要找到两个节点的最近公共祖先，首先若节点为空，返回-1，若节点等于p节点或q节点，直接返回节点值即可，表明当前节点中含有了p或q节点。如果不满足以上条件，说明p或q节点有可能在其子树上，故我们可以对当前节点的左右子节点进行递归判断，若左右子树中返回的不是-1，说明左右子树中...

2023-08-19

0 395

题解 | #农场牛的最佳观赏区间#

知识点：二叉树这道题目完全可以按照普通二叉树的方法来做，递归遍历所有节点，若节点值在目标区间内，则统计在总和中，同时向下遍历子节点，若不在目标区间中，则直接向下遍历子节点，重复以上判断，若节点为空，直接返回0即可，遍历整个二叉树，得到的结果即为整个目标区间内的和。 Java题解如下 impor...

2023-08-19

0 373

题解 | #最小三角路径和#

知识点：动态规划对于每一行来说，我们最小的路径和取决于上一行的元素和大小，我们对当前行的每一个元素进行判断，取其上一行的两个相邻元素和中最小的那个作为经过当前元素的最小路径和，每一层都重复以上判断，最终我们遍历最后一行列的元素，得到最小的路径和。部分测试用例有些问题，并不符合题目所说的三角形排列，...

2023-08-18

0 351

题解 | #训练聪明的牛II#

知识点：动态规划这道题一开始想要使用DFS，或者BFS，会造成超时或者内存溢出的情况，故需要使用动态规划来解决，我们定义dp[i]为组成 i 需要的元素个数，初始化将已有的元素dp设置为1，同时我们也需要定义dp[0]=0，表示对于目标和为零，我们可以从0开始遍历至目标和，同时，我们遍历更小元素，...

2023-08-18

0 378

题解 | #训练聪明的牛#

知识点：动态规划关于能否组成一个字符串，是由两部分决定：1.前半部分是否已经是可组合成的字符串2.后半部分字符串是否存在于字符字典中当两个条件都满足时，说明当前字符串可由字符字典组成。我们可以定义一个状态dp[i]，表示从0到当前位置i的字符串是可以组成的，对于dp[0]，我们初始化为true，表示...

2023-08-18

0 354

题解 | #农场最大产奶牛群#

知识点：二叉树，递归题目要求找到一个最大的路径和，可以由任意节点到达叶子节点，题目并没有要求只能向下寻找叶子节点，也就是最大的路径和，一定是一个叶子节点向上累加，再向下累加到另一个叶子节点，这样才能保证路径和一定是最大的，所以，我们应该寻找每一个节点所能到达的最大的左右叶子节点，也就是将当前节点作为...

2023-08-17

0 297

题解 | #牛群的合并#

知识点：链表我们需要合并多个链表，使其升序排列，一个有效的方法将所有的节点放入堆中，遍历完所有节点，同时将节点的后继指针指向空，最后在依次从堆顶拿出最小的节点，组合成新的链表。需要注意的是，在Java中使用PriorityQueue优先级队列来实现堆，我们也需要重写堆的比较方法，使其按照节点的val...

2023-08-17

0 346

题解 | #牛群编号变更#

知识点：动态规划这是一个经典的动态规划题目，这道题目的关键是要找到两个字符串中的最长相同子字符串长度，定义dp[i][j]为word1到达i位置，word2到达j位置时，二者相同的子字符串长度值，此时dp[i][j]有两种情况，若i位置与j位置字符相同，则dp[i][j] = dp[i-1][j-1...

2023-08-16

0 295