描述已知一个背包最多能容纳物体的体积为V现有n个物品第i个物品的体积为, 第i个物品的重量为求当前背包最多能装多大重量的物品示例  输入：10,2,[[1,3],[10,4]]返回值：4说明：第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4   方法一：动态规划这道题是经典的用动态规划可以解决的题• 首先我们要明确两个问题，状态和选择，状态有两个，分别是是可选择的物品和背包的容量，选择也很容易想到，就是装进背包与不装进背包 • 其次，我们要明确数组的含义，这里我们需要定义一个二维数组,表示当前装进背包的物品数量，表示当前背包的容量，...

描述这是一道典型的约瑟夫环问题，我们可以这样理解：有n个人围成一圈，从第一个人开始报数，第m个将被杀掉，最后剩下一个，其余人都被杀掉，返回最后剩下的这个人的索引，如果没有人，则返回-1示例  输入：5,3返回值：3  方法一：环形链表我们可以用环形链表来存储数字，每次找到被选中的元素将其移除， 删除元素的时间复杂度为，但是查找元素的时间复杂度贼为，相比于，时间复杂度会降低  创建环形链表存储元素     因为链表是环形的，所以被删除元素的索引应该对n取模，每次定位到被删除元素处直接进行remove操作，同时n需要减1    import java.util.*; public class So...

描述给定两个nxn的矩阵A和B，求AxB。示例  输入：[[1,2],[3,2]],[[3,4],[2,1]]返回值：[[7,6],[13,14]]  方法一：数学模拟有两个矩阵：a和b（矩阵实际上就是二维数组） a矩阵和b矩阵可以做乘法运算必须满足a矩阵的列的数量等于b矩阵的行的数量 运算规则：a的每一行中的数字对应乘以b的每一列的数字把结果相加起来   相乘后的矩阵c行数量等于a矩阵的行数，列数等于b矩阵的列数，因为每次循环都是a的行与b的列,所以最外面两层循环分别是a的行的变化和b的列的变化，而最里面的循环可以是a的列或者是b的行来进行变化，因为a的列和是b的行数量是相等的，这样就可以使...

描述请写一个整数计算器，支持加减乘三种运算和括号。示例  输入："1+2"返回值：3  思路：题目给出了一个中缀表达式，要我们求表达式的结果，最直接的想法就是把中缀表达式转为后缀表达式，再利用一个栈完成后缀表达式的求值。方法一：中缀表达式转后缀表达式+后缀表达式求值中缀表达式转后缀表达式：  定义一个保存运算符的优先级，乘除优先级高于加减 定义一个动态数组保存后缀表达式，运算符栈存储运算符 遇到左括号时直接入运算符栈，遇到右括号时不断弹出栈中的运算符，并将其加入后缀表达式直到左括号出栈，左括号不加入后缀表达式 遇到操作数时，如果是多位数则需要将连续的多个数字取出，使用u保存...

描述给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。示例  输入："absba"返回值：true  方法一：双指针设置两个指针分别位于字符串的开头和末尾，向左移动，向右移动，指针未相遇时，如果两指针所指向的值不相等直接返回，否则循环结束时返回. import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param str string字符串 待判断的字符串 * @return bool布尔型 */ pu...

描述给定一个矩阵，矩阵内所有数均为非负整数。求一条路径，该路径上所有数是递增的。这个路径必须满足以下条件：1、对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。2、你不能走重复的单元格。即每个格子最多只能走一次。示例  输入：[[1,2,3],[4,5,6],[7,8,9]]返回值：5说明：1->2->3->6->9即可。当然这种递增路径不是唯一的。   方法一：记忆化深度优先搜索把矩阵看成一个有向图，每个单元格对应图中的一个节点，问题转化成在有向图中寻找最长路径。我们自然而然想到用深度优先搜索，从一个点开始进行深度优先搜索，...

描述给定一个数组，请你编写一个函数，返回该数组排序后的形式。示例  输入：[5,2,3,1,4]返回值：[1,2,3,4,5]  本题主要考察几种常见的排序算法，除了冒泡排序和选择排序的时间复杂度比较高，会出现运行超时现象，其他排序算法可以采用。思路：方法一：用库函数Arrays.sort import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ publ...

描述请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图示例  输入：[1,2,4,5,3],[4,2,5,1,3]返回值：[1,3,5]  思路：先通过前序遍历序列和中序遍历序列构造出二叉树，再通过bfs或者dfs打印出二叉树的右视图 方法一：递归+bfs对于任意一颗树而言，前序遍历的形式总是[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ] 即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]  用Map保存中序遍历的值和对应索引，关键可以快速定位每一次根结点的位置 在中序遍历中定位...