NC544 我们的距离 题目描述 给你一个树，边权都是1，令dis(i,j)dis(i,j)dis(i,j)表示iii点和jjj点的路径长度，对每个点iii，输出∑j∈(1,n)&&j!=idis(i,j)\sum_{j \in (1,n) \&\& j != i} dis(i,j)∑j∈(1,n)&&j!=i​dis(i,j) 1. 暴力做法 用Floyd求出所有的dis(i,j)dis(i,j)dis(i,j)，直接算。 /** * struct Point { * int x; * int y; * Point(int xx, in...

NC543 魔力转圈圈 描述 给你一个二叉树和一个操作序列，要求你根据操作序列对二叉树的某个子树做镜像操作，mmm次操作之后，求得操作后的中序序列。 1. 直接模拟 本题是二叉树镜像的升级, 最暴力的做法是直接按题意模拟，对每个操作执行一遍，再中序遍历。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 魔力转圈圈 * @param n int整型 * @param m int整型 * @param l int整型vector ...

NC542 能被多个质数整除的第K长子段 题目描述 给你一个数组AAA和正整数X，KX，KX，K，定义如下的连续子序列A[l...r]A[l...r]A[l...r]是好的： 存在至少X个不同的质数，可以整除子数组里的每个数 求数组A所有的好的子序列里，第KKK长的是多长？ 1. 暴力 直接根据题意模拟： 求2到maxAimax{A_i}maxAi​的所有素数 枚举l,rl, rl,r, 判断这个子序列是不是好的，如果是，记录答案 排序，取第K大 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定...

NC541 换座位 题目描述： 给你一个环状数组，数组的元素是1,2,3。 要想把它换成所有1相邻，所有2相邻，所有3相邻，至少需要多少人换座？ 1. 解法一 要想换成123相邻，需要枚举123的六种排***定先后关系，然后取每种换法的最小值。 首先计算每个数字出现了多少次，用map维护； 接下来计算每种排列需要交换几个数，思路如下： 首先不考虑环，计算目标数组三个数最后一位所在下标，记为x,y,z 不考虑环计算需要几个数字交换，也就是与预期位置不符的个数； 让环转起来，若当前x,y,z分别指向的数就是预定结果，说明上一“格子”错开了，“上一格”不用换，这次要换了，故多换一次，如果等于预定...

NC135. 股票交易的最大收益（二） 描述 假定你知道某只股票每一天价格的变动。 你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。 请设计一个函数，计算你所能获得的最大收益。 1. 动态规划 跟NC134的分析思路一样，第n天的最大收益只与前面一天的最大收益有关，而与每一天的具体操作无关，因此本题适用于动态规划。 本题可以用一个状态机描述，分别是没交易，第1/2次交易有股票，第1/2次交易无股票。因此适用于状态机转移型dp。 用1~5分别表示空仓，第1次交易有股票，第1次交易无股票，第2次交易有股票，第2次交易无股票，根据状态机...

NC134 股票(无限次交易) 描述 假定你知道 n 天内的某只股票每一天价格的变动。 你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。 请设计一个函数，计算你所能获得的最大收益。 1. 动态规划 观察本题的性质，每一天的最优收益，与前面的某一天的收益无关，只和前面所有天的最优收益有关系，体现了动态规划的无后效性，因此本题适用动态规划。 本题涉及了2个状态的互相转移，因此需要用状态机类型的dp。 设dp[i][0],dp[i][1]dp[i][0], dp[i][1]dp[i][0],dp[i][1] 分别表示截止到第i天，你持有股票和不持有股票的最优解，那么有如下关...

NC133 链表的奇偶重排 题目描述 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。 注意是节点的编号而非节点的数值。 1. 使用2个队列 使用两个队列分别记录下链表的奇数节点，偶数节点，再遍历链表，依次出队列装回去，只改变value即可。 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** ...

NC132 环形链表的约瑟夫问题 题目描述 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？ 1. 暴力解法 没什么好说的，用一个数组模拟整个过程，n-1轮循环，每轮报一次数，然后每次出局的时候剩下的数据向前平移，直到剩一个人。 class Solution { public: /** * * @param n int整型 * @param m int整型 * @return int整型 */...

NC131 数据流中的中位数 题目描述： 设计一种数据结构，支持快速获取中位数。 1. 暴力解法 直接用一个数组承载，每次获取中位数的时候排序，再取中间点。 注意这里要求的是浮点数，可以用整数*1.0进行类型转换。 class Solution { public: vector<int> array; void Insert(int num) { array.push_back(num); } double GetMedian() { sort(array.begin(), array.end()); ...

NC99 树的直径 题目描述 给定一棵树，求出这棵树的直径，即树上最远两点的距离。 1. Floyd算法（不合要求） 求出全局任意两点间距离，找最大值即可。 代码较简单且不合要求，不再赘述。 时间复杂度: O(n3)O(n^3)O(n3), 3重循环。 空间复杂度：O(n2)O(n^2)O(n2), 需要使用邻接矩阵存图。 2. 两趟dfs/bfs 思路一的复杂度显然太高了，我们不需要算那么多冗余的东西。 从任意一个点出发（通常是1号点），dfs或bfs这棵树，找到离这个点最远的点，记为s，再从s开始搜，找离s最远的点记为t，s到t的距离即是直径。 /** * struct Inter...

NC97 字符串出现次数的TopK问题 描述 给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。 返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。 对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。 比如"ah1x"小于"ahb"，"231"<”32“ 字符仅包含数字和字母 本题其实是 寻找第K大 这道题的变种，无非就是把整数的第K大变成了数据结构的第K大。 1. 排序 用一个哈希表维护每个字符串的出现频率，然后用pair<string, int>承载这个二元组，...

NC94 LFU缓存结构设计 题目描述 一个缓存结构需要实现如下功能。 set(key, value)：将记录(key, value)插入该结构 get(key)：返回key对应的value值, 但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；如果调用次数最少的key有多个，上次调用发生最早的key被删除 这就是LFU缓存替换算法。实现这个结构，K作为参数给出 1. 哈希表+平衡树 方法一用到的是平...

NC90 包含min函数的栈 题目描述： 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min 函数、push函数 及 pop函数 的时间复杂度都是 O(1)O(1)O(1) push(value):将value压入栈中 pop():弹出栈顶元素 top():获取栈顶元素 min():获取栈中最小元素 1. 双栈法 用两个栈模拟1个栈，栈1就是普通的栈，栈2维护最小值，每次入栈1时，判断是不是比栈2顶部的最小值小，如果是，则把该value放入栈2，如果不是，则把栈2的栈顶抄一遍，放入栈2. 这样，min函数就等价于栈2的顶部元素。 图示说明： cla...

NC59 矩阵的最小路径和 题目描述： 给定一个 n∗mn * mn∗m 的矩阵 aaa，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。 1. 深搜做法（TLE) 从左上角开始，每次向下或向右走，遍历所有路径，走到右下角时判断当前路径是不是最小的，如果是则更新之。 class Solution { public: /** * * @param matrix int整型vector<vector<>> the matrix * @return int整型 ...