xqxls

分类

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

/ 注册

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

297篇文章 4409人学习

全部文章（共248篇）

题解 | #岛屿的最大面积# 来自专栏

题意整理给定一个用n*m矩阵表示的群岛的地图，其中1表示岛屿，0表示海洋。求最大的岛屿的面积，两个岛屿相邻算同一个岛屿。方法一（深度优先搜索） 1.思路整理遍历所有的岛屿。如果当前岛屿面积为1，则通过深度优先搜索（利用递归实现），找到与之相邻的所有的岛屿，计算其面积。统计所有面积中...

Java

2022-03-11

1 833

题解 | #两两交换链表的节点# 来自专栏

题意整理给定一个链表，要求两两交换相邻节点。方法一（递归） 1.思路整理递归终止条件：只有一个节点，或没有节点了，递归终止。递归如何传递：通过递归可以得到从当前节点的下下个节点断开之后的链表。比如1-2-3-4中的3-4部分。然后将当前节点的下一个节点，指向这个断开之后的链表，同时记录...

Java

2022-03-11

0 579

题解 | #二进制求和# 来自专栏

题意整理给定两个用字符串表示的二进制数。求它们的和，同样以字符串形式返回。方法一（模拟竖式计算） 1.思路整理模拟这两个数竖式计算的过程。逐次从低位到高位相加，逢二进一，每次将当前位加入到结果，同时记录余数。最后将结果反转之后返回。图解展示： 2.代码实现 import ja...

Java

2022-03-10

1 612

题解 | #字符串的全部子序列# 来自专栏

题意整理给定一个字符串s，长度为n，求s的所有子序列。如果子序列重复，则只添加一次。方法一（回溯） 1.思路整理首先将字符串转化为字符数组。然后对字符数组进行遍历，每一个字符要么添加、要么不添加，利用回溯法添加字符数组中所有可能的字符组合，每一个组合代表一个子序列。每完成一轮添加，将...

Java

2022-03-09

0 1139

题解 | #二叉树的前序遍历# 来自专栏

题意整理给定一颗二叉树的根节点root。求该二叉树的前序遍历。方法一（递归） 1.思路整理先序遍历的顺序是根、左、右。如果直接按照递归的思路进行遍历，只需在对应的位置将当前节点加入到序列即可。 2.代码实现 import java.util.*; /* * public class ...

Java

2022-03-07

0 512

题解 | #判断是不是二叉搜索树# 来自专栏

题意整理给定一颗二叉树。判断该树是否是二叉搜索树。方法一（递归） 1.思路整理判断搜索二叉树（BST）：考虑搜索二叉树的定义，每一个节点的值应该大于等于左子树中的最大值，小于等于右子树中的最小值。所以我们可以利用递归遍历每一个节点，如果某个节点不满足定义，则不合法，直接返回false。...

Java

2022-03-07

4 582

题解 | #最长公共子数组# 来自专栏

题意整理给定两个整数数组，求两个数组的最长的公共子数组的长度。方法一（动态规划） 1.解题思路状态定义：dp[i][j]表示A的子数组以i-1结尾，B的子数组以j-1结尾时的最长公共子数组长度。状态转移：两层循环，遍历A数组和B数组中每一个元素，如果当前元素相等，则由左上方对应位置状态...

Java

2022-03-06

0 634

题解 | #给数组加一# 来自专栏

题意整理给定一个用数组表示的数字，即数组中每个数表示一个数位上的数，例如[1,2,3][1,2,3][1,2,3]，表示123。求这个数字加1后的结果，以数组的形式返回。方法一（模拟） 1.解题思路首先定义一个长度为n+1的新数组res和一个进位carry。然后逆序遍历原数组，根据进...

Java

2022-03-05

0 661

题解 | #长度为 K 的重复字符子串# 来自专栏

题意整理给定一个由小写字母组成的长度为n的字符串S，找出所有长度为k且包含重复字符的子串。返回全部满足要求的子串的数目。方法一（字符串截取） 1.解题思路遍历整个字符串，依次截取长度为k的子串。每次判断子串是否包含重复字符，如果包含，则计数加1。 2.代码实现 import jav...

Java

2022-03-05

0 687

题解 | #打家劫舍(三)# 来自专栏

题意整理给定一个二叉树结构的小区，每个节点都有一个房子。现在有一个小偷，想偷到尽可能多的现金，但是不能偷相邻的房间，问最多偷多少现金。方法一（递归） 1.解题思路递归终止条件：遍历完所有节点。递归如何传递：分别计算选与不选当前节点的情况。如果选，则加上当前节点、左孩子对应的孙子的情况...

Java

2022-03-04

3 491