xqxls

分类

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

/ 注册

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

297篇文章 4409人学习

全部文章（共297篇）

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

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

Java

2022-03-04

3 491

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

题意整理给定n个房子排成一圈，每个房子都有一定现金。现在有一个小偷，想偷到尽可能多的现金，但是不能偷相邻的房间，问最多偷多少现金。方法一（动态规划） 1.解题思路状态定义：dp[i]dp[i]dp[i]表示到第i个房间为止，能偷到的最多的现金。状态初始化：到第0个房间时，最多偷第0个...

Java

2022-03-03

3 690

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

题意整理给定并排的n个房子，每个房子都有一定现金。现在有一个小偷，想偷到尽可能多的现金，但是不能偷相邻的房间，问最多偷多少现金。方法一（动态规划） 1.解题思路状态定义：dp[i]dp[i]dp[i]表示到第i个房间为止，能偷到的最多的现金。状态初始化：到第0个房间时，最多偷第0个房...

Java

2022-03-02

3 446

题解 | #最大值# 来自专栏

题意整理给定一个只由字符'1'到'9'组成的长度为n的字符串s。求s的长度为k的子串中，对应的最大的十进制数值。方法一（字符串截取） 1.解题思路遍历整个字符串，每次截取当前长度为k的子串。计算子串对应的十进制数值，取最大的一个。 2.代码实现 import java.util.*...

Java

2022-03-01

0 401

题解 | #二进制取反# 来自专栏

题意整理给定一个二进制字符串num，可以选择该串中的任意一段区间进行取反（将0变为1，或将1变为0）。求取反之后的num可能的最大的字典序。方法一（循环+标记） 1.解题思路首先将字符串转化为字符数组。然后只要遍历到一个为0的位置，则将当前所有连续为0的位变为1。并且将标记打为tru...

Java

2022-02-28

1 518

题解 | #直方图内最大矩形# 来自专栏

题意整理给定一个数组heights，长度为n，height[i]是在第i点的高度。每个height都表示一个直方图，宽度为1。求能组成的最大面积的矩形。方法一（枚举） 1.解题思路思路很简单，就是遍历每一个直方图，将其高度作为矩形的高度，然后分别向前、向后延申，得到可能的矩形的最大长度。...

Java

2022-02-22

4 680

题解 | #最长公共子序列(一)# 来自专栏

题意整理给定两个字符串s1和s2。求这两个字符串的最长公共子序列的长度。方法一（动态规划） 1.解题思路状态定义：dp[i][j]dp[i][j]dp[i][j]表示s1长度为i，s2长度为j时的最长公共子序列的长度。状态初始化：初始阿长度均为0。状态转移：两层循环遍历s1和s2中...

Java

2022-02-19

0 404

题解 | #最长上升子序列(二)# 来自专栏

题意整理给定一个长度为n的数组。求它的最长上升子序列的长度。子序列是指按原来数组顺序取的若干个数字组成的序列，上升子序列是指序列中元素严格单调递增。方法一（动态规划） 1.解题思路状态定义：dp[i]dp[i]dp[i]表示以下标i结尾的最长上升子序列的长度。状态初始化：以任意下标结...

Java

2022-02-17

0 394

题解 | #最长上升子序列(一)# 来自专栏

题意整理给定一个长度为n的数组。求它的最长上升子序列的长度。子序列是指按原来数组顺序取的若干个数字组成的序列，上升子序列是指序列中元素严格单调递增。方法一（动态规划） 1.解题思路状态定义：dp[i]dp[i]dp[i]表示以下标i结尾的最长上升子序列的长度。状态初始化：以任意下标结...

Java

2022-02-16

12 1487

二叉树总结（四）来自专栏

1.技巧描述对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如预处理、用迭代代替递归、回溯。预处理：比如对要处理的数据提前做哈希映射，或者计算前缀和、后缀和，计算差分数组，构建前缀树，构建树状数组等等。用迭代代替递归：递归一般会有很多重复的计算...

2022-02-07

0 466