xqxls

分类

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

/ 注册

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

297篇文章 4447人学习

全部文章（共28篇）

题解 | #车站建造问题# 来自专栏

题意整理数轴上有n个点，这n个点必须建立收集站。如果这n个点之间，相邻两个点间隔不是素数，则必须在中间修建对应数量的收集站，使得所有间隔是素数。求需要建设的收集站的最少数量。方法一（欧拉筛+动态规划） 1.解题思路首先计算给定n个特殊点的最大间隔距离，最大距离记为max。然后通过欧...

java 哥德巴赫猜想动态规划欧拉筛

2021-08-23

0 626

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

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

java 动态规划空间压缩

2021-08-17

0 594

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

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

java 动态规划空间压缩

2021-08-16

0 587

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

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

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

2021-08-13

0 556

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

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

java 动态规划

2021-08-11

0 762

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

题意整理给定N个城市，以及每个城市的开销。一个前置城市数组，即去y城市之前必须先去x城市。求牛妹用V元最多能去多少个城市旅游。方法一（记忆化递归） 1.解题思路前置知识：假设有N个城市，每个城市的编号是，牛妹去了哪几个城市可以用一个N位二进制编码mask来表示，mask中对应位是1，则...

java 记忆化递归动态规划状压dp

2021-08-07

0 626

题解 | #生产口罩# 来自专栏

题意整理牛妹要安排m名员工到n条生产线生产口罩。每条生产线有一个策略数组，对于这条生产线，牛妹要么一个员工也不给安排，要么按策略数组的某条策略进行安排。求怎么样安排每天生产的口罩最多，最多是多少。方法一（动态规划） 1.解题思路状态定义：表示i条生产线，j名员工每天产多少口罩。状...

java 动态规划状态压缩 01背包

2021-08-03

0 545

题解 | #牛牛恨66# 来自专栏

题意整理输入正整数。在到之间，有多少个数字不包含连续的，则输出多少。方法一（记忆化递归） 1.解题思路递归终止条件：当输入为0时，只有1不含66，返回1；当输入为1时，1到10这十个数都不含66，返回10。递归如何推进：当前位（第i位）可以选择6，也可以不选择6。如果选择6，...

java 记忆化递归动态规划

2021-08-01

0 726

题解 | #牛妹的招聘# 来自专栏

题意整理有n个同学，每个同学都有一个聪明值和一个勤奋值。从这个n个同学中选出若干同学，使得总的聪明值累加和和勤奋值累加和最大，但是聪明值累加和、勤奋值累加和必须大于0。方法一（单调栈） 1.解题思路牛妹想选择一些同学作为同事，如果最终有N个同学，那么总的组合数就是（每个同学，要么选，...

java 单调栈动态规划 01背包

2021-08-01

0 563

题解 | #牛牛的数列# 来自专栏

方法一（递归） 1.解题思路递归终止条件：向左寻找时，寻找到索引0终止；向右寻找时，到索引nums.length-1终止。递归如何推进：向左寻找时，如果大于左边元素，直接由左边索引子序列加一，否则重置为1；向右寻找时，如果小于右边元素，直接由右边索引子序列加一，否则重置为1。每一层递归返回什...

java 动态规划递归

2021-07-30

1 599