xqxls

分类

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

/ 注册

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

297篇文章 4409人学习

全部文章（共297篇）

题解 | #跳跃游戏(二)# 来自专栏

题意整理给定一个非负数组，数组的值记录当前位置所能跳的最大步数。从起始位置开始，如果能跳到结束位置，则可以获取每个位置对应值的积分。如果不能到结束位置，则不能获得积分，返回-1。方法一（暴力循环） 1.解题思路首先定义一个积分数组，用于记录对应结束点的最大积分。初始化0位置积分为对...

Java

2022-01-13

10 687

题解 | #设计LFU缓存结构# 来自专栏

题意整理设计一个缓存结构，实现set、get功能。 set(key, value)：将记录(key, value)插入该结构。get(key)：返回key对应的value值。缓存结构中最多存放k条记录，如果超过k条记录，则根据策略删掉一条记录。删除策略为：删掉调用次数最少的记录，如果调用次数...

Java

2021-12-22

0 546

题解 | #验证IP地址# 来自专栏

题意整理编写一个函数来验证输入的字符串是否是有效的IPv4或IPv6地址。 IPv4地址由4个十进制数表示，它们之间用"."隔开，每个数的范围在0-255。并且非0整数，不能以0开头。 IPv6地址由8组16进制的数字来表示，每组表示16比特。这些组数字通过":"隔开。不能存在某一组为空，或者等...

Java

2021-12-20

1 637

题解 | #把字符串转换成整数(atoi)# 来自专栏

题意整理写一个函数StrToInt，实现把字符串转换成整数的功能。不能直接使用库函数。字符串可能以空格+正负号+字符串表达式（数字、字母、负号、空格）+空格的形式出现。方法一（模拟） 1.解题思路首先去掉首尾空格。然后转化为字符数组，便于后续遍历。定义一个变量用于标记第一个位置是否...

Java

2021-12-19

0 430

题解 | #栈和排序# 来自专栏

题意整理给定一个1到n的排列和一个栈，并按照排列顺序入栈。在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列。方法一（动态规划） 1.解题思路首先新建一个栈，用于存放按顺序入栈的元素。再新建一个dpdpdp数组，dp[i]dp[i]dp[i]表示当前元素以及...

Java

2021-12-19

0 839

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

题意整理给出一个长度为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 488

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

题意整理给定一棵树，求出这棵树的直径，即树上最远两点的距离。方法一（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