思路： 题目的主要信息：  个节点，边使之任意两两都有相连，这是一棵树 每个节点初始值为0，一共m次增加数字的机会，会使给出的节点及与之直接相连的节点值加1 求最后的每个节点的数字  方法一：模拟过程具体做法：用构建图的方式，构建这棵树。遍历m次增加的机会，每次找到要增加节点的下标，将其值加1，然后遍历与下标相连的其他节点，值都加1.这里的res本来应该是哈希表的，但是因为数组的下标可以与节点名称一一对应，因此直接用数组。  class Solution { public: vector<int> solve(int n, int m, vector<int>&...

思路： 题目的主要信息：  一棵树每边长度为1，节点到节点的距离为 某个节点的权值 现求树每个节点的权值  方法一：两次dfs具体做法：我们可以用两次dfs解决这个问题。第一次dfs遍历这棵树，找到每个节点有多少个子节点，第二次dfs遍历每个节点，根据第一次找到的子节点数推算出到其他任何节点的距离。 public: vector<int> G[100001]; vector<int> s; //记录每个子树的结点数 vector<long> res; int dfs1(int u, int p, int d){ //u为当前节点，p为递归过来的前一个结点 i...

思路： 题目的主要信息：  一个二叉树根节点为1，l与r分别记录树的左右子节点，其中第个对应节点为的左右子节点 k数组中记录将要旋转的节点，旋转的时候将其所有子树及其子节点都交换位置 最后输出的数组为二叉树的中序遍历 0表示空节点  方法一：递归具体做法：利用递归的思想，遍历每一个要旋转的节点，将其子节点交换位置，并递归交换子节点的子节点。需要注意的是，如果一个节点被交换了两次，那么相当于没有被交换，因此我们用一个数组统计交换次数，如果次数为奇数，我们交换一次，次数为偶数，我们不交换。最后递归中序遍历（左根右）输出。 class Solution { public: void rotate(i...

思路： 题目的主要信息：  一个循环的圈，即数组首尾相接，数组中只有1 2 3三种元素 要使这三种元素相同的元素都排在一起，即类似111122222333或者112222233311 123的顺序不限  方法一：哈希表+贪心具体做法：因为123的顺序不限，因此我们的结果有6中排列组合方式，分别是：123132213231312321因为我们只需要检查这六种预定结果需要变换多少次，取其最小值即可，其中我们使用到了哈希表记录每个数字出现的次数。检查每个预定结果需要多少次交换的时候，我们调用findMin函数，利用贪心思想，首先我们看原数组与预定结果之间有多少位的差别，然后比较从每个预定结果的末尾位...

思路： 题目的主要信息：  p有n个数，一共有q次询问 每次询问从中选取，中选取,求有多少组满足，每个区间都是p的下标，从0开始  方法一：暴力法具体做法：遍历q次查询，遍历每个第一个区间的下标，与第二个区间的下标两两组合，判断是否满足条件。  class Solution { public: vector<int> PermutationQuery(int n, int q, vector<int>& p, vector<int>& l1, vector<int>& r1, vector<int>& ...

思路： 题目的主要信息：  数组PeoplePosition是每个人活动的区间，Personid表示感染者的下标 所有感染者直接活动过的区间，或者与之直接相交的区间，或者与之间接交叉的区间（与前面两个的并集相交）都视作感染区间 活动范围与感染区间有交集的人视为感染者计数，求最后的感染人数 下标从0开始  方法一：贪心具体做法：依据贪心思想，首先按照区间起点从小到大排序，维护区间终点的最大值，我们就可以知道每一块连续的区间包含了多少个小区间，再看感染者下标在哪一块里。如果一块连续的区间都没有目标感染者，那我们更新res为1，重新计数。  class Solution { public: int ...

思路： 题目的主要信息：  n个节点，n-1条边，使之全部连通，这就是一棵树 权值就是通话质量，任意去掉一条边，求影响的最大的通话质量（有n个城市受影响，就要用n乘上去掉边的权值）  即影响的城市数为去掉边后两个子树节点数相乘，因此我们找到，其中是去掉权值为的边后子树的节点数。 这道题需要求子树的节点数，只能用递归的dfs，自底向上相加，不能用bfs，也无法用非递归dfs，因为非递归dfs无法自底向上，这是树而不是二叉树。 方法：递归深度优先搜索具体做法：我们可以用深度优先搜索（dfs)的方式遍历树的每一条边，计算上述公式，找到最大值。因为深度优先搜索是自底向上的，因此节点数刚好可以累加。  ...

思路： 题目的主要信息：  n个节点，n-1条边，使之全部连通，这就是一棵树 树中任意节点的路径最长值，就是求树的直径  首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度优先搜索到另一最远距离就是树的直径。 方法一：两次深度优先搜索具体做法：我们需要用哈希表来存储树的边结构，将树看成图，以权重构建无向图，存入哈希表中。这里便是遍历u v w数组 ，将它们的信息存入哈希表中。因为dfs下标用到了0和-1，给的数据是节点从1开始的，因此录入哈希表的时候节点序号减1.再从顶点出发，利用dfs找到最远距离，第二次以当前最远距离再次调用dfs找到最远距离，第二个最远距离即是树...

思路： 题目的主要信息：  一个序列中仅有"("、")"、"?"三种符号，将其中的"?"替换成任意括号，使之变成一个括号合法的序列 括号合法的序列定义： 空序列一定合法 (+合法括号序列+) 为合法括号序列 ()+合法括号序列为合法括号序列   通俗来说就是，一个左括号就一定有一个右括号匹配，同理一个右括号就一定有一个左括号匹配  如果能构造出来则返回恢复后任意合法的括号序列，否则返回Impossible  方法一：数组记录法具体做法：首先我们准备两个辅助数组，index记录问号"?"出现的下标...

思路： 题目的主要信息：  字符串中只有字母AC 可选择任意k次变换将某个位置的字母变成另一个字母，求修改后的最长连续相同字母长度  方法一：暴力法具体做法：遍历字符串，每次遍历的点作为起点，如果起点为A，则第二次遍历后续遇到A直接计数，遇到C变换次数减1再计数，如果超过变换次数则与记录的最大值比较，维护最大值；如果起点为C，同理。 class Solution { public: int Solve(int k, string s) { int res = 0; for(int i = 0; i < s.length(); i++){ //每个字符都可以作为起点 int count =...

思路： 题目的主要信息：  一串字符串s中只包含了数字和大写字母 找出任意子串作为16进制数，求合法的最大数 结果一定是int型范围内  方法一：暴力法具体做法：遍历字符串每个字符都可以当成一个数字的起点，找到该数字的终点：第一个不合法的字母，将字串截取出来转换成数字，维护最大值即可。 class Solution { public: bool hex_valid(char c){ //判断字符是否合法 if((c >= '0' && c <= '9') || (c >= 'A' && c <= 'F')) return true; re...

思路： 题目的主要信息：  a数组是每个邻居在坐标上的位置（一维坐标），x数组牛牛搬家之后在坐标上的位置 要求每次搬家后最近邻居的最近距离  方法一：暴力法具体做法：对于每一种搬家方案，遍历每个邻居的位置，直接算出距离维护最小值。 class Solution { public: vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) { vector<int> res; for(int i = 0; i < m; i++){ int mindis = ...

思路： 题目的主要信息：  将字符串中数字为偶数的数字进行翻转，即翻转字符串，但只调换数字为偶数的位置 数字不包含0，字符串长度可能为0  方法一：暴力法具体做法：遍历字符串，用一个辅助数组顺序记录所有出现的偶数，再次遍历字符串，遇到偶数时，替换为辅助数组逆序中的字符。 class Solution { public: string change(string number) { string res = ""; vector<char> temp; int n = number.size(); if(n <= 1) //如果只有1位或者空，直接返回原串 ...

思路： 题目的主要信息：  给定一个数组，每次操作选择数组中一个区间的所有数字加1 使区间严格单调递增最少需要多少次操作  因为要严格单调递增，所以前一个数一定比后一个数字大，我们假设，那么我们只需要给即可严格大于，但是后面的数字因为的增加，需要严格单调也可能会要增加操作，刚好我们可以选择一个区间，因此我们每次区间可以选择成要递增这个数到数组结尾。 方法一：动态规划具体做法：用一个数组记录前一个元素比后一个元素大的差值，因为相等也不行，所以差值还要再加1。最后遍历数组将所有差值相加即可。 class Solution { public: long long IncreasingArray(ve...