xqxls

题解

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

/ 注册

全部文章 / 题解（共292篇）

题解 | #几步可以从头跳到尾# 来自专栏

题意整理给定一个数组A。如果A数组中索引i对应值为t，说明可以从i处往后跳t步。求从1出发跳到n，至少需要跳几次方法一（从后往前贪心） 1.解题思路基本思路是从后往前找能到达目标格子的前一个格子，然后在所有满足条件的格子中选择一个尽可能靠前的格子（贪心），找到之后，立即跟新目标格子的位...

java 贪心数组动态规划

2021-07-26

4 871

题解 | #主持人调度# 来自专栏

题意整理有n个活动即将举办，每个活动都有一个开始时间和结束时间。现在派若干个主持人来主持活动，要求每一个主持人主持的活动中，各个活动的时间段（开始时间到结束时间）不重叠。方法一（优先队列） 1.解题思路首先对startEnd按开始时间从小到大排序，如果开始时间相同，则按结束时间排序。 ...

java 堆优先队列贪心排序

2021-07-26

18 2498

题解 | #未排序数组中累加和为给定值的最长子数组长度# 来自专栏

题意整理给定一个未排序数组。求累加和为k的子数组中最长的那个子数组的长度。方法一（枚举） 1.解题思路首先构建前缀和数组，表示原数组索引0到i-1之间所有元素之和。然后按子数组可能的长度，进行逆序枚举。当某个长度下，子数组累加和刚好等于k，则直接返回。 2代码实现 import...

java 前缀和哈希表数组

2021-07-25

0 677

题解 | #字典树的实现# 来自专栏

题意整理构造一个数据结构，用来处理字符串。这个数据结构可以插入、删除、查询字符串。查询分两种，一种是查询字符串是否出现过，另一种是查询前缀单词出现次数。方法一（TrieNode实现） 1.解题思路首先构建一个TrieNode结构，包括一个TrieNode类型的child数组，用于记录所...

java 字典树前缀树数组数据结构

2021-07-24

8 986

题解 | #序列化二叉树# 来自专栏

题意整理序列化：给定一颗二叉树，将二叉树的节点信息转化为字符串存储起来。反序列化：给定一个序列化后的字符串，根据字符串还原出二叉树。方法一（DFS） 1.解题思路序列化：将大问题拆分为小问题，每次如果还可以递归，就将当前层拆分为当前层的左孩子，加上当前层的右孩子，加上当前层节点值。递归...

java 递归队列 DFS BFS 树

2021-07-22

0 658

题解 | #正则表达式匹配# 来自专栏

题意整理用模式串来检验整个匹配串。模式串中的'.'匹配任何字符，'*'表示它前面的字符可以出现任意次（即0到无穷次）。方法一（记忆化递归） 1.解题思路递归终止条件：当模式串走完的时候，递归终止，如果此时，原串也走完了，则匹配成功；如果没走完，则匹配失败。每一层递归从上一层获取什么：...

java 递归动态规划

2021-07-21

6 974

题解 | #字符串的排列# 来自专栏

题意整理返回输入字符串的所有排列。将所有排列按字典序排好。方法一（回溯+set去重） 1.解题思路基本思路：将字符串转化为字符数组，然后进行递归。递归的过程中，首先固定某一个下标对应元素，然后将其他元素进行交换，并且每次交换后都进行回溯。当游标走到末尾的时候，将对应的数组转化为字符串，...

java 回溯排列

2021-07-21

0 810

题解 | #股票交易的最大收益（二）# 来自专栏

题意整理已知股票每一天的价格波动最多持有一只股，也就是买入时，必须卖出之前持有的股最多交易两次，求最大收益方法一（动态规划） 1.解题思路本题的难点在于交易次数进行了限定，可以多开一维空间来存储交易次数。所以可以用三维dp来求解。状态定义：第一维表示交易天数，第二维表示交易次数，第...

java 动态规划状态压缩

2021-07-18

6 1155

题解 | #股票(无限次交易)# 来自专栏

题意整理已知股票每一天的价格波动。最多持有一只股，也就是买入时必须卖出之前持有的股。可以无限次买入和卖出股票，求最大收益。方法一（贪心） 1.解题思路为了在股票交易中获得最大收益，我们肯定希望在极小值点买入，在邻近的极大值点卖出，由于是邻近的极大值点，所以在买入点和卖出点之间股票肯定是...

java 动态规划贪心

2021-07-18

0 703

题解 | #链表的奇偶重排# 来自专栏

题意整理给定一个链表。链表的奇数位、偶数位索引节点分别连在一起，重排成一个新的链表。方法一（转化为数组） 1.解题思路比较容易实现的方法是先将链表转化为数组，然后分别将奇数、偶数索引对应的值构造成对应的奇偶链表。最后再将奇链表和偶链表拼接起来。 2.代码实现 import java.ut...

java 链表双指针

2021-07-18

0 668