思路： 题目的主要信息：  对A任意位置切割，调转前后连接（即右边部分拼到左边前面），查看与B是否相等 AB都不为空，不用判断特殊情况  方法一：暴力求解 具体做法： 遍历A数组，每次利用string的substr函数从0到 i 截取前半部分，将其后半部分连在前面，再与B比较。 class Solution { public: bool solve(string A, string B) { if(A == B) //如果A=B直接不用旋转 return true; for(int i = 0; i < A.length() - 1; i++){ string temp = "...

思路： 题目的主要信息：  IPv4只有十进制数和分割点，其中数字在0-255之间，共4组，且不能有零开头的非零数，不能缺省 IPv6由8组16进制数组成，会出现a-fA-F，通过冒号分割，不可缺省，可以零开头，或者为一个单独零，每组最多4位。  方法一：分割字符串比较法 我们可以先对IP字符串进行分割，然后依次判断每个分割是否符合要求。 具体做法： 写一个split函数，遍历IP字符串，遇到.或者:将其分开储存在一个vector中，遍历vector，判断其中每个字符串是否符合上述要求。  class Solution { public: vector<string> split(...

思路： 题目的主要信息：  将十进制整数M转化为N进制整数，其中M可正可负可零，N最大为16 结果返回一个string字符串  进制之间的转化，我们常用的是连除取余法，但是因为余数可能会超过9，需要用ABCDEF来表示，我们可以事先设定一个字符串常量"0123456789ABCDEF"，每次余数对应该数字的下标即可。 连除法如下图： M=7，N=2，最终逆向连接为111 M=156，N=11，最终逆向连接为132  方法一：连除取余，逆向相加 具体做法： 使用连除法每次取余数，但是因为连除是从下取到上，因此我们连接字符串的时候每次新出现的需要连接在前头。 class Sol...

思路： 题目的主要信息：  对非负整数进行拼接，使得到数最大 得到的数可能会很大，需要用string保存  我们可以想到，对于一个数列拼接，自然是拼接后在前面数在数组前方比较好，这就涉及到了一个排序，如何排序：自然是顺序拼接较大的放在前面，将int转换成string后相连，然后比较字典序即可。  方法一：冒泡排序法 具体做法： 使用冒泡排序法，依次比较前后两个数，转化成string后相连的大小，排成由大到小的组合。 class Solution { public: string solve(vector<int>& nums) { for(int i = 0; i <...

思路： 题目的主要信息：  要求树的直径，即树上两点最远距离 这里的树不止是二叉树，都有可能 题目给的Tree_edge是一个点到另一个点有边，Edge_value为与之对应的边的权重weigh  方法一：两次深度优先搜索 首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度优先搜索到另一最远距离就是树的直径。  具体做法： 我们需要用map即哈希表来存储树的边结构，将树看成图，以权重构建无向图，存入map中。这里便是遍历Tree_edge和Edge_value，将它们的信息存入map中。 再从顶点出发，利用dfs找到最远距离，第二次以当前最远距离再次调用dfs找到最远...

思路： 题目的主要信息：  t1中含有t2的拓扑结构，即t2是t1的子树  方法一：先序递归法 具体做法： 对t1的每个结点递归遍历（先序），寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是t1与t2同步先序遍历，遍历完一个t2或者有不相等的结点为止。  class Solution { public: bool function(TreeNode* root1, TreeNode* root2){ if(root1 == NULL && root2 != NULL) //当一个结点存在另一个不存在时 return false; if(root1 != NULL...

思路： 题目的主要信息：  需要统计字符串出现的频率 最大复杂度为O(nlgk) 选出频率前K，相同频率算字典序最小  方法一：排序法 使用先统计次数，再排序，再找出前k的策略，但是不符合题目要求！！！！ 不符合规定 复杂度分析：  时间复杂度：O(nlgn)，排序算法最快O(nlgn)，遍历前k个 空间复杂度：O(1)，无额外空间  方法二：哈希表+小顶堆 拥有关联的一组数据快速访问，我们想到了哈希表，快速找到topK我们想到了小顶堆：当超过k时，与堆顶比较，若堆顶较小，则将堆顶pop出，加入新的元素。 具体做法： 使用map当哈希表，记录字符串与出现次数，做到快速访问。遍历哈希表，将其加入...

思路： 题目的主要信息：  链表至少为1，不用担心为空 判断单链表中的数值是否是回文  因为比较回文的基本思路是最前和最后比较，然后依次向中间靠齐，但是这是一个单链表，无法向前，所以我们要用另外的方法使它逆序。 方法一：中点逆链表法 具体做法： 找到链表长度，然后找到链表中间结点，从中间结点开始往后将链表指针反过来。然后比较前半部分和后半部分即可，因为后半部分相当于是逆序。  class Solution { public: ListNode* reverse(ListNode* head) { //反转链表指针 ListNode* prev = NULL; while (head != NU...

思路： 题目的主要信息：  数组无序，且有重复 需要找连续最长子序列长度，且连续不必相邻  方法一：排序法 既然无序我们可以用排序来解决。 具体做法： 使用sort的快排，将序列排成递增序列。然后遍历数组，依次将其与前一个数比较，若是比前一个大1，则连续子序列增加1；若是与前一个一样大，需要不管直接进入下一循环（去重）；若是比前一个大超过1，则连续断掉，重新计数，同时比较并更新最大值。 class Solution { public: int MLS(vector<int>& arr) { sort(arr.begin(), arr.end()); //排序 int n =...

思路： 题目的主要信息：  实现LFU的set与get函数，且复杂度为O(1) 每次调用这两个函数会给一个频率赋值，超出长度则移除频率最少的，若有频率相同，则移除访问时间最早的  方法一：平衡二叉树+哈希表 哈希表有非常好的之间访问，可以达成O(1)，而经过算术符号重载后的平衡二叉树，能够找到最近最少用的放在树根节点。 具体做法： 使用STL自带的map作为哈希表，set作为平衡二叉树。 对于 get函数，只需要查看一下哈希表mp是否有key这个键即可，有的话需要同时更新哈希表和集合中该缓存的使用频率cnt以及使用时间time，否则返回 -1。（时间最大等于操作数n，所以不用担心很大） 而对于...

思路： 题目的主要信息：  实现LRU缓存的模拟结构，包括加入函数set，访问函数get 结构有长度限制，加入新数时，超出长度则需要删除最不常访问的，其中set与get都访问 两个函数都是O(1)  方法一：构建双向链表 插入与访问值都是O(1)，没有任何一种数据结构可以做到。 于是我们可以想到数据结构的组合。访问O(1)很容易想到了哈希表，插入O(1)有很多，但是如果访问到了再插入，且超出长度要在O(1)之内删除，我们可以想到用链表。因为要在O(1)之内删除最不常访问的，所以是双向链表。于是我们的方法就是哈希表+双向链表。 具体做法： 用哈希表存储链表结点和key值，能够做到O(1)访问链表...

思路： 题目的主要信息：  仅存在一个最长公共子序列，不需要去重 最长公共子序列为空需要返回"-1"，而不是空序列，最后要变换  我们以dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度，若是i与j相等，则该问题可以变成1+dp[i][j]，即最长公共子序列长度加1，若是不相等，则换成两个子问题：dp[i][j-1]或者dp[i-1][j]，由此用递归即可以解决。 但是递归的复杂度过高，重复计算了太多部分，因此可以用动态规划，从前往后加： 方法一：动态规划 具体做法： 可以用二维矩阵dp记录在s1中以i结尾，s2中以j结尾的字符串的最长公共子序...

思路：  先找最长递增子序列长度 再根据长度逆向得到序列（逆向的原因是字典序更小，若是小值跑到后面去的情况，同样长度大值跑后面只会增加子序列长度）  要找到最长的递增子序列长度，常用方法是动态规划，dp[i]表示到元素i结尾时，最长的子序列的长度，初始化全部为1。  方法一：暴力动态规划（超时） 具体做法： 遍历两层，前面的指针i记录元素，后面指针j比较与前面的值，若是前面大，理论上dp[i]需要加上1，但是需要用dp[i] < dp[j] + 1判断是否是需要这个j，若是还有更大的就不需要这个j。但是因为两层遍历，时间复杂度很高，会超时。 class Solution { public...

思路： 题目中的要求：  实现栈的push、pop、top、min函数 访问每个函数的时间复杂度为O(1)  我们都知道栈结构的push、pop、top操作都是O(1)，但是min函数做不到，于是想到在push的时候将最小值记录下来，由于栈先进后出的特殊性，只能同样用栈来记录最小值。 方法：双栈法 具体做法： 使用一个栈记录进入栈的元素，正常进行push、pop、top操作，使用另一个栈记录每次push进入的最小值：每次push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈，若是较大，则第二个栈的栈顶元素再次入栈，因为即便加了一个元素，它依然是最小值。于是，每次访问最小值即访问第...