xqxls

分类

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

/ 注册

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

297篇文章 4409人学习

全部文章（共297篇）

题解 | #好多牛牛# 来自专栏

题意整理给定一个字符串S。求S中有多少子序列等于"niuniu"。方法一（动态规划） 1.解题思路假设长度为i-1的字符串s包含N个长度为j的字符串t（"niuniu"）的子序列。如果s的第i个字符不等于t的第j个字符，那么当前状态必定等于前一个状...

java 动态规划空间压缩

2021-08-17

0 581

题解 | #平衡的选择题# 来自专栏

题意整理牛牛准备出一套卷子，共n个多项选择题。正确答案中，A和C出现次数差距不超过1，B和D出现次数差距不超过2。问有多少种符合要求的正确答案。方法一（动态规划） 1.解题思路正确答案主要由两个因素决定它的种类数，一是A和C出现次数差距，二是B和D出现次数差距，可以通过这两个因素确定1...

java 动态规划空间压缩

2021-08-16

0 568

题解 | #魔法货车# 来自专栏

题意整理有m辆货车，每辆货车能运送若干个鸡蛋。总共要运送n个鸡蛋。如果货车装不下，可以使用魔法将某辆货车容量翻倍，问最少需要使用多少次魔法，才能一次运完所有鸡蛋。方法一（排序+贪心） 1.解题思路首先对x数组进行排序，获得容量最大的货车。然后计算还剩多少鸡蛋运不走，每次选择容量最大的货...

java 贪心

2021-08-14

0 616

题解 | #简单变向# 来自专栏

题意整理牛牛在一个3行n列的跑道上跑步。牛牛的下一步只能在原来的那一行，或者由相邻行跳转过来（不能跨行或者越界）。求牛牛从(1,1)到(3,n)有多少条不同的路径可走。方法一（记忆化递归） 1.解题思路递归终止条件：起点第1行第1列的位置肯定是可达的。递归如何推进：总共有1，2，3...

java 动态规划递归记忆化递归

2021-08-13

0 539

题解 | #又见台阶# 来自专栏

题意整理总共有n层台阶，起初牛牛在第1层。牛牛每次能跳奇数层台阶，问有多少种不同的跳法到达第n层台阶（不能踩到积水的台阶）。方法一（记忆化递归） 1.解题思路递归终止条件：只有0层或1层的时候，共1种方案，返回1。递归如何推进：当前层的方案数，需要借助之前所有相隔奇数层的方案数来计算...

java 递归记忆化递归迭代

2021-08-12

0 519

题解 | #牛妹的项链# 来自专栏

题意整理牛妹有一条由n个珠子组成的项链，每个珠子都有自己的颜色。现在牛妹要截取一段尽可能长的珠子，但是截下的这一段不能有相同颜色的珠子。方法一（暴力统计） 1.解题思路简要分析：由于项链总共有n颗珠子，我们可以枚举所有的起始位置，然后从每个起始位置开始，最多截取n个珠子，每一个起始位置（...

java 哈希表滑动窗口

2021-08-11

0 624

题解 | #k长连续子段和# 来自专栏

题意整理给定由n个数字组成的一个序列。求所有长度大于等于k的连续子段中，子段和的最大值。方法一（枚举k长子段和） 1.解题思路首先定义结果变量，用于记录最终结果。固定子段和开始处索引，枚举所有长度的子段，并记录子段和。如果长度大于等于k，则与res比较，并记录最大值。 2.代码实现...

java 动态规划

2021-08-11

0 741

题解 | #MagicString# 来自专栏

题意整理给定两个字符串S1和S2。求S2在S1的哪一个循环同构串中出现次数最多。如果有多个这样的同构串，输出字典序最小的那一个。方法一（kmp） 1.解题思路首先初始化计数数组。通过kmp算法，获取S2在同构串中出现的次数。记录最大的出现次数。通过最大出现次数定位到同构串起点索...

java kmp 哈希字符串

2021-08-10

0 645

题解 | #航海# 来自专栏

题意整理二维海面上有n只船，每只船有一个坐标，以及一个权值。求最小的带权曼哈顿距离。方法一（求极值） 1.解题思路简要分析：首先考虑一个简化版的情况，一维横轴上有n个点，要从这个n个点中，找到一个点，使得其他点移动到这个点的距离之和最小。假设当前处于第x个点的位置（位置p），当前的最小移...

java 中位数极值

2021-08-09

0 650

题解 | #旅行Ⅰ# 来自专栏

题意整理给定N个城市，以及每个城市的开销。一个前置城市数组，去y城市之前必须先去x城市。牛妹手上有V元，她每次都会去开销最小的城市，如果开销相同，就选编号较小的城市，求牛妹最多能去几个城市。方法一（优先队列+拓扑排序） 1.解题思路首先明确一个事实，如果要去某个城市，那么他的前置城市一...

java 优先队列拓扑排序

2021-08-08

0 699