xqxls

分类

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

/ 注册

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

297篇文章 4409人学习

全部文章（共248篇）

题解 | #最长的括号子串# 来自专栏

题意整理给出一个长度为n的，仅包含字符'('和')'的字符串，计算最长的格式正确的括号子串的长度。格式正确的括号子串是指每一个左右括号都能相互抵消掉。方法一（栈） 1.解题思路首先新建一个栈，用于存放出现左括号字符对应的下标。遍历字符串，如果当前是左括号，直接将下标入栈。如果是右括号...

Java

2021-12-19

1 518

题解 | #进制转换# 来自专栏

题意整理给定一个十进制数M，将M转换为N进制数。 N大于10时，应在结果中使用大写字母表示大于10的一位，如'A'表示此位为10。如果M为负数，结果中要保留负号。方法一（利用库函数） 1.解题思路首先利用java自带的库函数，将M转化为N进制数。由于结果中大于10的部分是以小写字母表...

Java

2021-12-18

0 506

题解 | #树的直径# 来自专栏

题意整理给定一棵树，求出这棵树的直径，即树上最远两点的距离。方法一（dfs） 1.解题思路首先初始化邻接表，以边的起点为索引，将对应的边的终点以及边的权值放在该索引对应的list里。先从0号节点进入递归，通过递归找到当前节点所能到达的最远节点，跟新最远节点的规则是路径权值和大于之前的权...

Java

2021-12-18

4 713

题解 | #寻找第K大# 来自专栏

题意整理给定一个整数数组，找出数组中第 k 大的数。方法一（利用小顶堆） 1.解题思路首先定义一个小顶堆。然后将前k个元素直接加入到小顶堆。遍历后续每一个元素，如果比堆顶元素大，则可能是前k大的元素，加入小顶堆，并弹出堆顶元素。否则，直接跳过。 2.代码实现 import java...

Java

2021-12-18

0 434

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

题意整理给定一个数组arr，求arr数组的最长上升子序列。可能存在多个最长上升子序列，取字典序最小的那一个。方法一（动态规划） 1.解题思路状态定义：dp[i]dp[i]dp[i]表示以i位置元素结尾的最长上升子序列长度。状态初始化：以每个位置结尾的上升子序列长度至少为1。状态转移...

Java

2021-12-17

11 833

题解 | #丢棋子问题# 来自专栏

题意整理给定整数n作为楼层数，再给定整数k作为棋子数。如果想找到棋子不会摔碎的最高层数，考虑最差的情况下，至少需要扔多少次棋子。方法一（暴力递归） 1.解题思路递归终止条件：0层时，不需要确定，返回0次；一枚棋子时，需要一个一个地试，返回n。递归如何推进：假设当前为第i层，要么...

Java

2021-12-17

0 436

题解 | #矩阵元素查找# 来自专栏

题意整理给定一个有序矩阵mat和待查找元素x，矩阵的行和列都是从小到大有序的。求x在矩阵中的位置，以二元数组的形式返回。方法一（二分） 1.解题思路遍历所有行，对每一行所有元素进行二分查找。如果找到，直接返回。如果小于x，则排除左边所有元素。如果大于x，则排除右边所有元素。 2.代...

Java

2021-12-16

0 429

题解 | #跳台阶# 来自专栏

题意整理已知一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。方法一（迭代） 1.解题思路本题是一个基本的递归问题，假设跳上n级台阶有f(n)f(n)f(n)中跳法，则跳上n-1级、n-2级分别有f(n−1)f(n-1)f(n−1)、f(n−2)f...

Java

2021-12-15

0 359

题解 | #二叉搜索树与双向链表# 来自专栏

题意整理输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。方法一（递归） 1.解题思路由于二叉搜索树的中序遍历是从小到大依次输出的，所以可以利用中序遍历，在遍历的过程中，逐个改变当前节点的指向。预先定义一个pre指针，指向当前节点的前一个节点。以及一个head指针指向头节点。...

Java

2021-12-15

3 949

题解 | #数据分类处理# 来自专栏

题意整理输入一组整数序列I和一组规则整数序列R。根据条件找出满足规则Ri的I，并按指定格式输出。需要预先对R进行排序和去重，然后对于每一个Ri，找出所有包含Ri的I，依次输出I的个数、I的索引以及I。最后需要在输出结果之前，先输出结果中包含多少整数。方法一（TreeSet） 1.解题思路...

Java

2021-12-15

4 461