球球了给孩子一个offer吧

题解

/ 注册

全部文章 / 题解（共10篇）

题解 | #权值最大的路径#

题目：给出一个有向无环图，规定路径是单向且小序号指向大序号，每个节点都有权值。在图上求一条路径使得经过的节点权值和最大，输出路径方法一：递归先构建邻接矩阵存储每个结点的邻接结点记录以每个结点为结尾结点时的路径权值和以及路径，路径权值和存储在w数组中，对应路径存储在path数组中，找出路径权值和...

递归记忆化搜索

2021-09-04

0 682

题解 | #大鱼吃小鱼#

题目：现在有N条鱼，每条鱼的体积为Ai，从左到右拍成一排。A数组是一个排列。牛牛每轮可以执行一次大鱼吃小鱼的操作一次大鱼吃小鱼的操作：对于每条鱼，它在每一次操作时会吃掉右边比自己小的第一条鱼值得注意的时，在一次操作中，每条鱼吃比自己小的鱼的时候是同时发生的。举一个例子，假设现在有三条鱼,体积为分别[...

递归栈

2021-08-18

0 1284

题解 | #简单变向#

题目：矩阵大小为3xn，以(1,1)为起点可以向右走，右上对角线走，右下对角线走（不能出界），有些位置设置了路障，走不了，求出从(1,1)到(3,n)的路径数量方法一：记忆化递归可以用自顶向下的递归解决初始化路障数组，遇到路障直接返回0，为了避免重复计算，初始化记忆数组每个位置为0，用记忆数组记录...

记忆化搜索递归动态规划

2021-08-14

0 404

题解 | #又见台阶#

题目：台阶一共有n层，有一些台阶上有积水。牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n层，但是它不希望在跳跃的过程中踩到积水。已知有m个台阶上有积水。请问牛牛在不踩到积水的情况下跳到第n层有多少种不同的方案。如果不可能到达第n层，则答案为0。为了防止答案过大，答案对1e9+7取模。方法一...

记忆化搜索递归

2021-08-13

0 469

题解 | #切割成本#

题目描述：将一条长度为x的线段切成若干段，切割点已给出，每次切割的成本为切割后产生的两段线段长度之和，求最小的切割成本。示例输入：20,[2,5,10,18]返回值：45说明：线段长为20，切割点为[2,5,10,18]。第一种方案：1.先切开第一个点，成本为2+18=202.切开第二个点，成本...

区间dp 记忆化搜索递归

2021-08-04

0 511

题解 | #牛妹的蛋糕#

题目描述众所周知，牛妹非常喜欢吃蛋糕。第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？这道题是典型的猴子吃桃问题...

递归动态规划

2021-08-03

0 685

题解 | #牛妹的礼物#

题意描述：有NxM大小的矩阵，从左上角走到右下角，只能向右，下，右下走，求到达右下角的最短带权路径长度方法一：动态规划采用递推的方式,定义一个二维数组，显然，的值就是从左上角走到的最短路径，要求从左上角到右下角的最短路径就是求的值状态转移方程： import java.util.*; p...

动态规划递归

2021-08-01

0 445

题解 | #不相邻最大子序列和#

描述给你一个n（1≤n≤10^5），和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，求该序列的最大子序列和（挑选出的子序列可以为空）。示例输入：3,[1,2,3]返回值：4说明：有[],[1],[2],[3],[1,3] 4种选取方式其中[1,3]选取最优，答案为4 这道题本质上是“...

记忆化搜索递归动态规划

2021-07-28

0 573

题解 | #孩子们的游戏(圆圈中最后剩下的数)#

描述这是一道典型的约瑟夫环问题，我们可以这样理解：有n个人围成一圈，从第一个人开始报数，第m个将被杀掉，最后剩下一个，其余人都被杀掉，返回最后剩下的这个人的索引，如果没有人，则返回-1示例输入：5,3返回值：3 方法一：环形链表我们可以用环形链表来存储数字，每次找到被选中的元素将其移除，删除...

递归

2021-07-25

0 410

题解 | #输出二叉树的右视图#

描述请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图示例输入：[1,2,4,5,3],[4,2,5,1,3]返回值：[1,3,5] 思路：先通过前序遍历序列和中序遍历序列构造出二叉树，再通过bfs或者dfs打印出二叉树的右视图方法一：递归+bfs对于任意一颗树而言，前序遍历...

递归 dfs bfs

2021-07-18

0 666