xqxls

分类

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

/ 注册

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

297篇文章 4409人学习

全部文章（共248篇）

题解 | #Nim游戏# 来自专栏

题意整理 A和B玩一个游戏。桌子上有n个石头，A、B轮流从桌子上取石头，每一回合可以取1-3个，谁最先取完石头则获胜，否则另一方获胜。给定石头数n，判断最终谁会获得胜利。方法一（动态规划） 1.解题思路状态定义：dp[i]dp[i]dp[i]表示i个石头时是否能获胜。状态初始化：i为...

Java

2022-01-15

4 537

题解 | #逆波兰表达式求值# 来自专栏

题意整理给定一个逆波兰表达式，表达式中仅包含加减乘除和数字。求表达式的值。方法一（栈） 1.解题思路逆波兰表达式求值的过程总是先列出运算符前面两个数字，然后将这两个数字进行相应运算，得到一个新的数字，这个数又与后面的数进行相应运算，直到结束。所以，可以先新建一个栈，当遇到数字时，直接压...

Java

2022-01-14

4 510

题解 | #将二叉搜索树改为累加树# 来自专栏

题意整理给定一个二叉搜索树，树上的节点各不相同。现在要将其修改为累加树，使每个节点的值变成原树中更大节点之和。方法一（递归） 1.解题思路由于二叉搜索树的左子树节点值总是小于当前节点，右子树节点值总是大于当前节点。所以按右、根、左顺序遍历时，树中的节点值一定是从大到小变化的，只要在遍历的...

Java

2022-01-14

1 430

题解 | #分割等和子集# 来自专栏

题意整理给定一个只包含正整数的数组nums。问是否能从这个数组取出若干个数使得取出的数之和和剩下的数之和相同。方法一（动态规划） 1.解题思路可以转化为0-1背包问题。只要从数组中找出若干个数，使得这些数的和等于所有数之和的一半即可。假设数组所有数的累加和为sum，则背包的容量为sum/...

Java

2022-01-14

0 514

题解 | #最短无序连续子数组# 来自专栏

题意整理给定一个整数数组，找出一个连续子数组，将这个子数组升序排列后整个数组都变为升序数组。求满足条件的最短的连续子数组的长度。方法一（排序） 1.解题思路首先定义一个新数组arr，将原数组的值复制到新数组。对原数组nums进行排序。从前往后，找到第一个不相等的元素位置，记为子数组...

Java

2022-01-13

0 482

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

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

Java

2022-01-13

10 686

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

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

Java

2021-12-22

0 545

题解 | #验证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