题目的主要信息：  n个节点，m条边，边权记录在邻接表cost中 求最小生成树的总边权  方法一：kruskal算法+并查集 具体做法： 最小生成树，我们可以连通的点看成是同一个并查集，利用并查集的思想来逐渐加边使所有节点连在一起。同时，最小生成树需要用kruskal算法的贪心思想，先对邻接表按照边权递增排序，然后从最小的边开始遍历，检查边的两边是否在同一个并查集中，如果在则不加这条边，如果不在则将这条边加入总边权，同时设置二者属于同一个并查集。  class Solution { public: static bool cmp(vector<int>& x, vector...

题目的主要信息：  在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径 如果 1 无法到 n ，输出 -1 图没有自环，可能有重边  方法一：floyd算法 具体做法： 可以用floyd算法计算任意两个节点之间的最短路径，然后取1-n的即可。用矩阵w表示任意两个节点之间的最短路径，初始化自己到自己为0，其余都是INT_MAX，然后用图的邻接矩阵来初始化矩阵w，选择边的最小值。 进行floyd算法时，首先枚举中转点，然后枚举起点和终点，当起点到中转点且中转点到终点的路径都存在时，比较最小值收缩路径。 class Solution { public: void f...

题目的主要信息：  给定一个长度为 n 的可能含有重复值的数组 arr ，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置 结果返回一个二维数组，表示所有位置相应的信息，如果找不到位置，则相应地方为-1 下标0开始 进阶要求：空间复杂度 O(n)O(n)O(n) ，时间复杂度 O(n)O(n)O(n)  方法一：暴力解法 具体做法： 遍历数组，对于数组每个元素arr[i]，分别从左边和右边开始向左和向右遍历，查找到第一个小于arr[i]的元素记录位置即可，如果没找到记录-1. class Solution { public: vector<vector<...

题目的主要信息：  给定数组arr，arr中所有的值都为正整数且不重复 arr中每个值代表一种面值的货币，每种面值的货币可以使用任意 组成aim的最少货币数 如果无解，请返回-1  方法一：空间记忆递归 具体做法： 对于需要凑成aimaimaim的钱，第一次我们可以选择使用arr[0]arr[0]arr[0]，则后续需要凑出aim−arr[0]aim-arr[0]aim−arr[0]的钱，那后续就是上一个的子问题，可以用递归进行。因为每种面值使用不受限，因此第一次我们可以使用arr数组中每一个，同理后续每次也可以使用arr数组中每一次，因此每次递归都要遍历arr数组，相当于分枝为arr.siz...

题目的主要信息：  给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，则这两个1属于同一个岛 只考虑上下左右为相邻 判断岛屿的个数  方法一：dfs 具体做法： 可以从上到下从左到右依次遍历矩阵，每次遇到一个1则岛屿数记为1，然后将与这个1及与其相邻的所有1全部置为0，相当于这个岛屿已经被统计了，避免重复统计。 将邻近的1全部置为0的方法，我们可以用dfs。从每次遍历到的第一个1为起点，分别向四个方向进行深度优先搜索，注意不能越界且值为1才能搜索过去，到达每个节点，将其值置为0即可。 class Solution { public: void dfs(vector<vector&...

题目的主要信息：  给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积 输入的矩阵是字符形式而非数字形式  方法一：动态规划 具体做法： 对于这类区间内找最大某某值的问题，一般采用动态规划。 可以用dp[i][j]dp[i][j]dp[i][j]表示以[i,j][i,j][i,j]点处为右下角的正方形的边长，很明显如果这个点本来就是0，则边长就为0，如果这个点是1才可能会有边长。如下图所示，需要需要检查这个点左边、上边、左上角三个点，这三个点可以直接决定以[i,j][i,j][i,j]点处为右下角的正方形的边长有多长，因为新增的正方形都是在它们三个最小值的基础...

题目的主要信息：  给定一个长度为 n 的无序数组 A ，包含正数、负数和 0 找出 3 个数，使得乘积最大，返回这个乘积  方法一：排序法 具体做法：  如果数组全是正数，则数组最大的三个数相乘乘积最大； 如果数组全是负数，则数组最大的三个数相乘乘积最大； 如果数组只有1个正数，其余都是负数，则数组最小的两个数再乘上正数乘积最大； 如果数组只有2个正数，其余都是负数，则数组最小的两个数再乘上较大的正数乘积最大； 如果数组只有1个负数，其余都是正数，则数组最大的三个数乘积最大； 如果数组有两个及以上的负数和三个及以上的正数，则最大值可能是三个最大的正数相乘，也可能是最小的两个负数乘积再乘上最大...

题目的主要信息：  给出2个版本号version1和version2，比较它们的大小 版本号是由修订号组成，修订号与修订号之间由一个"."连接 修订号可能有前导0，按从左到右的顺序依次比较它们的修订号，比较修订号时，只需比较忽略任何前导零后的整数值 如果版本号没有指定某个下标处的修订号，则该修订号视为0 版本号中每一节可能超过int的表达范围  方法一：流输入截取 具体做法： 可以通过字符串流输入按点进行分割，将两个版本号字符串通过分割得到修订号的数组。然后同时遍历两个数组，将数组的字符串组成数字再判断数字的大小关系。 需要注意，有可能某一个版本号比另一个短，修订号更少，此时应该比较下标i与修...

题目的主要信息：  给定一个元素非降序的、有重复数字的整型数组 nums 和一个目标值 target 找到第一个目标值的下标 如果找不到返回-1 进阶要求：时间复杂度O(log2n)O(log_2n)O(log2​n) ，空间复杂度O(1)O(1)O(1)  方法一：遍历查找 具体做法： 遍历数组，查找到第一个与目标值相等的数组元素，返回其下标。 class Solution { public: int search(vector<int>& nums, int target) { for(int i = 0; i < nums.size(); i++) //遍历数组...

题目的主要信息：  有一个长度为 n 的非降序数组，把一个数组最开始的若干个元素“平移”到数组的末尾，变成一个旋转数组 找到这个旋转数组的最小值 进阶要求：时间复杂度O(log2n)O(log_2n)O(log2​n)，空间复杂度O(1)O(1)O(1)  方法一：遍历查找 具体做法： 直接遍历数组，每个数组元素与res比较，维护最小值即可。 class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int res = INT_MAX; for(int i = 0; i < r...

题目的主要信息：  一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值 该二叉树每个节点值不同  方法一：中序非递归 具体做法： 使用栈辅助进行二叉树的中序遍历：栈记录当前节点，不断往左深入，直到左边子树为空，再弹出栈顶（即为当前子树的父节点），然后再访问其右子树，其中每棵子树都遵循左中右的次序。 而搜索二叉树的中序遍历恰好是升序的，我们可以用一个数组记录中序遍历的结果。然后遍历该数组，查看前一个元素比后一个元素大的情况。交换位置的有可能有两种情况，如下图所示：  情况一：相邻位置交换，直接将大小相反的两个元素加入答案； 情...

题目的主要信息：  给定一个32位的有符号整数num，将num中的数字部分反转 只反转数字部分，符号位部分不反转 最后的结果需要在32位有符号数范围之内，超出范围返回0  方法一：取模反转 具体做法： 数对10取余可以得到数字最后一位，将最后一位加在答案数字最前面，然后数除10即可去掉最后一位数字，后续继续取余，添加到答案数字后，答案数字添加前先乘10，空出最后一位给要加的数字，如图所示： 因此对答案数字乘10加上余数后可能会超过范围，因此在乘10之前要比较答案数字是否超过了INT型整数最大最小值的1/10，处理溢出。  class Solution { public: int reverse...

题目的主要信息：  一个长度为nnn的仅包含左右括号的字符串 计算最长的格式正确的括号子串的长度  方法一：栈 具体做法： 可以使用栈来记录左括号下标，每次遇到右括号则弹出左括号的下标，然后长度则更新为当前下标与栈顶下标的距离。因为遇到不符合的括号，可能会会使栈为空，因此需要使用start记录上一次结束的位置，这样用当前下标减去start即可获取长度。  class Solution { public: int longestValidParentheses(string s) { int res = 0; int start = -1; //记录上一次连续括号结束的位置 stack<i...

题目的主要信息：  给出一组数字，返回该组数字的所有排列 数字无重复 以数字在数组中的位置靠前为优先级，按字典序排列输出  方法一：递归 具体做法： 可以通过递归，每次递归对每个下标的元素与它后面每个元素交换位置成为一种排列的情况，当下标到了数组结尾即可认为一种排列加入答案中。当某一种交换的结果经过了所有递归，需要进行回溯，以保证每种情况都有。如下图所示：  class Solution { public: void recursion(vector<vector<int> > &res, vector<int> & num, int ind...