题意整理： 题目以边的形式给出一个有向图，要求找到图中指定两个点（1，n）中的最短路径为了便于后续操作，我们先将给出的边权数组转化为点对之间的距离，对于没有边链接的距离为INT_MAX，对于重边取得较小值。 方法一：DFS（超时） 核心思想： 首先，我们需要从起点1开始，往能够前往的点进行搜索。此处需要维持一个vis数组记录哪些点已经进行了访问，如果再次访问将不对其进行访问，因为边权都是正值，明显对一个点再次访问不会得到更好的答案。当到达点n时停止搜索，更新答案。由于对边的访问没有特殊顺序，所有可能每次都以最差路径为开始进行遍历，时间复杂度很高，无法通过所有测试案例 核心代码： class S...

题意整理： 本题题意很明显。给定一个数组，需要找到数组中每个元素左边和右边的第一个比元素小的数字。 方法一：暴力 核心思想： 根据题意，对每一个元素，都各自往左以及往右遍历数组，直到到达数组边界或者找到第一个比元素小的数字即可。 核心代码： class Solution { public: vector<vector<int> > foundMonotoneStack(vector<int>& nums) { int n = nums.size(),res = 0; vector<vector<int>> ans(n, vec...

题意整理： 0-1背包是极其经典的动态规划问题。理清题意，题目通过数组给出 个背包，每个背包为二元数对 ，求解对给定体积 ，在选择若干个物品 ，满足时能够得到的最大重量。 方法一：动态规划 核心思想： 可以发现，对一个物体，我们可以选择将它装入背包，以及不选择，这就将问题划分成了更小的子问题，可以利用动态规划求解。令 表示当前分析到第 个物品，背包体积为 时能够得到的最大质量和。容易得到，方程的转移为 其中边界条件为 ,既没有选择任何物品，或背包容量为0时重量为0。返回的答案为  核心代码： class Solution { public: int knapsack(int V, int n,...

题意整理： 本题实际上的要求就是从数组中选择一些数，要求这些数字不相邻，求能够得到的最大子序列和。对于一个数字，如果它相邻的数字被选取，那么我们不能选取这个数字；如果它相邻的数字没有被选取，那么我们可以考虑选取或者不选取这个数字。注意到一个问题，对于连续的三个数 ,在这三个数中，我们最少会选择一个数字，否则不是最优解。如果 被选取，那么已经选择了一个数；否则，我们肯定会在 中选择一个数字，如果没有的话，那么选择 能够让结果比不选择更大，而且不会与其他元素造成矛盾。对于数组第一个元素和第二个元素，两个元素必须要选择一个，否则同上可以推出此序列不是最优解：既额外选择第一个元素不会引出矛盾且能够让答...

题意整理： 本题题意非常清晰，就是求出两个矩阵的矩阵乘积对于两个矩阵，设 为 的矩阵， 为 的矩阵，那么它们的乘积结果为一个 的矩阵 。其中， 的第 行第 列的元素计算方法如下 需要注意的是，只有矩阵的列数和矩阵的行数相同的时候，两个矩阵才能进行乘法对于本题，给定的两个矩阵维数相同，所以无需判断。 方法一：暴力模拟 核心思想： 直接根据上述公式，进行模拟后计算即可。具体实现为枚举矩阵 的行以及矩阵 的列，第三维的 枚举上述公式的 1 到 p 进行计算即可。 核心代码： class Solution { public: vector<vector<int> > solve...

题意整理： 本题题意较为简单，实际上就是在给定字符串中找到是否存在一个子串，该子串能够表示为一个字符串的重复拼接。也既从字符串 a 中，找到 字符串 s， s能够表示为 的形式（其中竖线只是表示分割）。例如字符串 fabcabcd 中，存在子串 abcabc，能够表示为 ，此处 s = abcabc, w = abc。 方法一：枚举起点和长度 核心思想： 我们可以枚举一个字符串 w 的起点以及长度，判断在它的后面是否存在与它一样的字符串，如果存在，说明满足题目中要求的重复拼接形式。具体实现时，对于字符串长度的枚举，可以从大到小枚举，这样找到答案后能够直接返回。其中枚举的起点为 ，即为字符串长度...

题意整理: 本题题意非常清晰，既判断给定字符串是否为回文字符串，回文字符串满足一个性质，既以字符串中间为对称点，与对称点距离相等的点值相等 方法一：翻转后对比 核心思想： 回文串的性质既第一个字符与最后一个字符相等，第二个字符与倒数第二个字符相等...。也即 。可以使用一个字符串表示原字符串反转后结果。如果原本的字符串是回文串，那么翻转后的字符串应该与原字符串相等，否则说明原字符串不是回文串 核心代码： class Solution { public: bool judge(string str) { string res = str; reverse(res.begin(), res.end...

题意整理： 题目会给出一个数组，需要对该数组进行排序后返回排序的结果 排序算法有很多种，下图给出常见的排序算法及其时间复杂度，空间复杂度以及稳定性（由于是在编译器中编写，用 n2 表示 n²）需要注意的是，对于本题，的算法明显是无法通过的。而的算法不是基于比较排序，需要依赖数据性质，在此处也不合适。所以可以采用的有快速排序、堆排序和归并排序。本题解实现快排和归并排序，对于堆排直接调用优先队列解决。 方法一：快速排序 核心思想： 快速排序是对较大的随机数据中速度最快的算法，可以视作冒泡排序的优化版本。快速排序的具体思路如下：在待排序的元素取出一个元素作为基准点，之后将待排序的元素进行分区，比基准...

题意整理: 去除题中的无关成分，实际上就是给出一个数组长度n，以及一个数字m,删除从起点开始的第m个数，最开始的起点为0，后面的起点为被删除元素的下一个元素。 实际上，理清题意后可以发现，本题即为约瑟夫环问题。最容易想到的思路就是使用数组模拟，但这涉及大量的数据搬运工作，非常耗时。一个优化就是使用链表表示数据进行模拟，这样可以省去数据搬运的时间，但时间复杂度仍为。但实际上，对约瑟夫环问题，进行一些观察很容易发现一个不需要模拟的更优的解题思路 方法一：数学 + 递归 核心思想： 可以对一个数列进行实际观察，这样更容易发现规律。假设 表示 个人，指定的数为 时最后留下的序号。对 个人，会被删除的元...

题意整理: 题目给出一个元素为非负整数的矩阵，要求计算出矩阵中任意起点开始，每次只能向上下左右移动且不允许重复访问一个格子时，并且要求只能够向数值更大的格子移动时，能够得到的最大长度 方法一：深度优先搜索 + 记忆化 核心思想： 可以利用深度优先搜索解决本题。对于两个单元格，值较小的格子可以有一条路径前往相邻的值较大的格子，所以可以对每个单元格进行深度优先搜索，一直往下到无法前进，得到一条路径长度。每次到达一个单元格时考虑四个方向的转移。对每个单元格分别进行深度优先搜索之后，即可得到矩阵中的最长递增路径的长度。以上分析已经可以正确的找到最长递增路径，但无法通过全部测试，原因在于简单的深度优先搜...

题意整理: 题目会给出一个包含括号，数字以及加减乘三种运算符的表达式，需要计算出表达式最终的值。 方法一：栈+递归 核心思想：可以利用栈对表达式进行解析。 思路：对于一个表达式，可以先记录当前遇到的前一个符号，开始时默认为+号。当解析完成一个数字时（字符串结尾或遇到符号），将数字与记录的符号进行运算后压栈，并更新符号。在遍历完字符串后，将栈中的数字一一弹出进行求和即可得到结果。具体分析：当遇到数字时，对其求值即可。当遇到左括号时，递归进入下一层当遇到右括号时，结束本层，计算出结果进行返回当遇到符号或字符串结尾时，根据前一个遇到的符号进行数字的压栈当前一个符号为号时，直接将数字压入（此时为 x ...

题意整理： 题目给出一颗二叉树的前序遍历以及中序遍历，要求得到这颗二叉树的右视图。右视图简单的理解，既在树的右侧能够看到的数的第一个元素。更专业的说，即为树的每一层的最右侧元素。 方法一：递归+层序遍历 核心思想： 可以先使用递归，从先序遍历和中序遍历中重构树，再使用层次遍历求出右视图。重构树：对一颗二叉树，其前序遍历的顺序为：1.遍历根节点 2.递归地遍历左子树 3.递归地遍历右子树。其中序遍历的顺序为：1.递归地遍历左子树. 2遍历根节点 3.递归地遍历右子树。在递归遍历子树的过程中，可以将这颗子树看成一颗新的树按以上步骤进行重建，所以重构可以通过简单的的递归实现。对于前序遍历，其第一个元...

题意整理: 本题要求设计一个LRU缓存结构，LRU即为最近最少使用算法，既缓存中保存的数据以使用顺序进行排序，缓存淘汰时选中最久为使用的进行淘汰 方法一：哈希表+双向链表 核心思想： LRU 缓存结构可以通过使用一个哈希表和一个双向链表维护所有在缓存中的键值对实现。双向链表按照键值对被使用的顺序进行存储了，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。哈希表负责通过缓存数据的键映射到其在双向链表中的位置，使得定位操作复杂度为。对一个操作，首先使用哈希表进行定位，找出其在双向链表中的位置，随后将其移动到双向链表的头部，即实现 的时间内完成 或者 操作。具体实现： :如果不存在，...

题意整理 本题题意既找到给定的两个字符串中的最长公共子序列，子序列为一个序列去除部分（也可以不去除）元素后，其他元素相对位置保持不变得到的序列。 方法一：动态规划 核心思想： 分析题意可以知道可以通过二维动态规划解决这道题假设两个字符串的长度分别为 。建立一个大小为行，列的dp数组，其中表示 长度为 的前缀和 长度为 的前缀两个字符串的最长公共子序列的长度。故有当 或 时值为。对其他情况，当 时，可将这两个字符作为公共字符，故此时 当 时,应取 和 中较大的一项进行转移 为了得到答案，同时需要一个方向数组记录转移方向，最后进行判断图示：  核心代码： class Solution { publ...