知识点回文串思路这道题需要判断链表的值是不是构成了回文串。遍历链表，取出这些值，然后判断是不是回文即可。时间复杂度只需要遍历链表若干次 时间复杂度为 vector单次在尾部插入元素的均摊复杂度是，插入n次为总体时间复杂度为AC code （C++） /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规...

知识点二叉树 递归思路本题是要判断给出根节点的两个二叉树是不是完全相同。可以自顶向下递归的方法。首先确定递归出口，如果p和q均为空，或者均不为空且值相等，那么可以判断为true；否则判断为false如果在该点满足了相等，那么它们的左右儿子也应该对应相等，这样递归下去。时间复杂度访问每个结点最多一次，和结点总个数成正比，AC code （C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr...

知识点层序遍历 二叉树思路题目需要我们找出val和最大的一层，可以用层序遍历来找到每一层的所有元素。实现上，因为层序遍历是边权为1的BFS，在任意时刻queue中的idx的差值最大为1；因此我们整个层序遍历的过程中idx是非递减的，所以可以逐个累加val，如果出现idx和当前的idx不同，则更新结果。时间复杂度层序遍历只访问每个点一次，时间复杂度为AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x)...

知识点快速排序 计数排序 链表思路分析求的是整个链表的按值排序后的结果，可以把所有的值取出来进行排序后再重新连接为新的链表。在实现上可以建立虚拟头结点简化代码逻辑。排序可以选择快速排序或者 计数排序 时间复杂度遍历链表的复杂度为排序的复杂度为或者瓶颈在排序上AC code (C++) /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数...

知识点层序遍历 二叉树思路和上一道题非常类似。要求Z字形遍历，只需要在正常的层序遍历结果后翻转奇数层的结果。或者在加入答案的时候从后向前加入即可。时间复杂度层序遍历，遍历每个节点1次，AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法...

知识点层序遍历 二叉树思路分析把二叉树同一层的值拼接成一个字符串，然后把这些字符串返回。很经典的层序遍历题，我们只需要对二叉树跑层序遍历，把每次遍历到的val加入到对应的字符串中即可。在遍历的过程中遇到第一次出现的层的值，需要建立一个新的位置的空串来拼接，这里我是写的while循环（实际上最多只会执行一次，写if也可以），这个的原因是因为层序遍历实际上也是一种BFS，在同一时间之内，queue中的idx最多只会差1。时间复杂度层序遍历，访问每个结点各一次，时间复杂度vector每次插入的时间复杂度可以均摊为常数的。整体时间复杂度 AC code （C++） /** * struct TreeN...

知识点递归 二叉树思路分析给出一个二叉树根节点，要我们翻转整棵二叉树。首先，如果只有一个节点（只有根节点），我们不需要翻转。假如有子节点，需要先各自让左右子节点翻转之后，再交换左右子节点。而让子节点翻转显然是原问题的一个规模变小的子问题，可以用递归解决。显然递归出口是当二叉树到达树底端，出现空节点返回空节点即可。时间复杂度只访问每个节点常数次，时间复杂度AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val...

知识点二叉树思路分析要判断一棵二叉树是不是对称的。首先空树一定是满足条件的。假如这个树非空，我们从根节点自顶向下，除了根节点以外应该可以找到对称的匹配节点（只有根节点找不到对称节点）。那么我们定义一个函数check，来判断以r1和r2两个节点为根节点的子树是否是对称的。对于两个节点来说要求他们是满足check要求的，一定值要相等，或者都为空节点，如果不为空那么左右子树对应也要满足check。这样自顶向下递归下去即可判断。时间复杂度每个节点只访问了常数次，时间复杂度为AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode...

知识点多路归并 / 优先队列（堆）思路解析链表形式的多路归并题，由于原来的k个序列每一个都是递增的，只需要先把k个序列的头结点加入小顶堆，依次抛出堆顶元素后把堆顶元素的非空的next结点加入堆。即可实现多路归并得到有序序列。时间复杂度堆的每次插入的时间复杂度是添加n个元素的总时间复杂度是 n是全部链表的总结点数AC code (C++) /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <queu...

知识点链表题意分析链表循环右移k位，链表长度为n，那么右移k次和右移k%n次的效果相同。因此虽然k的范围很大，但是取模之后 k % n相当于把链表的后k%n个元素移到链表的头部，这里实现上可以用两个指针，一个先移动k%n次，然后两个一起移动，当前面的移动到了末尾，前面的指针就到了倒数第k%n的位置，从这里接到链表头部即可。时间复杂度只需要遍历链表若干次，时间复杂度AC code (C++) /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {...

知识点哈希表 链表思路假设不存在环，那么对应的是一条链，每头牛指向它的后面那头牛，指向的牛的编号不会出现重复如果出现重复，证明存在环。判断是否出现过，可以开一个布尔数组或者哈希表判断。时间复杂度每次哈希表查询和插入的时间复杂度是遍历一遍链表的复杂度为总体时间复杂度为AC code （c++） /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法...

知识点二叉树思路要我们判断两棵二叉树的叶子结点是不是从左到右逆序的，我们只需要遍历二叉树，从左到右找到叶子结点的值加入序列，最后比较即可。遍历二叉树时，先左子树后右子树即可做到访问到叶子结点是从左到右的。时间复杂度访问每个结点最多一次，和节点个数成正比 AC code （C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ clas...

知识点链表 模拟思路链表形式的模拟进位的大整数加法, 维护一个进位值carry由加法的进位我们可以知道下一次的carry值是由上一次的k除以10得到的, 当前位置的值是 k % 10当两个链表都没到达末尾, k值由上一次剩下的carry + l1->val + l2->val组成l1到达末尾, l2没到达末尾, k值由上一次剩下的carry + l2->val组成l2到达末尾, l1没到达末尾, k值由上一次剩下的carry + l1->val组成 (和上一条不会同时出现)l1 l2均到达末尾, k值由carry组成l1 l2 到达末尾, carry为0, 循环结束时间...

知识点递归 分治思路两个有序数组，一个长度为n，一个长度为m，找到两个数组归并后的中位数。根据中位数的定义，假如是奇数，那么需要找到第小的数作为答案；假如是偶数，那么需要找到第 小的数和小的数的平均数作为中位数。因此我们需要实现一个函数find可以在log时间内找到两个有序数组的第k小的数。对于找两个有序数组的第k小数的函数 find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k)：其中i是第一个数组第一个可以选的位置, j是第二个数组第一个可以选的位置首先，假如两个有序数组中的剩...