牛客443689898号

分类

题解(3)

/ 注册

全部文章（共3篇）

购物车

购物车其实这题就是0-1背包问题首先来看一下经典背包问题，稍作修改就可以得出这题的解答 0-1背包问题问题描述：有一个背包可以装物品的总重量为W，现有N个物品，每个物品中w[i]，价值v[i]，用背包装物品，能装的最大价值是多少？定义状态转移数组dp[i][j]，表示前i个物品，背包重量为j...

2020-04-23

809 38011

链表中环的入口结点

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。解题思路 1、设快慢指针，当快慢指针相遇时，快指针走的长度刚好是慢指针的两倍 2、快慢指针一定在环中相遇，而且第一次相遇慢指针一定还没绕环超过一圈，因为当慢指针进入环时，此时快指针无论在环中的哪个位置，都可以在慢指针走...

2020-03-09

0 561

矩阵中的路径

矩阵中的路径思路：DFS+回溯 1、寻找矩阵中的入口 2、深度优先搜索，按照上->右->下->左的顺序 3、当前深度搜索路径不满足要求。回溯，回到上一步。重复步骤1，2，3，直到找到一条匹配路径退出。注意事项：需要有一个标记矩阵，标记当前已走过的路径。代码如下： class...

2020-03-09

0 626